图处理算法-Kosaraju's-算法

Kosaraju 算法实现

1.用c++写了算法课的作业，计算了875714个顶点的有向图，计算了前5个最大连通分量的个数，用了两次DFS算法。
2.用c++开辟大数组容易出segment fault，后来改用堆开辟。图的邻接表用了链表表示。
VertexNode* adjList = new VertexNode[875714];
3.Kosaraju算法流程不在此详述。

深度优先搜索

1递归实现

伪代码如下：
输入：有向图: $G = (V, E)$ ，邻接链表表示，和某个顶点 $v_{i}$ ：
1. 将顶点 $v_{i}$ 标记为已经访问。
2. 对于每条边 $(i, j) \in G 进行遍历$ :
{
如果存在某个顶点 $v_{j}$ 未被访问,则对顶点 $v_{j}$ 进行访问：
DFS(G,j)
}
代码如下：
图处理算法-Kosaraju's-算法

2.非递归实现

非递归实现要用到栈。
输入：有向图: $G = (V, E)$ ，邻接链表表示，和某个顶点 $v_{i}$ .
1.栈初始化，将顶点 $v_{i}$ 入栈，并标记为已访问。
2.while(栈非空)
x = 栈顶元素
a.对于每条边 $(x, j) \in G 进行遍历$ :
if.如果存在某个顶点 $v_{j}$ 未被访问：
{
.将 $v_{j}$ 标记为已访问
.将顶点 $v_{j}$ 入栈。
break;
}
else
X出栈.
代码如下：
图处理算法-Kosaraju's-算法