图的深度优先搜索以及广度优先搜索

一、基本概念1. 图的深度优先搜索（Depth First Search）2. 图的广度优先搜索（Board First Search） 二、基本思路1. 深度优先遍历实现步骤：2. 广度优先遍历实现步骤： 三、代码实现

一、基本概念

1. 图的深度优先搜索（Depth First Search）

深度优先遍历，从初始访问节点出发，初始访问节点可能有多个邻接节点，深度优先遍历的策略就是首先访问第一个邻接节点，然后再以这个被访问的节点作为初始节点，访问它的第一个邻接节点，即每次都在访问完当前节点后首先访问当前节点的第一个邻接节点。这样的访问策略是优先往纵向挖掘深入，而不是对一个节点的所有邻接节点进行横向访问。深度优先搜索是一个递归的过程。

2. 图的广度优先搜索（Board First Search）

图的广度优先搜索类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的节点的顺序，以便按照这个顺序来访问这些节点的邻接节点。

二、基本思路

1. 深度优先遍历实现步骤：

1. 访问初始节点，并标记节点v为已访问。 2. 查找节点v的下一个邻接节点w。 3. 若w存在，则继续下一步，否则回到1，将从v的下一个节点继续。 4. 若w未被访问，对w进行深度优先遍历（把w当作初始节点）。 5. 查找节点v的邻接节点w的下一个邻接节点，回到3。

以节点A,B,C,D,E为例：

我们以A为初始节点，首先访问A并标记A为已访问[A]A的下一个邻接节点B存在，且并未被访问，所以再以B节点出发[A,B]B的下一个邻接节点C存在，且并未被访问，所以再以C节点出发[A,B,C]C的邻接节点A，B都已经被访问过了，所以再以B节点出发，查找下一个邻接节点，即以D出发[A,B,C.D]D的下一个邻接节点不存在，所以再以B节点出发，查找下一个邻接节点，即以E出发[A,B,C.D,E]E的下一个邻接节点不存在，所以再以B节点出发，查找下一个邻接节点，下一个邻接节点并不存在，就再以A节点出发，查找下一个节点[A,B,C.D,E]A的邻接节点B，C都已经访问过了，所以遍历结束。[A,B,C.D,E]

2. 广度优先遍历实现步骤：

1. 访问初始节点v并标记节点v已访问。 2. 节点v加入队列。 3. 当队列非空，则继续进行，否则结束遍历。 4. 出队列，得到队头节点u。 5. 查找节点u的第一个邻接节点w。 6. 若节点u的邻接节点w不存在，则回到步骤3，否则继续进行 6.1. 若w未被访问，则访问节点w并标记已访问。 6.2 节点w入队列。 6.3 查找节点u的继w邻接节点后的下一个邻接节点w，转到步骤6

以节点A,B,C,D,E为例：

以A节点为初始节点，首先访问A节点并标记A节点已经访问。[A]节点A加入队列，队列中元素：（A)此时队列非空，所以所以队头元素A出队列，并查找其邻接节点，即从B出发。B节点存在，且并未被访问，所以访问B节点，并标记为已访问。[A,B]将节点B加入队列，队列中元素：（B)查找节点A的下一个邻接节点，即从C出发。C节点存在且未被访问，所以访问C节点，并标记为已访问。[A,B,C]将将节点B加入队列，队列中元素：（B,C)查找节点A的下一个邻接节点，并不存在。此时队列非空，所以队头元素B出队列，并查找其邻接节点，即从A出发。队列中元素：（C)节点A已被访问，所以查找节点B的下一个邻接节点，即从C出发。节点C已被访问，所以查找节点B的下一个邻接节点，即从D出发。D节点存在，且并未被访问，所以访问D节点，并标记为已访问。[A,B,C,D]节点D入队列，队列中元素：（C,D)查找B的下一个邻接节点，即从E出发。E节点存在，且并未被访问，所以访问E节点，并标记为已访问。[A,B,C,D,E]节点E入队列，队列中元素：（C,D,E)查找节点B的下一个邻接节点，并不存在。此时队列非空，所以队头元素C出队列，并查找其邻接节点，即从A出发。队列中元素：（D,E)节点A已被访问，所以查找节点C的下一个邻接节点，即从B出发。节点B已被访问，所以查找节点C的下一个邻接节点，并不存在。此时队列非空，所以队头元素D出队列，并查找其邻接节点。队列中元素：（E)查找节点D的下一个邻接节点，并不存在。此时队列非空，所以队头元素E出队列，并查找其邻接节点。()查找节点E的邻接节点，并不存在。此时队列为空，遍历结束。

三、代码实现

1.创建图类并定义相关方法

class Graph { private ArrayList<String> vertexList;//存储顶点 private int[][] edges;//存储对应邻接矩阵 private int numOfEdges;//存储边的数目 private boolean[] isVisited; public Graph(int n) { edges = new int[n][n]; vertexList = new ArrayList<>(n); numOfEdges = 0; isVisited = new boolean[n]; } //得到第一个邻接节点的下标w public int getFirstNeighbor(int index) { for (int i = 0; i < vertexList.size(); i++) { if (edges[index][i] > 0) { return i; } } return -1; } //根据前一个邻接节点的下标来获取下一个邻接节点 public int getNextNeighbor(int v1, int v2) { for (int i = v2+1; i < vertexList.size(); i++) { if (edges[v1][i] > 0) { return i; } } return -1; } //对一个节点进行广度优先遍历算法 private void bfs(boolean[] isVisited, int i) { int u;//队列的头节点对应的下标 int w;//邻接节点w LinkedList queue = new LinkedList();//队列，记录访问节点的顺序 System.out.print(getValueByIndex(i) + "->");//访问节点并输出信息 isVisited[i] = true;//将节点设置为已经访问 queue.addLast(i); while (!queue.isEmpty()) { //取出队列的头节点下标 u = (Integer) queue.removeFirst(); w = getFirstNeighbor(u); while (w != -1) { if (!isVisited[w]) { System.out.print(getValueByIndex(w) + "->"); isVisited[w] = true; queue.addLast(w); } w = getNextNeighbor(u, w); } } } //重载bfs public void bfs() { for (int i = 0; i < vertexList.size(); i++) { if (!isVisited[i]) { bfs(isVisited,i); } } } //深度优先遍历算法 private void dfs(boolean[] isVisited, int i) { //首先访问该节点，并输出 System.out.print(getValueByIndex(i) + "->"); //将节点设置为已经访问 isVisited[i] = true; //查看节点i的第一个邻接节点W int w = getFirstNeighbor(i); while (w != -1) { if (!isVisited[w]) { dfs(isVisited,w); } w = getNextNeighbor(i, w); } } //重载深度优先遍历算法 public void dfs() { for (int i = 0; i < getNumofVertex(); i++) { if (!isVisited[i]) { dfs(isVisited,i); } } } //插入节点 public void insertVertex(String vertex) { vertexList.add(vertex); } //添加边 public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; } //返回顶点个数 public int getNumofVertex() { return vertexList.size(); } //返回节点i对应的数据 public String getValueByIndex(int i) { return vertexList.get(i); } //返回v1和v2的权值 public int getWeight(int v1, int v2) { return edges[v1][v2]; } //得到图对应的邻接矩阵 public void showGraph() { for (int[] link : edges) { System.out.println(Arrays.toString(link)); } } //返回边的个数 public int getNumOfEdges() { return numOfEdges; } }

2.写一个简单的Demo进行测试

public class GraphDemo { public static void main(String[] args) { int n = 5; String[] vertexs = {"A", "B", "C", "D", "E"}; Graph graph = new Graph(5); for (String vertex : vertexs) { graph.insertVertex(vertex); } graph.insertEdge(0,1,1); graph.insertEdge(0,2,1); graph.insertEdge(1,2,1); graph.insertEdge(1,3,1); graph.insertEdge(1,4,1); graph.showGraph(); System.out.println("深度遍历"); graph.dfs(); // System.out.println("广度遍历"); // graph.bfs(); } }

测试结果：这里我们把标志访问的数组初始化放到构造器里进行了，所以这里深度优先和广度优先遍历是使用了同一个数组，所以需要分开测试。如果需要同时使用，也可以在具体的方法里对标志访问的数组进行初始化。