基于Java,无向图采用邻接表存储结构,编写算法输出图中各连通分量的顶点序列
时间: 2024-01-16 18:05:11 浏览: 94
以下是基于Java语言的实现,实现了输出无向图中各连通分量的顶点序列。
```java
import java.util.*;
public class Main {
private static List<List<Integer>> res = new ArrayList<>(); // 存储所有连通分量
public static void dfs(List<Integer>[] adjList, boolean[] visited, int u, List<Integer> path) {
visited[u] = true;
path.add(u);
// 遍历u的所有邻接点
for(int v : adjList[u]) {
if(!visited[v]) {
dfs(adjList, visited, v, path);
}
}
}
public static List<List<Integer>> findConnectedComponents(List<Integer>[] adjList) {
int n = adjList.length - 1;
boolean[] visited = new boolean[n+1];
// 遍历所有未访问过的顶点,找出所有连通分量
for(int i=1; i<=n; i++) {
if(!visited[i]) {
List<Integer> path = new ArrayList<>();
dfs(adjList, visited, i, path);
res.add(path);
}
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
List<Integer>[] adjList = new ArrayList[n+1];
// 初始化邻接表
for(int i=1; i<=n; i++) {
adjList[i] = new ArrayList<Integer>();
}
// 读入m条边,建立邻接表
for(int i=1; i<=m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
adjList[u].add(v);
adjList[v].add(u);
}
// 输出各连通分量的顶点序列
List<List<Integer>> res = findConnectedComponents(adjList);
for(List<Integer> path : res) {
System.out.println(path);
}
}
}
```
在上面的代码中,我们使用了深度优先搜索(DFS)来遍历所有连通的顶点,并将它们存储到一个列表中。在主函数中,我们读入无向图的边,建立邻接表,并调用`findConnectedComponents`函数找出所有连通分量。最后,我们输出所有连通分量的顶点序列。
阅读全文