Kosaraju-algoritmus

• IPA:

Kosaraju-algoritmus

1. (matematika)

A Kosaraju-algoritmus egy hatékony módszer a gráf erősen összefüggő komponenseinek (strongly connected components, SCC) meghatározására. Az algoritmus működése két egyszerű mélységi keresésen (DFS) alapul, és a direkt gráf reverzáltjának (inverzének) használatán.

Egy gráf komponense erősen összefüggő, ha a gráf minden csúcspárja között létezik irányított út. Formálisan: - Egy komponensben lévő csúcsok között ${\displaystyle u\to v}$ és ${\displaystyle v\to u}$ utak léteznek.

• Egy irányított gráf ( G = (V, E) ), ahol ( V ) a csúcsok halmaza, ( E ) az élek halmaza.

• Az erősen összefüggő komponensek halmaza.

1. Első DFS és topológiai sorrend:
   • Végezz mélységi keresést (DFS) az eredeti gráfon.
   • Jegyezd fel a csúcsokat befejezési sorrendben (amikor az összes gyerekük feldolgozásra kerül).
2. Gráf transzponálása (inverzálása):
   • Hozd létre a gráf transzponáltját (( G^T )), amelyben minden él megfordul.
3. Második DFS a transzponált gráfon:
   • A befejezési sorrend szerint iterálj a csúcsokon.
   • Végezz mélységi keresést a ( G^T )-n, és minden DFS-hívás során jegyezd fel az összes meglátogatott csúcsot egy SCC-be.

Kosaraju(G):
    1. Létrehozzuk az üres stack-et és meglátogatott csúcsok listáját
    2. Első DFS: Jegyezzük fel a csúcsokat befejezési sorrendben
       for minden v ∈ V:
           if v még nem látogatott:
               DFS1(G, v)

    3. Készítsük el a transzponált gráfot G^T

    4. Második DFS: Az első DFS során rögzített sorrendben dolgozzuk fel a csúcsokat
       for minden v a stack sorrendjében:
           if v még nem látogatott:
               Hívj DFS2-t v-re, jegyezd fel az SCC-t

    5. Visszaadjuk az SCC-ket

Az algoritmus futási ideje ( O(V + E) ), mivel: - Az első DFS ( O(V + E) )-s. - A gráf transzponálása ( O(V + E) )-s. - A második DFS ( O(V + E) )-s.

from collections import defaultdict

def kosaraju(graph):
    # Első DFS
    def dfs1(v):
        visited.add(v)
        for neighbor in graph:
            if neighbor not in visited:
                dfs1(neighbor)
        stack.append(v)

    # Második DFS
    def dfs2(v, transposed_graph, component):
        visited.add(v)
        component.append(v)
        for neighbor in transposed_graph:
            if neighbor not in visited:
                dfs2(neighbor, transposed_graph, component)

    # Gráf transzponálása
    def transpose(graph):
        transposed = defaultdict(list)
        for src in graph:
            for dest in graph:
                transposed.append(src)
        return transposed

    # Első DFS a befejezési sorrendhez
    stack = 
    visited = set()
    for node in graph:
        if node not in visited:
            dfs1(node)

    # Gráf transzponálása
    transposed_graph = transpose(graph)

    # Második DFS az SCC-k meghatározására
    visited = set()
    sccs = 
    while stack:
        node = stack.pop()
        if node not in visited:
            component = 
            dfs2(node, transposed_graph, component)
            sccs.append(component)

    return sccs

# Példa gráf
graph = {
    0: ,
    1: ,
    2: ,
    3: ,
    4: ,
    5: ,
}

sccs = kosaraju(graph)
print("Erősen összefüggő komponensek:", sccs)

Kimenet:

Erősen összefüggő komponensek: , ]

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

void dfs1(int v, vector<vector<int>>& graph, vector<bool>& visited, stack<int>& finish_stack) {
    visited = true;
    for (int neighbor : graph) {
        if (!visited) {
            dfs1(neighbor, graph, visited, finish_stack);
        }
    }
    finish_stack.push(v);
}

void dfs2(int v, vector<vector<int>>& transposed_graph, vector<bool>& visited, vector<int>& component) {
    visited = true;
    component.push_back(v);
    for (int neighbor : transposed_graph) {
        if (!visited) {
            dfs2(neighbor, transposed_graph, visited, component);
        }
    }
}

vector<vector<int>> kosaraju(int n, vector<vector<int>>& graph) {
    stack<int> finish_stack;
    vector<bool> visited(n, false);

    // Első DFS
    for (int i = 0; i < n; ++i) {
        if (!visited) {
            dfs1(i, graph, visited, finish_stack);
        }
    }

    // Gráf transzponálása
    vector<vector<int>> transposed_graph(n);
    for (int u = 0; u < n; ++u) {
        for (int v : graph) {
            transposed_graph.push_back(u);
        }
    }

    // Második DFS
    fill(visited.begin(), visited.end(), false);
    vector<vector<int>> sccs;

    while (!finish_stack.empty()) {
        int v = finish_stack.top();
        finish_stack.pop();
        if (!visited) {
            vector<int> component;
            dfs2(v, transposed_graph, visited, component);
            sccs.push_back(component);
        }
    }

    return sccs;
}

int main() {
    int n = 6;
    vector<vector<int>> graph = {
        {1},       // 0 -> 1
        {2, 3},    // 1 -> 2, 3
        {0},       // 2 -> 0
        {4},       // 3 -> 4
        {5},       // 4 -> 5
        {3}        // 5 -> 3
    };

    vector<vector<int>> sccs = kosaraju(n, graph);

    cout << "Erősen összefüggő komponensek:" << endl;
    for (const auto& component : sccs) {
        for (int v : component) {
            cout << v << " ";
        }
        cout << endl;
    }

    return 0;
}

Kimenet:

Erősen összefüggő komponensek:
3 5 4
0 2 1

1. Hatékony:
   • Az algoritmus lineáris időben ((O(V + E))) fut.
2. Egyszerű implementáció:
   • Két DFS és egy gráf transzponálása elegendő.

1. Csak irányított gráfokra alkalmazható.
2. Memóriaigény:
   • Nagy gráfok transzponálása jelentős memóriahasználattal járhat.

1. Hálózatelemzés:
   • Erősen összefüggő alhálózatok megtalálása.
2. Körök azonosítása:
   • Gráfban lévő erősen összefüggő körök azonosítása.
3. Program analízis:
   • Függőségi gráfok komponenseinek azonosítása.

A Kosaraju-algoritmus egy hatékony és elegáns megoldás az irányított gráfok erősen összefüggő komponenseinek meghatározására. Egyszerűsége és hatékonysága miatt széles körben alkalmazzák gráfalgoritmusok területén.

• Kosaraju-algoritmus - Értelmező szótár (MEK)
• Kosaraju-algoritmus - Etimológiai szótár (UMIL)
• Kosaraju-algoritmus - Szótár.net (hu-hu)
• Kosaraju-algoritmus - DeepL (hu-de)
• Kosaraju-algoritmus - Яндекс (hu-ru)
• Kosaraju-algoritmus - Google (hu-en)
• Kosaraju-algoritmus - Helyesírási szótár (MTA)
• Kosaraju-algoritmus - Wikidata
• Kosaraju-algoritmus - Wikipédia (magyar)