数据结构——图的遍历方法（Java代码实现）

偏执的太偏执、 2023-02-12 15:20 4阅读 0赞

所谓图的遍历，即是对结点的访问。-一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略: (1)深度优先遍历 (2)广度优先遍历

图的深度优先遍历介绍

深度优先遍历基本思想：图的深度优先搜素(Depth FirstSearch)：DFS

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

深度优先遍历算法步骤

1.  访问初始结点v。并标记结点v为已访问。
2.  查找结点v的第-一个邻按结点w.
3.  若w存在，则继续执行4，如果w不存在，则回到第1步， 将从v的下一个结点继续。
4.  若w未被访问，对w进行深度优先遍历递归(即把w当做另一个v，然后进行步骤123)。
5.  查找结点v的w邻按结点的下一个邻接结点，转到步骤3。

代码实现：在原先的代码基础上进行添加：[数据结构——图简介（java代码实现邻接矩阵）][java]  
添加变量数组用于记录，在构造方法当中进行初始化。

public boolean[] isVisited; // 记录被访问了的节点
    
    	public Graph(int n) { 
    		edges = new int[n][n];
    		vertexList = new ArrayList<String>(n);
    		num = 0;
    		isVisited = new boolean[n];
    	}

添加方法：

// 得到第一个邻接节点的下标
    	public int getFirstNode(int index) { 
    		for (int j = 0; j < vertexList.size(); j++) { 
    			if (edges[index][j] > 0) {  // 存在下一个节点
    				return j;
    			}
    		}
    		return -1;
    	}
    
    	// 根据前一个邻接节点的下标获取下一个邻接节点
    	public int getNextNode(int v1, int v2) { 
    		for (int j = v2 + 1; j < vertexList.size(); j++) { 
    			if (edges[v1][j] > 0) { 
    				return j;
    			}
    		}
    		return -1;
    	}
    
    	// 深度优先遍历
    	private void DFS(boolean[] isVisited, int i) { 
    		// 先进行访问i
    		System.out.print(getValue(i) + " -> ");
    		// 把这个节点设置为已访问
    		isVisited[i] = true;
    		// 查找第一个邻接节点
    		int w = getFirstNode(i);
    		while (w != -1) { 
    			if (!isVisited[w]) { // 节点还未被访问
    				DFS(isVisited, w);
    			}
    			// 已经被访问,查找下一个邻接 节点
    			w = getNextNode(i, w);
    		}
    	}
    
    	// 对DFS进行重载
    	public void DFS() { 
    		// 遍历所有节点进行DFS
    		for (int i = 0; i < nodeNum(); i++) { 
    			if (!isVisited[i]) { 
    				DFS(isVisited, i);
    			}
    		}
    	}

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]  
图的广度优先遍历介绍

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

广度优先遍历算法步骤

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。

使用代码实现广度优先遍历，添加对应的方法。

// 广度优先遍历
    	public void BFS(boolean[] isVisited, int i) { 
    		int u; // 队列的头节点
    		int w; // 邻接节点
    		LinkedList queue = new LinkedList(); // 使用队列记录访问顺序
    		System.out.print(getValue(i) + " -> ");
    		isVisited[i] = true;
    		queue.addLast(i);
    		while (!queue.isEmpty()) { 
    			// 取出队列头节点下标
    			u = (Integer) queue.removeFirst();
    			w = getFirstNode(u);
    			while (w != -1) { 
    				// 是否被访问过
    				if (!isVisited[w]) { 
    					System.out.print(getValue(w) + " -> ");
    					isVisited[w] = true;
    					// 入队列
    					queue.addLast(w);
    				}
    				w= getNextNode(u, w); //继续找下一个节点
    			}
    		}
    	}
    
    	public void BFS() { 
    		// 遍历所有节点进行DFS
    		for (int i = 0; i < nodeNum(); i++) { 
    			if (!isVisited[i]) { 
    				BFS(isVisited, i);
    			}
    		}
    	}

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]

[java]: https://blog.csdn.net/qq_44973159/article/details/106355167
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200526203735828.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020052620393345.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70