Wikiszótár

Tarjan-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈtɒrjɒnɒlɡoritmuʃ]

Főnév

Tarjan-algoritmus

  1. (matematika, gráfelmélet, algoritmusok)

Tarjan-algoritmus

A Tarjan-algoritmus egy hatékony gráfelméleti algoritmus, amely a gráf erősen összefüggő komponenseinek (SCC - Strongly Connected Components) meghatározására szolgál. Az algoritmust Robert Tarjan dolgozta ki 1972-ben, és az erősen összefüggő komponenseket mély keresés (DFS) segítségével azonosítja. Az algoritmus időbonyolultsága (O(V + E)), ahol (V) a csúcsok, (E) az élek száma.


Fő ötlet

Egy irányított gráfban egy erősen összefüggő komponens olyan maximális csúcshalmaz, amelyben bármely két csúcs között létezik egy irányított út. A Tarjan-algoritmus egyetlen mélységi keresés (DFS) során azonosítja az összes ilyen komponenst, miközben egy verem segítségével nyomon követi a csúcsok elérhetőségi viszonyait.


Algoritmus működése

1. DFS és indexelés

  • Minden csúcsot egyedi index-szel látunk el a DFS látogatási sorrendje alapján.
  • Minden csúcs kap egy low-link értéket, amely azt jelzi, hogy az adott csúcsból legfeljebb milyen “alacsony” indexű csúcs érhető el a gráfban.

2. Veremhasználat

  • Az algoritmus egy vermet használ, hogy nyomon kövesse az aktuális DFS-hívásban szereplő csúcsokat.
  • Az erősen összefüggő komponensek csúcsait a veremről vesszük le.

3. Komponensek azonosítása

  • Ha egy csúcs saját maga a legkisebb elérési pontja ((low-link[u] = index[u])), akkor ez egy erősen összefüggő komponens gyökércsúcsa. Ekkor az algoritmus kiemeli az ehhez tartozó csúcsokat a veremből.

4. Rekurzív DFS

  • A mélységi keresés során rekurzívan dolgozza fel a csúcsok gyermekeit, frissítve az aktuális csúcs (low-link) értékét.


Pszeudokód

TarjanAlgorithm(G):
    index = 0
    stack = []
    indices = {}
    lowlink = {}
    on_stack = {}
    sccs = []

    function strongconnect(v):
        indices[v] = index
        lowlink[v] = index
        index += 1
        stack.append(v)
        on_stack[v] = True

        for w in G[v]:
            if w not in indices:  # Ha w még nincs meglátogatva
                strongconnect(w)
                lowlink[v] = min(lowlink[v], lowlink[w])
            elif on_stack[w]:  # Ha w már a vermen van
                lowlink[v] = min(lowlink[v], indices[w])

        if lowlink[v] == indices[v]:
            component = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                component.append(w)
                if w == v:
                    break
            sccs.append(component)

    for v in G:
        if v not in indices:
            strongconnect(v)

    return sccs

Példa

Bemenet:

Egy irányított gráf az alábbi élekkel: [ G = {0 , 1 , 2 , 1 , 3 , 4 , 5 , 6 , 6 , 7 } ]

Lépések:

  1. Az algoritmus elindítja a mélységi keresést a (0)-ból.
  2. A verem segítségével azonosítja az összes erősen összefüggő komponenst:
    • ([0, 1, 2])
    • ([3, 4, 5])
    • ([6, 7])

Kimenet:

[ SCCs = {[0, 1, 2], [3, 4, 5], [6, 7]} ]


Python implementáció

from collections import defaultdict

def tarjan_scc(graph):
    index = 0
    stack = []
    indices = {}
    lowlink = {}
    on_stack = {}
    sccs = []

    def strongconnect(v):
        nonlocal index
        indices[v] = index
        lowlink[v] = index
        index += 1
        stack.append(v)
        on_stack[v] = True

        for w in graph[v]:
            if w not in indices:
                strongconnect(w)
                lowlink[v] = min(lowlink[v], lowlink[w])
            elif on_stack[w]:
                lowlink[v] = min(lowlink[v], indices[w])

        if lowlink[v] == indices[v]:
            component = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                component.append(w)
                if w == v:
                    break
            sccs.append(component)

    for v in graph:
        if v not in indices:
            strongconnect(v)

    return sccs

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

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

Kimenet: 

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

C++ implementáció

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

using namespace std;

void strongconnect(int v, int& index, vector<int>& indices, vector<int>& lowlink, vector<bool>& on_stack, stack<int>& st, vector<vector<int>>& sccs, const unordered_map<int, vector<int>>& graph) {
    indices[v] = index;
    lowlink[v] = index;
    index++;
    st.push(v);
    on_stack[v] = true;

    for (int w : graph.at(v)) {
        if (indices[w] == -1) {
            strongconnect(w, index, indices, lowlink, on_stack, st, sccs, graph);
            lowlink[v] = min(lowlink[v], lowlink[w]);
        } else if (on_stack[w]) {
            lowlink[v] = min(lowlink[v], indices[w]);
        }
    }

    if (lowlink[v] == indices[v]) {
        vector<int> component;
        int w;
        do {
            w = st.top();
            st.pop();
            on_stack[w] = false;
            component.push_back(w);
        } while (w != v);
        sccs.push_back(component);
    }
}

vector<vector<int>> tarjan_scc(const unordered_map<int, vector<int>>& graph, int num_nodes) {
    vector<int> indices(num_nodes, -1);
    vector<int> lowlink(num_nodes, -1);
    vector<bool> on_stack(num_nodes, false);
    stack<int> st;
    vector<vector<int>> sccs;
    int index = 0;

    for (const auto& [v, _] : graph) {
        if (indices[v] == -1) {
            strongconnect(v, index, indices, lowlink, on_stack, st, sccs, graph);
        }
    }

    return sccs;
}

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

    vector<vector<int>> sccs = tarjan_scc(graph, 8);

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

    return 0;
}

Kimenet: 

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

Előnyök

  1. Hatékonyság:
    • Az algoritmus időbonyolultsága (O(V + E)), ami optimális a gráfok erősen összefüggő komponenseinek keresésére.
  2. Egyszerű implementáció:
    • Könnyen implementálható, még bonyolult gráfok esetén is.
  3. Direkt alkalmazás:
    • Közvetlenül alkalmazható különböző hálózatelemzési és optimalizálási feladatokban.


Hátrányok

  1. Mély rekurzió:
    • Nagyon mély gráfstruktúrák esetén a rekurzív megközelítés memóriaigényes lehet.
  2. Statikus gráf:
    • Dinamikusan változó gráfokhoz az algoritmust újra kell futtatni.


Alkalmazások

  1. Hálózatelemzés:
    • Weboldalak vagy szociális hálózatok összefüggő részeinek elemzése.
  2. Fordítóprogramok:
    • Függőségek feloldása.
  3. Áramkörök:
    • Elektromos áramkörök erősen összefüggő komponenseinek azonosítása.


Összegzés

A Tarjan-algoritmus egy hatékony és egyszerű módszer az irányított gráf erősen összefüggő komponenseinek meghatározására. Az (O(V + E)) időbonyolultságának és intuitív megközelítésének köszönhetően a modern számítástudomány egyik alapvető algoritmusa.


További információk

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