//邻接表实现图的广搜和深搜(java模板)
import java.util.*;
public class GraphSearch{
private int n; //图的顶点数,顶点为0,1,2,,,,n-1
private List<ArrayList<Integer>> G;// 邻接表实现图。
private boolean[] visited;//判断顶点是否被访问过
public GraphSearch(int n,List<ArrayList<Integer>> G){
this.n=n;
this.G=G;
visited = new boolean[n];
}
public static void main(String[] args) {
int n,m;
List<ArrayList<Integer>> G;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
G = new ArrayList<ArrayList<Integer>>();
for(int i = 0;i<n;i++)
G.add(new ArrayList<Integer>());//初始化邻接表
for(int i=0;i<m;i++) {
int u = sc.nextInt();
int v = sc.nextInt();
if(!G.get(u).contains(v)) {// 避免重边的情况比如a b可能出现两次的情况
G.get(u).add(v);
}
//对于无向图
if(!G.get(v).contains(u)) {
G.get(v).add(u);
}
}
GraphSearch ma=new GraphSearch(n,G);
//ma.dfs(0);
ma.bfs(0);
}
// 深搜
private void dfs(int v) {
visited[v] = true;
System.out.print(v+" ");
for (int i = 0; i <G.get(v).size(); i++) {
//递归调用搜索没有被访问过的当前节点的下一个节点(邻接点)
int k=G.get(v).get(i);
if (!visited[k])
dfs(k);
}
}
//广搜
private void bfs(int v) {
//队列用来保存被访问节点的分支节点(邻接点)
Queue<Integer> que = new LinkedList<Integer>();
que.offer(v);
while (!que.isEmpty()) {
v = que.poll();
System.out.print(v+" ");
visited[v] = true;
//将被访问节点的分支节点(邻接点)加入到队列中
for (int i = 0; i <G.get(v).size(); i++) {
int k=G.get(v).get(i);
if (!visited[k]){
que.add(k);
visited[k] = true;
}
}
}
}
}
运行:
C:\ex>java GraphSearch
6
10
0 1
0 2
0 3
1 2
1 4
2 4
2 5
2 3
3 5
4 5
0 1 2 3 4 5
源码:
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1745423
这是我的课程设计,题为《图的遍历》,包括利用邻接矩阵、邻接链表建图,利用深度优先和广度优先遍历图,以及利用prim和克鲁斯卡尔算法生成最小生成树。里面注解详细!
图的邻接矩阵和邻接表实现, 深度搜索, 广度搜索, Dijstra最短路径
实现图的深度和广度优先搜索 /* 邻接表的结点类型 */ typedef struct arc {int adjvex; struct arc *next;}ArcNode; typedef struct VexNode {int vertex; ArcNode *firstarc; }VerNode; typedef VerNode ...
用邻接表实现无向图的存储结构,并进行深度优先搜索及广度优先搜索。
C++实现图的邻接表,利用了类模板,可以构建有向图和无向图,包含链表、图的ADT,里面附有说明文档,详细说明了主程序的测试方式。
图的邻接表实现,用邻接矩阵实现了图,基本操作,主要算法
有向图的邻接链表实现 头文件 模板 包含插入/删除节点/边等功能
NULL 博文链接:https://128kj.iteye.com/blog/1663164
邻接表表示的图的深度优先搜索和广度优先搜索程序
(1) 基于邻接表的图的构建功能 (2) 标准Dijkstra算法 (3) 有向图的强连通算法 Environment: Eclipse 3.4 + JDK 1.6 注:目前只实现了以上三个功能,但由于各功能都基于模块化分解的思想实现,所以加入新功能会比较...
用邻接表实现图的数据结构,链表方式实现,win32+vs2013
邻接链表实现图的操作,具体操如下: 1. 创建图; 2. 销毁图; 3. 清空图; 4. 加入边; 5. 删除边; 6. 获取权; 7. 获取结点的度; 8. 获取图的结点数; 9. 获取图的边数。
分别以邻接矩阵和邻接表的方式实现图的深度优先搜索、广度优先搜索
NULL 博文链接:https://128kj.iteye.com/blog/1663043
领会图的两种主要存储结构、图基本运算算法和两种遍历算法设计内容:编写一个程序,设计带权图的邻接矩阵与邻接表的创建和输出运算,并在此基础上设计一个主程序完成如下功能:(1)建立如图所示的有向图G的邻接矩阵...
采用邻接表存储图,,输出深度优先搜索序列和广度优先序列。
Dijkstra算法C++邻接表实现,用邻接表存图,还有记录路径。
《数据结构与算法(C++版)》先关 邻接表表示的图的广度优先遍历的动画演示