【数据结构周周练】024 图的经典遍历算法之深度优先搜索、广度优先搜素

àì夳堔傛蜴生んèń 2021-06-24 16:09 386阅读 0赞

# 一、图的遍历算法简述 #

上两篇博客给大家讲了图的存储结构：邻接表，邻接矩阵，十字链表以及邻接多重表以及邻接表转化为邻接矩阵的方法。在周周练里，我们只讲了图的算法原理，并没有具体的实现过程，因为我们周周练是一个循序渐进的过程，我们先给大家分享一些基础的内容，然后再逐步深化。

今天要给大家分享的是图的两种遍历算法，深度优先搜索和广度优先搜索，当然以理论为主，同时给大家讲解算法原理以及算法内容，并没有算法具体的测试与应用，后续慢慢会给大家分享，让我们一起从基础开始，从理论开始。

我们知道，图的每一种存储结构其实都可以当作图的遍历，但是这种方式很多结点都会重复遍历，所以，我们希望能找到一种算法，避免重复查找，这就是我们今天要讲的两种遍历算法。

当然为了方便起见，我们将邻接矩阵的每个边初始化为0，在转化过程中，直接寻找存在的边，赋值为1即可。

# 二、深度优先遍历（DFS） #

图的深度优先遍历类似于树的先序遍历，我们借助栈的先进后出的功能，对其进行遍历。

## 1.基本思想 ##

1.首先访问图的其中一个结点，并置该结点访问标记，然后将该结点存入栈中；

2.然后访问与该结点邻接且未访问的结点，如果存在某邻接结点未被访问，进行与第一个结点相同的操作，如果邻接结点全部访问过，获取栈中栈顶元素进行步骤2。直到进行出栈操作时栈为空，遍历完成。

## 2.代码 ##

#define MAXVERTEXNUM 100  //Maximum value of the vertex number
    bool visited[MAXVERTEXNUM]; // An array of tag for saving visited or not
    
    typedef char VertexType; //the type of vertex
    
    // the graph are storaged by adjacency matrix 邻接矩阵存储图
    typedef struct {
    	VertexType Vex[MAXVERTEXNUM];
    	EdgeType Edge[MAXVERTEXNUM][MAXVERTEXNUM];  // adjacency matrix
    	int vexNum, arcNum;  //current vertex number and arc of graph
    }MGraph;
    
    //ergodic the graph by Depth-First-Search 深度优先搜索遍历图
    void DFSTraverse(MGraph G) {
    	for (int i = 0; i < G.vexNum; i++)
    		visited[i] = false;
    	for (int i = 0; i < G.vexNum; i++)
    	{
    		if (!visited[i]) {
    			DFS(G, i);
    		}
    	}
    }
    
    void DFS(MGraph G,int v){
    	visit(v);
    	visited[v] = true;
    	for (int i = FirstNeighbor(G,v); i >= 0; i = NextNeighbor(G, v, i))
    	{
    		if (!visited[i]) {
    			DFS(G, v);
    		}
    	}
    }

# 三、广度优先遍历（BFS） #

图的广度优先遍历类似于树的层次遍历，我们借助队列的先进先出的功能，对其进行遍历。

## 1.基本思想 ##

1.首先访问图的其中一个结点，并置该结点访问标记，然后将该结点存入队列中；

2.然后进行出队操作，获取出队元素，并判断该元素所有的邻接点是否已经被访问，若未被访问将其入队；

3.重复进行操作2，直到出队时队列为空，说明遍历完成.

## 2.代码 ##

#define MAXVERTEXNUM 100  //Maximum value of the vertex number
    bool visited[MAXVERTEXNUM]; // An array of tag for saving visited or not
    
    typedef char VertexType; //the type of vertex
    
    // the graph are storaged by adjacency matrix 邻接矩阵存储图
    typedef struct {
    	VertexType Vex[MAXVERTEXNUM];
    	EdgeType Edge[MAXVERTEXNUM][MAXVERTEXNUM];  // adjacency matrix
    	int vexNum, arcNum;  //current vertex number and arc of graph
    }MGraph;
    
    int visit(int v) {
    
    }
    
    //ergodic the graph by Breadth-First-Search 深度优先搜索遍历图
    void BFSTraverse(MGraph G) {
    	//Initialization the array
    	for (int i = 0; i < G.vexNum; i++) 
    	{
    		visited[i] = false;
    	}
    	//Initalization an auxiliary queue
    	InitQueue(Q);
    	for (int i = 0; i < G.vexNum; i++)
    	{
    		if (!visited[i]) {
    			BFS(G, i);
    		}
    	}
    }
    
    void BFS(MGraph G, int v) {
    	visit(v);
    	visited[v] = true;
    	EnQueue(Q, v);
    	while (Q)
    	{
    		DeQueue(Q, v);
    		for (int i = FirstNeighbor(G, v); i >= 0; i = NextNeighbor(G, v, i))
    		{
    			if (!visited[i]) {
    				BFS(G, v);
    				visited[v] = true;
    				EnQueue(Q, v);
    			}
    		}
    	}
    }