一、图的遍历算法简述

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

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

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

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

二、深度优先遍历（DFS）

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

1.基本思想

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

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

2.代码

#define MAXVERTEXNUM 100  //Maximum value of the vertex numberbool visited[MAXVERTEXNUM]; // An array of tag for saving visited or nottypedef 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 numberbool visited[MAXVERTEXNUM]; // An array of tag for saving visited or nottypedef 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);			}		}	}}

转载地址：http://edyni.baihongyu.com/

你可能感兴趣的文章