Trajan & SCC

Tarjan算法介绍

算法分析

Tarjan算法用于在有向图中寻找强连通分量（SCC）。强连通分量是指在一个子图中，任意两个顶点之间都存在路径。Tarjan算法基于深度优先搜索（DFS），其时间复杂度为\(O(V + E)\)，其中\(V\)是顶点数，\(E\)是边数。

算法的核心思想是通过DFS遍历图，并使用一个栈来跟踪访问路径。每个节点都有一个唯一的索引和一个低链接值，低链接值表示该节点或其子节点能够访问的最早节点。

伪代码

以下是Tarjan算法的伪代码：

function tarjanSCC(graph):
    index = 0
    stack = []
    for each vertex v in graph:
        if v.index is undefined:
            strongConnect(v)

function strongConnect(v):
    v.index = index
    v.lowlink = index
    index += 1
    stack.push(v)
    v.onStack = true

    for each (v, w) in v.edges:
        if w.index is undefined:
            strongConnect(w)
            v.lowlink = min(v.lowlink, w.lowlink)
        else if w.onStack:
            v.lowlink = min(v.lowlink, w.index)

    if v.lowlink == v.index:
        start a new SCC
        repeat
            w = stack.pop()
            w.onStack = false
            add w to current SCC
        until w == v

C++代码

以下是Tarjan算法的C++实现：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Graph {
    int V;
    vector<int> *adj;
    void SCCUtil(int u, int disc[], int low[], stack<int> *st, bool stackMember[]);

public:
    Graph(int V);
    void addEdge(int v, int w);
    void SCC();
};

Graph::Graph(int V) {
    this->V = V;
    adj = new vector<int>[V];
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

void Graph::SCCUtil(int u, int disc[], int low[], stack<int> *st, bool stackMember[]) {
    static int time = 0;
    disc[u] = low[u] = ++time;
    st->push(u);
    stackMember[u] = true;

    for (int i : adj[u]) {
        if (disc[i] == -1) {
            SCCUtil(i, disc, low, st, stackMember);
            low[u] = min(low[u], low[i]);
        } else if (stackMember[i]) {
            low[u] = min(low[u], disc[i]);
        }
    }

    int w = 0;
    if (low[u] == disc[u]) {
        while (st->top() != u) {
            w = st->top();
            cout << w << " ";
            stackMember[w] = false;
            st->pop();
        }
        w = st->top();
        cout << w << "\n";
        stackMember[w] = false;
        st->pop();
    }
}

void Graph::SCC() {
    int *disc = new int[V];
    int *low = new int[V];
    bool *stackMember = new bool[V];
    stack<int> *st = new stack<int>();

    for (int i = 0; i < V; i++) {
        disc[i] = -1;
        low[i] = -1;
        stackMember[i] = false;
    }

    for (int i = 0; i < V; i++) {
        if (disc[i] == -1) {
            SCCUtil(i, disc, low, st, stackMember);
        }
    }
}

int main() {
    Graph g(5);
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(2, 1);
    g.addEdge(0, 3);
    g.addEdge(3, 4);

    cout << "Strongly Connected Components in the given graph are:\n";
    g.SCC();

    return 0;
}

以上代码定义了一个图类 Graph，并实现了Tarjan算法来寻找图中的强连通分量。Graph类包含添加边的方法 addEdge 和执行Tarjan算法的方法 SCC。SCCUtil 是一个辅助函数，用于递归地执行深度优先搜索并计算每个节点的 disc 和 low 值。