在很多情况下，我们需要遍历图，得到图的一些性质，例如，找出图中与指定的顶点相连的所有顶点，或者判定某 个顶点与指定顶点是否相通，是非常常见的需求。 有关图的搜索，最经典的算法有深度优先搜索和广度优先搜索，接下来我们分别讲解这两种搜索算法。

一、深度优先搜索

所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找子结点，然后找 兄弟结点。

很明显，在由于边是没有方向的，所以，如果4和5顶点相连，那么4会出现在5的相邻链表中，5也会出现在4的相 邻链表中，那么为了不对顶点进行重复搜索，应该要有相应的标记来表示当前顶点有没有搜索过，可以使用一个布 尔类型的数组 boolean[V] marked,索引代表顶点，值代表当前顶点是否已经搜索，如果已经搜索，标记为true， 如果没有搜索，标记为false；

API设计：

代码：

public class DepthFirstSearch { 
//索引代表顶点，值表示当前顶点是否已经被搜索 
private boolean[] marked; 
//记录有多少个顶点与s顶点相通 
private int count; 
//构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相邻顶点 
public DepthFirstSearch(Graph G,int s){ 
//创建一个和图的顶点数一样大小的布尔数组 marked = new boolean[G.V()]; 
//搜索G图中与顶点s相同的所有顶点 dfs(G,s); }
//使用深度优先搜索找出G图中v顶点的所有相邻顶点 
private void dfs(Graph G, int v){ //把当前顶点标记为已搜索 marked[v]=true; 
//遍历v顶点的邻接表，得到每一个顶点w for (Integer w : G.adj(v)){ 
//如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点 
if (!marked[w]){ dfs(G,w); } }//相通的顶点数量+1 count++; }//判断w顶点与s顶点是否相通 
public boolean marked(int w){ return marked[w]; }//获取与顶点s相通的所有顶点的总数 
public int count(){ return count; } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二、广度优先搜索

所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后 找子结点。

API设计：

代码：

public class BreadthFirstSearch { 
//索引代表顶点，值表示当前顶点是否已经被搜索 
private boolean[] marked; 
//记录有多少个顶点与s顶点相通 
private int count; 
//用来存储待搜索邻接表的点 private Queue waitSearch; 12345678
//构造广度优先搜索对象，使用广度优先搜索找出G图中s顶点的所有相邻顶点 
public BreadthFirstSearch(Graph G, int s) { 
//创建一个和图的顶点数一样大小的布尔数组 
marked = new boolean[G.V()]; 
//初始化待搜索顶点的队列 
waitSearch = new Queue<Integer>(); 
//搜索G图中与顶点s相同的所有顶点 
dfs(G, s); }
//使用广度优先搜索找出G图中v顶点的所有相邻顶点 
private void dfs(Graph G, int v) { 
//把当前顶点v标记为已搜索 
marked[v]=true; 
//把当前顶点v放入到队列中，等待搜索它的邻接表 
waitSearch.enqueue(v); 
//使用while循环从队列中拿出待搜索的顶点wait，进行搜索邻接表 
while(!waitSearch.isEmpty()){ Integer wait = waitSearch.dequeue(); 
//遍历wait顶点的邻接表，得到每一个顶点w for (Integer w : G.adj(wait)) { //如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点 if (!marked[w]) { dfs(G, w); } } }//相通的顶点数量+1 count++; }//判断w顶点与s顶点是否相通 public boolean marked(int w) { return marked[w]; }//获取与顶点s相通的所有顶点的总数 public int count() { return count; } }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三、案例-畅通工程续1

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。目前的道路状况，9号城市和10号城市是否相通？9号城市和8号城市是否相通？

在我们的测试数据文件夹中有一个trffiffiffic_project.txt文件，它就是诚征道路统计表，下面是对数据的解释：

总共有20个城市，目前已经修改好了7条道路，问9号城市和10号城市是否相通？9号城市和8号城市是否相通？

解题思路：

1.创建一个图Graph对象，表示城市；

2.分别调用

addEdge(0,1),addEdge(6,9),addEdge(3,8),addEdge(5,11),addEdge(2,12),addEdge(6,10),addEdge(4,8)，表示已经修建好的道路把对应的城市连接起来；

3.通过Graph对象和顶点9，构建DepthFirstSearch对象或BreadthFirstSearch对象；

4.调用搜索对象的marked(10)方法和marked(8)方法，即可得到9和城市与10号城市以及9号城市与8号城市是否相通。

代码：

本文是Java数据结构与算法教程的课件文档，获取学习最新全套java数据结构算法，左神算法大厂LeetCode刷题教程请点击即可获取。