Java数据结构之图的遍历

你的名字 2022-02-01 15:41 379阅读 0赞

# 核心思想 #

图的遍历指从图的任意一个顶点出发对图的每个顶点访问且仅访问一次的过程，因为图中可能存在回路，为了避免对一个顶点的重复访问可以增设一个辅助数组visited，初始化为0，一旦第i个顶点被访问，置visited\[i\]=1。因此，图的遍历需要考虑如下三点：

> 1.  指定遍历的第一个顶点。
> 2.  由于一个顶点和多个顶点相邻，需要在多个邻接顶点间确定访问次序。
> 3.  由于图中存在回路，必须对访问过的顶点做标记，防止出现重复访问同一顶点的情况。

## 广度优先搜索算法（BFS） ##

#### 核心思想 ####

BFS遵循“先被访问的顶点，其邻接点先被访问”的规则，因此可以引入队列。  
先将起始点加入队列中，以后每次从队列中删除一个数据元素，依次访问它的未被访问的邻接点，并将其插入到队列中，直到队列为空。

> 1.  建立标识数组visited\[n\]，并初始化为0，n为顶点个数
> 2.  将未访问顶点vi入队
> 3.  将队首元素顶点vi从队列中取出，依次访问它的未被访问的邻接点，并将其入队
> 4.  重复步骤3，直到队列为空
> 5.  改变i的值，跳到步骤2继续执行

#### 代码实现 ####

//导入包见参考类
    	import ch03.LinkQueue;
    	
    	/**
    	 * 广度优先搜索算法BFS（
    	 * @param g
    	 * @throws Exception
    	 */
    	public void BFSTraverse(IGraph g) throws Exception{
    		visited = new int[g.getVNum()];
    		for(int i=0;i<g.getVNum();i++) {
    			if(visited[i]==0)
    				BFS(g,i);
    		}
    	}
    	
    	public void BFS(IGraph g, int i) throws Exception{
    		visited[i] = 1;
    		System.out.println(g.getVex(i).toString()+"");
    		LinkQueue q = new LinkQueue();
    		q.offer(i);
    		while(!q.isEmpty()) {
    			int u = (int)q.poll();
    			for(int v = g.firstAdj(u);v>0;v=g.nextAdj(i, v)) {
    				if(visited[v] == 0) {
    					System.out.println(g.getVex(v).toString() + "");
    					visited[v] = 1;
    					q.offer(v);
    				}
    			}
    		}
    	}

#### 参考类 ####

> [ch03.LinkQueue][]

## 深度优先搜索算法（DFS） ##

#### 核心思想 ####

DFS类似于树的先序遍历，从一个顶点u为起始点访问其邻接点v0，再访问v0未被访问的邻接点v1，然后从v1出发继续进行类似的访问，直到所有的邻接点都被访问。然后后退到前一个被访问的顶点，看是否存在其他未被访问的顶点，若有再进行上述访问过程；若没有，则继续回退，直到图中所有的顶点都被访问为止。

> 1.  建立标识数组visited\[n\]，并初始化为0，n为顶点个数
> 2.  以未访问顶点vi为起始点访问其未访问的邻接点vj
> 3.  从vj出发，继续递归进行步骤2，直到所有邻接点均被访问
> 4.  改变i值，跳到步骤2继续进行

#### 代码实现 ####

/**
    	 * 深度优先搜索算法DFS（Depth_Frist_Search）
    	 * 从图中某个顶点v出发，访问次顶点，然后从v的未被访问的邻接点出发，深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。
    	 * 把第一个邻接点当做左孩子
    	 */     
    	public void DFSTraverser(IGraph g) throws Exception{
    		visited = new int[g.getVNum()];
    		for(int i=0;i<g.getVNum();i++) {
    			if(visited[i] == 0)
    				DFS(g,i);
    		}
    	}
    	
    	public void DFS(IGraph g, int i) throws Exception{
    		visited[i] = 1;
    		System.out.println(g.getVex(i).toString()+"");
    		for(int u=g.firstAdj(i);u>=0;u=g.nextAdj(i, u)) {
    			if(visited[u] ==0)
    				DFS(g,u);
    		}
    	}

将上述方法加入到[MGraph][]类中即可使用

[ch03.LinkQueue]: https://blog.csdn.net/weixin_44270248/article/details/90229970
[MGraph]: https://blog.csdn.net/weixin_44270248/article/details/90203474