数据结构之无向图的遍历

博主： admin123
发布时间：2019 年 11 月 18 日
3356 次浏览
暂无评论
加载中
1671字数
分类：学习笔记

欢迎移步博主CSDN：[CSDN博客](https://blog.csdn.net/weixin_42327790/article/details/103120803)

# 无向图的两种遍历算法的实现
## 简介
图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为

$$
G = (V,E)
$$

如果图的任意两个顶点之间的边都是无向边，则称该图为**无向图**,否则称该图为**有向图**。

## 图的两种遍历算法思想
* 深度优先遍历算法思想
 （1）访问顶点v；
 （2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
 （3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到
* 广度优先遍历算法思想
 （1）访问顶点v；
 （2）依次访问v的各个未被访问的邻接点v1，v2，v3......
 （3）分别从v1，v2，v3......出发依次访问它们未被访问的邻接点，并使先被访问顶点的邻接点先于后被访问顶点的邻接点被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。

## 采用邻接矩阵存储
图的邻接矩阵存储也称为数组表示法，其方法是用一个以为数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间临界关系的二维数组称为邻接矩阵。

---
以下面这个无向图为例进行实现
![31.jpg](/usr/uploads/2019/11/1225897599.jpg)

* 该无向图的`DFS`访问顺序：V0->V1->V4->V5->V2->V3
* 该无向图的`BFS`访问顺序：V0->V1->V2->V3->V4->V5

为了省时间（~~其实是自己懒~~ ），此处省略邻接矩阵的构造过程，采用手动写入边集和点集构建该无向图。
```java
		//手动构造图的点集和边集
        //点集
        int[] vector = {
                0,1,2,3,4,5
        };
        //边集
        int[][] arc ={
                {0,1,1,1,1,0},
                {1,0,0,0,1,0},
                {1,0,0,0,1,0},
                {1,0,0,0,0,0},
                {1,1,1,0,0,1},
                {0,0,0,0,1,1}
        };
        //记录是否访问
        int[] visited = {
                0,0,0,0,0,0
        };
```
### 深度优先遍历（递归实现）
```java
 	//图的深搜DFS,递归
    public static void DFS(int[] vector, int[] visited, int[][] arc,int i){
        //访问结点并标记
        System.out.println(vector[i]);
        visited[i]=1;
        for (int j = 0;j<vector.length; ++j){
            if (visited[j]==0 && arc[i][j]==1)
                DFS(vector,visited,arc,j);
        }
    }

```

### 深度优先遍历 （非递归实现）
```java
//图的深搜DFS ,非递归
    public static void DFS(int[] vector, int[] visited, int[][] arc){
        //访问第一个顶点并入栈
        System.out.println(vector[0]);
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);
        visited[0] = 1;
        while(!stack.isEmpty()){
            //获取栈顶元素
            int x = stack.peek();
            //标志位
            boolean flag = false;
            for (int i = 0; i<vector.length;++i){
                if (visited[i]==0 && arc[x][i]==1){
                    System.out.println(vector[i]);
                    //入栈
                    stack.push(i);
                    //更改访问位,标志位
                    visited[i] = 1;
                    flag = true;
                    break;
                }
            }
            //出栈
            if (!flag)
                stack.pop();
        }
    }

```

### 广度优先遍历
```java
//图的广搜BFS,非递归
    public static void BFS(int[] vector, int[] visited, int[][] arc){
        Queue<Integer> queue = new LinkedList<Integer>();
        //第一个顶点入队
        queue.offer(0);
        while (!queue.isEmpty()){
            //出队
            int x = queue.poll();
            //访问结点并标记
            System.out.println(vector[x]);
            visited[x] = 1;
            //寻找连通的结点并入队
            for (int i = 0; i<vector.length;++i){
                if (visited[i]==0 && arc[x][i]==1){
                    queue.offer(i);
                    visited[i] = 1;
                }
            }
        }
    }
```

## 采用邻接表存储
图的邻接表存储是一种顺序存储与链接存储相结合的存储方法，类似于数的孩子链表表示法。对于图的每个顶点v，将所有邻接于v的顶点链成一个单链表，称为顶点v的边表（对于有向图则称为出边表）。

顶点类：
```java
/**
 * @Author zbl
 * @Date: 2019/11/18/ 17:59
 * @Description
 */

//顶点结点
public class VertexNode{
    public int vertex;
    public ArcNode firstEdge;
}
```
边表类：
```java
/**
 * @Author zbl
 * @Date: 2019/11/18/ 17:12
 * @Description
 */

//边结点
public class ArcNode {
    //邻接点域
    public int adjvex;
    public ArcNode next;
    public ArcNode(){}
    public ArcNode(int adjvex,ArcNode arcNode) {this.adjvex=adjvex;this.next=arcNode;}
}
```

---
以下面这个无向图为例进行实现
![39.jpg](/usr/uploads/2019/11/2915814393.jpg)

* 该无向图的`DFS`访问顺序：V0->V1->V4->V2->V3
* 该无向图的`BFS`访问顺序：V0->V1->V2->V3->V4

为了省时间（~~其实是自己懒~~ ），此处省略邻接表的构造过程，采用手动写入边集和点集构建该无向图。
```java
		//手动构造图的点集和边集
		//手动构造点集和边集
        VertexNode[] vertex = new VertexNode[5];
        for (int i = 0;i<vertex.length;++i){
            vertex[i] = new VertexNode();
            vertex[i].vertex=i;
        }

ArcNode V03 = new ArcNode(3,null);
        ArcNode V02 = new ArcNode(2,V03);
        ArcNode V01 = new ArcNode(1,V02);
        ArcNode V12 = new ArcNode(4,null);
        ArcNode V11 = new ArcNode(0,V12);
        ArcNode V22 = new ArcNode(3,null);
        ArcNode V21 = new ArcNode(0,V22);
        ArcNode V32 = new ArcNode(2,null);
        ArcNode V31 = new ArcNode(0,V32);
        ArcNode V41 = new ArcNode(1,null);

vertex[0].firstEdge=V01;
        vertex[1].firstEdge=V11;
        vertex[2].firstEdge=V21;
        vertex[3].firstEdge=V31;
        vertex[4].firstEdge=V41;

for(int i = 0; i<visited.length; ++i)
            visited[i] = 0;

```
### 深度优先遍历（递归实现）
```java
 	/**
    * @Description: 图的深搜DFS，邻接矩阵存储，递归
    * @Param: [vertex, visited, i]
    * @return: void
    * @Author: zbl
    * @Date: 2019/11/18
    */
    public static void DFS(VertexNode[] vertex,int[] visited,int i){
        System.out.println(vertex[i].vertex);
        visited[i]=1;
        ArcNode tmp = vertex[i].firstEdge;
        while(tmp != null){
            int j = tmp.adjvex;
            if(visited[j]==0)
                DFS(vertex,visited,j);
            tmp = tmp.next;
        }
    }
```

### 深度优先遍历 （非递归实现）
```java
/**
     * @Description: 图的深搜DFS，邻接矩阵存储，非递归
     * @Param: [vertex, visited]
     * @return: void
     * @Author: zbl
     * @Date: 2019/11/18
     */
    public static void DFS(VertexNode[] vertex,int[] visited){
        Stack<Integer> stack = new Stack<Integer>();
        //访问第一个顶点并入栈
        System.out.println(vertex[0].vertex);
        stack.push(0);
        visited[0]=1;
        //栈不为空
        while(!stack.isEmpty()){
            boolean flag = false;
            //获取栈顶但不弹栈
            int i = stack.peek();
            ArcNode tmp = vertex[i].firstEdge;
            //遍历边表
            while(tmp!=null){
                if (visited[tmp.adjvex]==0){
                    //访问并入栈
                    System.out.println(vertex[tmp.adjvex].vertex);
                    stack.push(tmp.adjvex);
                    //更改访问位,标志位
                    visited[tmp.adjvex]=1;
                    flag = true;
                    break;
                }
                tmp = tmp.next;
            }
            //弹栈
            if(!flag)
                stack.pop();
        }
    }
```

### 广度优先遍历
```java
	/**
    * @Description: 图的广搜BFS，邻接矩阵存储，非递归
    * @Param: [vertex, visited]
    * @return: void
    * @Author: zbl
    * @Date: 2019/11/18
    */
    public static void BFS(VertexNode[] vertex,int[] visited){
        for (int i = 0; i<vertex.length; ++i){
            ArcNode tmp = vertex[i].firstEdge;
            //若未访问,则访问并标记
            if (visited[i]==0){
                System.out.println(vertex[i].vertex);
                visited[i]=1;
            }

while(tmp!=null){
                //若未访问,则访问并标记
                if (visited[tmp.adjvex]==0){
                    System.out.println(vertex[tmp.adjvex].vertex);
                    visited[tmp.adjvex]=1;
                }
                tmp = tmp.next;
            }
        }
    }
```

## 完整函数代码
顶点类和边表类在上面已经给出，在此就不重复放出来了。

```java
import javafx.scene.shape.Arc;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
 * author zbl
 *
 * datetime 2019.11.18
 *
 */
public class Main {

//图的深搜DFS ,非递归
    public static void DFS(int[] vector, int[] visited, int[][] arc){
        //访问第一个顶点并入栈
        System.out.println(vector[0]);
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);
        visited[0] = 1;
        while(!stack.isEmpty()){
            //获取栈顶元素
            int x = stack.peek();
            //标志位
            boolean flag = false;
            for (int i = 0; i<vector.length;++i){
                if (visited[i]==0 && arc[x][i]==1){
                    System.out.println(vector[i]);
                    //入栈
                    stack.push(i);
                    //更改访问位,标志位
                    visited[i] = 1;
                    flag = true;
                    break;
                }
            }
            //出栈
            if (!flag)
                stack.pop();
        }
    }

//图的深搜DFS,递归
    public static void DFS(int[] vector, int[] visited, int[][] arc,int i){
        //访问结点并标记
        System.out.println(vector[i]);
        visited[i]=1;
        for (int j = 0;j<vector.length; ++j){
            if (visited[j]==0 && arc[i][j]==1)
                DFS(vector,visited,arc,j);
        }
    }

//图的广搜BFS,非递归
    public static void BFS(int[] vector, int[] visited, int[][] arc){
        Queue<Integer> queue = new LinkedList<Integer>();
        //第一个顶点入队
        queue.offer(0);
        while (!queue.isEmpty()){
            //出队
            int x = queue.poll();
            //访问结点并标记
            System.out.println(vector[x]);
            visited[x] = 1;
            //寻找连通的结点并入队
            for (int i = 0; i<vector.length;++i){
                if (visited[i]==0 && arc[x][i]==1){
                    queue.offer(i);
                    visited[i] = 1;
                }

}
        }
    }

/**
     * @Description: 图的深搜DFS，邻接矩阵存储，非递归
     * @Param: [vertex, visited]
     * @return: void
     * @Author: zbl
     * @Date: 2019/11/18
     */
    public static void DFS(VertexNode[] vertex,int[] visited){
        Stack<Integer> stack = new Stack<Integer>();
        //访问第一个顶点并入栈
        System.out.println(vertex[0].vertex);
        stack.push(0);
        visited[0]=1;
        //栈不为空
        while(!stack.isEmpty()){
            boolean flag = false;
            //获取栈顶但不弹栈
            int i = stack.peek();
            ArcNode tmp = vertex[i].firstEdge;
            //遍历边表
            while(tmp!=null){
                if (visited[tmp.adjvex]==0){
                    //访问并入栈
                    System.out.println(vertex[tmp.adjvex].vertex);
                    stack.push(tmp.adjvex);
                    //更改访问位,标志位
                    visited[tmp.adjvex]=1;
                    flag = true;
                    break;
                }
                tmp = tmp.next;
            }
            //弹栈
            if(!flag)
                stack.pop();
        }
    }

/**
    * @Description: 图的深搜DFS，邻接矩阵存储，递归
    * @Param: [vertex, visited, i]
    * @return: void
    * @Author: zbl
    * @Date: 2019/11/18
    */
    public static void DFS(VertexNode[] vertex,int[] visited,int i){
        System.out.println(vertex[i].vertex);
        visited[i]=1;
        ArcNode tmp = vertex[i].firstEdge;
        while(tmp != null){
            int j = tmp.adjvex;
            if(visited[j]==0)
                DFS(vertex,visited,j);
            tmp = tmp.next;
        }
    }
    
    /**
    * @Description: 图的广搜BFS，邻接矩阵存储，非递归
    * @Param: [vertex, visited]
    * @return: void
    * @Author: zbl
    * @Date: 2019/11/18
    */
    public static void BFS(VertexNode[] vertex,int[] visited){
        for (int i = 0; i<vertex.length; ++i){
            ArcNode tmp = vertex[i].firstEdge;
            //若未访问,则访问并标记
            if (visited[i]==0){
                System.out.println(vertex[i].vertex);
                visited[i]=1;
            }

while(tmp!=null){
                //若未访问,则访问并标记
                if (visited[tmp.adjvex]==0){
                    System.out.println(vertex[tmp.adjvex].vertex);
                    visited[tmp.adjvex]=1;
                }
                tmp = tmp.next;
            }
        }
    }

public static void main(String[] args) {
        //手动构造点集和边集
        //点集
        int[] vector = {
                0,1,2,3,4,5
        };
        //边集
        int[][] arc ={
                {0,1,1,1,1,0},
                {1,0,0,0,1,0},
                {1,0,0,0,1,0},
                {1,0,0,0,0,0},
                {1,1,1,0,0,1},
                {0,0,0,0,1,1}
        };
        //记录是否访问
        int[] visited = {
                0,0,0,0,0,0
        };
        System.out.println("===============邻接矩阵Start===============");
        System.out.println("Start DFS:");
        DFS(vector,visited,arc);
        System.out.println("End DFS\n");

for(int i = 0; i<visited.length; ++i)
            visited[i] = 0;

System.out.println("Start DFS:");
        DFS(vector,visited,arc,0);
        System.out.println("End DFS\n");

for(int i = 0; i<visited.length; ++i)
            visited[i] = 0;

System.out.println("Start BFS:");
        BFS(vector,visited,arc);
        System.out.println("End BFS");

System.out.println("===============邻接矩阵End===============\n");

System.out.println("===============邻接表Start===============");
        //手动构造点集和边集
        VertexNode[] vertex = new VertexNode[5];
        for (int i = 0;i<vertex.length;++i){
            vertex[i] = new VertexNode();
            vertex[i].vertex=i;
        }

vertex[0].firstEdge=V01;
        vertex[1].firstEdge=V11;
        vertex[2].firstEdge=V21;
        vertex[3].firstEdge=V31;
        vertex[4].firstEdge=V41;

for(int i = 0; i<visited.length; ++i)
            visited[i] = 0;

System.out.println("Start DFS:");
        DFS(vertex,visited);
        System.out.println("End DFS\n");

for(int i = 0; i<visited.length; ++i)
            visited[i] = 0;

System.out.println("Start DFS:");
        DFS(vertex,visited,0);
        System.out.println("End DFS\n");

for(int i = 0; i<visited.length; ++i)
            visited[i] = 0;

System.out.println("Start BFS:");
        BFS(vertex,visited);
        System.out.println("End BFS");
        System.out.println("===============邻接表End===============");
    }
}

```
## 注意事项
以上代码只适用于强连通图！！！
以上代码只适用于强连通图！！！
以上代码只适用于强连通图！！！
~~重要的事说三遍。~~ 
## 参考文献
* 王红梅，胡明，王涛编著. 数据结构（C++版）（第二版）[M]. 清华大学出版社.

最后修改：2020 年 03 月 14 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

rmviutrdtf
你的文章内容非常卖力，让人点赞。 https://www...
gcdcnzyapx
你的文章让我感受到了不一样的风景，谢谢分享。 https...
lfiiizlxlk
你的文章内容非常卖力，让人点赞。 http://www....
bwypobamml
你的文章让我感受到了不一样的风景，谢谢分享。 http:...
nixxjqcbzz
你的才华让人惊叹，请继续保持。 http://www.5...

数据结构之无向图的遍历

admin123 • 2019 年 11 月 18 日