Wikiszótár

Kosaraju-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈkoʃɒrɒjuɒlɡoritmuʃ]

Főnév

Kosaraju-algoritmus

  1. (matematika)

Kosaraju-algoritmus

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.


Erősen összefüggő komponens (SCC)

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   és   utak léteznek.


Algoritmus működése

Bemenet:

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

Kimenet:

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


Lépések

  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.


Pszeudokód

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

Időbonyolultság

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.


Példa Pythonban

from collections import defaultdict

def kosaraju(graph):
    # Első DFS
    def dfs1(v):
        visited.add(v)
        for neighbor in graph[v]:
            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[v]:
            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[src]:
                transposed[dest].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],
    1: [2, 3],
    2: [0],
    3: [4],
    4: [5],
    5: [3],
}

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

Kimenet: 

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

Példa C++-ban

#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[v] = true;
    for (int neighbor : graph[v]) {
        if (!visited[neighbor]) {
            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[v] = true;
    component.push_back(v);
    for (int neighbor : transposed_graph[v]) {
        if (!visited[neighbor]) {
            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[i]) {
            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[u]) {
            transposed_graph[v].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[v]) {
            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

Előnyök

  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ő.


Hátrányok

  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.


Alkalmazások

  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.


Összegzés

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.


Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Kosaraju-algoritmus&oldid=3479731”