//邻接表实现图的广搜和深搜(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
源码:
分享到:
相关推荐
本文将深入探讨如何使用邻接矩阵来实现图的广度优先搜索(BFS)和深度优先搜索(DFS),并提供一个Java模板。 首先,我们需要理解邻接矩阵的概念。邻接矩阵是一个二维数组,其中的元素表示图中节点之间的连接。如果...
在这个课程设计中,我们将深入探讨“图的遍历”这一主题,它包括了如何使用邻接矩阵和邻接链表来构建图,以及如何通过深度优先搜索(DFS)和广度优先搜索(BFS)遍历图,最后还将学习Prim算法和Kruskal算法来生成...
本项目提供了一个C++实现的邻接表,能够处理有向图和无向图,并且使用了类模板来增强代码的通用性。以下是对这个项目的详细解释: 首先,邻接表是一种存储图的有效方式,尤其适用于稀疏图(即边的数量远小于顶点...
在计算机科学中,图是一种数据结构,用于...在Java中,我们可以利用HashMap、ArrayList和LinkedList等内置数据结构轻松实现邻接表。理解并熟练运用邻接表对于解决实际问题,如路径查找、最短路径计算等,具有重要意义。
本文将深入探讨如何使用Java实现图的邻接矩阵以及如何在该数据结构上执行广度优先搜索(BFS)。 **邻接矩阵** 邻接矩阵是一种二维数组,它用来表示图中顶点之间的连接。如果图是无向的,邻接矩阵是对称的;如果图...
对于诸如图的着色问题等高级应用,邻接表提供了一种清晰且直观的解决方案,有助于简化算法设计和实现过程。掌握图的邻接表存储和操作,对于任何从事计算机科学或相关领域的专业人士来说都是必不可少的技能之一。
这个应用程序演示了如何使用Java实现图的邻接矩阵和深度优先搜索的基本概念。 总结一下,这个话题涵盖了以下关键知识点: 1. 图的邻接矩阵表示法:使用二维数组存储图中节点的关系。 2. Java中实现邻接矩阵:创建一...
在编程中,有多种方法来存储图,其中两种常用的方法是邻接矩阵和邻接表。这两种方法各有优缺点,适用于不同类型的图和不同的操作需求。 邻接矩阵是一种二维数组,其中的每个元素代表两个顶点之间是否存在边。如果...
实现图的深度和广度优先搜索 /* 邻接表的结点类型 */ typedef struct arc {int adjvex; struct arc *next;}ArcNode; typedef struct VexNode {int vertex; ArcNode *firstarc; }VerNode; typedef VerNode ...
本文将详细探讨图的两种常见存储方式——邻接矩阵和邻接表,以及基于这两种数据结构的深度搜索(DFS)、广度搜索(BFS)和Dijkstra最短路径算法。 首先,邻接矩阵是一种二维数组,用于表示图中所有节点之间的连接...
本文将深入探讨如何使用邻接矩阵和邻接表这两种方法来创建图,并实现深度优先搜索(DFS)和广度优先搜索(BFS)算法。 首先,我们来看邻接矩阵。邻接矩阵是一个二维数组,其中的元素代表图中节点之间的连接状态。...
在编译原理中,自动机是一种重要的概念,用于识别和处理特定的语言或模式。自动机主要有两种类型:非确定性有限...通过邻接表这一数据结构,可以有效地组织和操作DFA的状态转移关系,从而实现高效的自动机识别功能。
文件`LGraph`可能是实现这些功能的源代码文件,包含了定义数据结构和实现相关操作的函数。通过阅读和理解这个文件,可以深入学习邻接链表法实现图的细节。这种实现方式适合处理稀疏图(边的数量远小于节点数量的平方...
用邻接表实现无向图的存储结构,并进行深度优先搜索及广度优先搜索。
这篇文章介绍了使用邻接表表示的图的深度优先搜索和广度优先搜索程序,旨在帮助读者理解图的深度优先搜索和广度优先搜索算法的实现。 首先,文章定义了图的邻接表表示的数据结构,包括顶点结点 vertexnode 和边结点...
在这个Java程序中,我们将探讨如何使用邻接表来实现图的深度优先遍历(DFS)和广度优先遍历(BFS)。邻接表是图数据结构的一种有效实现方式,尤其对于稀疏图(边的数量远小于节点数量的平方)来说,它比邻接矩阵更加...
本篇将详细介绍有向图的邻接链表实现,以及如何通过头文件`LinkedGraphDirected.h`进行操作。 有向图是由顶点(或节点)和边组成的集合,边具有方向性,即每个边都有一个起点和终点。邻接链表是一种常用的有向图...
图的邻接表实现,用邻接矩阵实现了图,基本操作,主要算法
图是数据结构中的一种重要...综上所述,`createadjlist.cpp`和`creatematix.cpp`文件分别实现了图的邻接表和邻接矩阵存储,为理解和操作图提供基础。通过阅读和理解这些代码,你可以更好地掌握这两种重要的图数据结构。