数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Tarjan 算法求解强连通分量
Tarjan 算法用于查找有向图的强连通分量。它只需要一次深度优先搜索 (DFS) 遍历即可实现。
使用 DFS 遍历，我们可以找到森林的 DFS 树。从 DFS 树中，可以找到强连通分量。当找到这样的子树的根时，我们可以显示整个子树。该子树就是一个强连通分量。
输入和输出
Input: Adjacency matrix of the graph. 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 Output: The strongly connected components: 4 3 1 2 0
算法
findComponent(u, disc, low, stack, stackItemFlag)
输入：起始节点、发现时间、low 值。disc 存储顶点的发现时间，low 存储子树信息。stack 用于存储顶点，另一个标志数组用于跟踪哪个节点在 stack 中。
输出：显示强连通分量 (SCC)。
Begin time := 0 //the value of time will not be initialized for next function calls set disc[u] := time+1 and low[u] := time + 1 time := time + 1 push u into stack stackItemFalg[u] := true for all vertex v which is adjacent with u, do if v is not discovered, then fincComponent(v, disc, low, stack, stackItemFalg) low[u] = minimum of low[u] and low[v] else if stackItemFalg[v] is true, then low[u] := minimum of low[u] and disc[v] done poppedItem := 0 if low[u] = disc[u], then while u is not in the stack top, do poppedItem := top of stack display poppedItem stackItemFlag[poppedItem] := false pop item from stack done poppedItem := top of stack display poppedItem stackItemFlag[poppedItem] := false pop item from stack End
strongConComponent(graph)
输入：给定的图。
输出：所有强连通分量。
Begin initially set all items in the disc array to undiscovered for all elements in low to φ and mark no item is stored into the stack for all node i in the graph, do if disc[i] is undiscovered, then findComponent(i, disc, low, stack, stackItemFlag) End
示例
#include<iostream>
#include<stack>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 0, 1, 1, 0},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0}
};
int min(int a, int b) {
return (a<b)?a:b;
}
void findComponent(int u, int disc[], int low[], stack<int>&stk, bool stkItem[]) {
static int time = 0;
disc[u] = low[u] = ++time; //inilially discovery time and low value is 1
stk.push(u);
stkItem[u] = true; //flag as u in the stack
for(int v = 0; v<NODE; v++) {
if(graph[u][v]) {
if(disc[v] == -1) { //when v is not visited
findComponent(v, disc, low, stk, stkItem);
low[u] = min(low[u], low[v]);
} else if(stkItem[v]) //when v is in the stack, update low for u
low[u] = min(low[u], disc[v]);
}
}
int poppedItem = 0;
if(low[u] == disc[u]) {
while(stk.top() != u) {
poppedItem = stk.top();
cout << poppedItem << " ";
stkItem[poppedItem] = false; //mark as item is popped
stk.pop();
}
poppedItem = stk.top();
cout << poppedItem <<endl;
stkItem[poppedItem] = false;
stk.pop();
}
}
void strongConComponent() {
int disc[NODE], low[NODE];
bool stkItem[NODE];
stack<int> stk;
for(int i = 0; i<NODE; i++) { //initialize all elements
disc[i] = low[i] = -1;
stkItem[i] = false;
}
for(int i = 0; i<NODE; i++) //initialize all elements
if(disc[i] == -1)
findComponent(i, disc, low, stk, stkItem);
}
int main() {
strongConComponent();
}输出
4 3 1 2 0
更新于： 2020年6月16日
2K+ 次浏览
广告