强连通分量算法的典型案例,用Java语言实现
时间: 2024-03-16 14:46:35 浏览: 35
强连通分量算法的典型案例是在有向图中寻找强连通分量。强连通分量是指在一个有向图中,每个节点都可以到达其他节点的一组节点。
下面是一个用Java语言实现强连通分量算法的示例代码:
```
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class StronglyConnectedComponents {
private int V; // 节点数
private List<Integer>[] adj; // 邻接表
public StronglyConnectedComponents(int V) {
this.V = V;
adj = new ArrayList[V];
for (int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
// 添加边
public void addEdge(int u, int v) {
adj[u].add(v);
}
// 逆转图
public StronglyConnectedComponents reverse() {
StronglyConnectedComponents reverseGraph = new StronglyConnectedComponents(V);
for (int i = 0; i < V; i++) {
for (int j : adj[i]) {
reverseGraph.addEdge(j, i);
}
}
return reverseGraph;
}
// 获取强连通分量
public List<List<Integer>> getSCCs() {
List<List<Integer>> sccs = new ArrayList<>();
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();
// 第一遍 DFS
for (int i = 0; i < V; i++) {
if (!visited[i]) {
dfs(i, visited, stack);
}
}
// 逆序后的图
StronglyConnectedComponents reverseGraph = reverse();
// 第二遍 DFS
visited = new boolean[V];
while (!stack.isEmpty()) {
int v = stack.pop();
if (!visited[v]) {
List<Integer> scc = new ArrayList<>();
reverseGraph.dfs(v, visited, scc);
sccs.add(scc);
}
}
return sccs;
}
// DFS
private void dfs(int v, boolean[] visited, List<Integer> list) {
visited[v] = true;
for (int i : adj[v]) {
if (!visited[i]) {
dfs(i, visited, list);
}
}
list.add(v);
}
// DFS
private void dfs(int v, boolean[] visited, Stack<Integer> stack) {
visited[v] = true;
for (int i : adj[v]) {
if (!visited[i]) {
dfs(i, visited, stack);
}
}
stack.push(v);
}
public static void main(String[] args) {
StronglyConnectedComponents graph = new StronglyConnectedComponents(5);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(1, 3);
graph.addEdge(3, 4);
List<List<Integer>> sccs = graph.getSCCs();
System.out.println(sccs);
}
}
```
以上代码实现了一个基于DFS算法的强连通分量算法。在`main`函数中,我们创建了一个有向图,并寻找其中的强连通分量。输出结果为:
```
[[4], [3], [0, 1, 2]]
```
其中,`[4]`和`[3]`分别表示有向图中的两个孤立点,`[0, 1, 2]`表示一个强连通分量。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)