在很多情况下，我们需要遍历图，得到图的一些性质，例如，找出图中与指定的顶点相连的所有顶点，或者判定某 个顶点与指定顶点是否相通，是非常常见的需求。 有关图的搜索，最经典的算法有深度优先搜索和广度优先搜索，接下来我们分别讲解这两种搜索算法。
一、深度优先搜索所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找子结点，然后找 兄弟结点。
很明显，在由于边是没有方向的，所以，如果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; } }
二、广度优先搜索
所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后 找子结点。
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();
//搜索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
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。目前的道路状况，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刷题教程请点击即可获取。
