图的深度和广度遍历

发表于 | 阅读量 次 | 分类于 |

前言

图是数据结构中最复杂的，正是因为它的复杂，它也是最优魅力的。当然图的存储结构有多种方式，最常用的就是邻接矩阵和邻接表。为了方便，这里图的遍历使用邻接矩阵表示

邻接矩阵

Alt text
如图，这里只画了无向图，其中顶点由一个一维数组表示，一个二维数组存储图中的边或弧的信息，可以发现无向图是一个对称矩阵，并且约定二维数组arc[i][j]=w，若边（vi，vj）属于该图，arc[i][j]=0，若i=j，否则arc[i][j]=一个无强大值，图中是用1代替了，实际中按上述规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535
typedef struct{
	VertexType vexs[MAXVEX];          /* 顶点表 */
	EdgeType arc[MAXVEX][MAXVEX];     /* 邻接矩阵，可看作边表 */
	int numVertexes,numEdges;         /* 图中当前的顶点数和边数 */ 
}MGraph;
void CreateMGraph(MGraph *G)
{
	int i,j,k,w;
	printf("输入顶点数和边数:\n");
	scanf("%d,%d",&G->numVertexes,&G->numEdges);
	for(i=0;i<G->numVertexes;i++)
		scanf(&G->vexs[i]);
	for(i=0;i<G->numVertexes;i++)
		for(j=0;j<G->numVertexes;j++)
			G->arc[i][j]=INFINITY;
		for(k=0;k<G->numEdges;k++)
		{
			printf("输入边（vi，vj）上的下标i，下标j和权值w：\n");
		     scanf("%d,%d,%d",&i,&j,&w);
		     G->arc[i][j]=w;
		     G->arc[j][i]=G->arc[i][j];
		}
}

深度优先遍历

Alt text
图的遍历就是指从图中某一顶点出发遍历图中其余顶点且使每一个顶点仅被访问一次，然而由于同一个图可能在空间形式上有不同画法，所以造成不能采用之前使用的双亲等方法，所以可以把访问过的顶点打上标记，即设置一个访问数组visited[n]，n是图中原点个数，初值为0，访问过后设置为1，这样就可以避免访问重复的了
而深度优先遍历，也叫深度优先搜索，简称DFS，就像在一个房子中搜索一样，从每一个房间开始，而是不留死角的搜索，也就是说该房间内所有地方搜索完，在去搜索其他房间，以此类推
从图中可以发现它是一个递归过程，也就是像二叉树的先序遍历，只不过，已经遍历的结点可以跳过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
void CreateMGraph(MGraph *G)
{
	int i, j;
	G->numEdges=15;
	G->numVertexes=9;
	/* 读入顶点信息，建立顶点表 */
	G->vexs[0]='A';
	G->vexs[1]='B';
	G->vexs[2]='C';
	G->vexs[3]='D';
	G->vexs[4]='E';
	G->vexs[5]='F';
	G->vexs[6]='G';
	G->vexs[7]='H';
	G->vexs[8]='I';
	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		for ( j = 0; j < G->numVertexes; j++)
		{
			G->arc[i][j]=0;
		}
	}
	G->arc[0][1]=1;
	G->arc[0][5]=1;
	G->arc[1][2]=1; 
	G->arc[1][8]=1; 
	G->arc[1][6]=1; 
	
	G->arc[2][3]=1; 
	G->arc[2][8]=1; 
	
	G->arc[3][4]=1;
	G->arc[3][7]=1;
	G->arc[3][6]=1;
	G->arc[3][8]=1;
	G->arc[4][5]=1;
	G->arc[4][7]=1;
	G->arc[5][6]=1; 
	
	G->arc[6][7]=1; 
	
	for(i = 0; i < G->numVertexes; i++)
	{
		for(j = i; j < G->numVertexes; j++)
		{
			G->arc[j][i] =G->arc[i][j];
		}
	}
}
Boolean visited[MAXSIZE];//访问标志的数组
//深度优先递归算法
void DFS(MGraph G,int i){
	int j;
	visited[i]=TRUE;
	printf("%c",G.vexs[i]);
	for(j=0;j<G.numVertexes;j++)
		if(G.arc[i][j]==1&&!visited[j]) //对未访问的顶点递归调用
			DFS(G,j);
}
//深度遍历
void DFSTraverse(MGraph G){
	int i;
	for(i=0;i<G.numVertexes;i++) //初始化
		visited[i]=FALSE;
	for(i=0;i<G.numVertexes;i++)
		if(!visited[i])
			DFS(G,i);
}
int main(void)
{    
	MGraph G;
	CreateMGraph(&G);
	printf("\n深度遍历：");
	DFSTraverse(G);
	return 0;
}

为了方便，就创建图的过程写死，最终深度遍历的结果为ABCDEFGHI

广度优先遍历

又称为广度优先搜索，简称BFS，它像二叉树遍历中的层序遍历，也就是一层一层的遍历，如上图，与A相连的有B、F，先遍历，又与B相连的有C,I,G，F相连的有G,E，所以下一层为C,I,G,F，依次类推一层一层遍历
Alt text
如图它的核心思想就是构造一个队列，每一层的结点，如A出队后，与它相连的下一层结点B、F就要入队开始遍历，然后B遍历完出队，与B相连的下一层结点C、I、J入队，依次类推
队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/* 循环队列的顺序存储结构 */
typedef struct
{
	int data[MAXSIZE];
	int front;    	/* 头指针 */
	int rear;		/* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}Queue;
/* 初始化一个空队列Q */
Status InitQueue(Queue *Q)
{
	Q->front=0;
	Q->rear=0;
	return  OK;
}
/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(Queue Q)
{ 
	if(Q.front==Q.rear) /* 队列空的标志 */
		return TRUE;
	else
		return FALSE;
}
/* 若队列未满，则插入元素e为Q新的队尾元素 */
Status EnQueue(Queue *Q,int e)
{
	if ((Q->rear+1)%MAXSIZE == Q->front)	/* 队列满的判断 */
		return ERROR;
	Q->data[Q->rear]=e;			/* 将元素e赋值给队尾 */
	Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置， */
								/* 若到最后则转到数组头部 */
	return  OK;
}
/* 若队列不空，则删除Q中队头元素，用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{
	if (Q->front == Q->rear)			/* 队列空的判断 */
		return ERROR;
	*e=Q->data[Q->front];				/* 将队头元素赋值给e */
	Q->front=(Q->front+1)%MAXSIZE;	/* front指针向后移一位置， */
									/* 若到最后则转到数组头部 */
	return  OK;
}

广度遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/* 邻接矩阵的广度遍历算法 */
void BFSTraverse(MGraph G)
{
	int i, j;
	Queue Q;
	for(i = 0; i < G.numVertexes; i++)
       	visited[i] = FALSE;
    InitQueue(&Q);		/* 初始化一辅助用的队列 */
    for(i = 0; i < G.numVertexes; i++)  /* 对每一个顶点做循环 */
    {
		if (!visited[i])	/* 若是未访问过就处理 */
		{
			visited[i]=TRUE;		/* 设置当前顶点访问过 */
			printf("%c ", G.vexs[i]);/* 打印顶点，也可以其它操作 */
			EnQueue(&Q,i);		/* 将此顶点入队列 */
			while(!QueueEmpty(Q))	/* 若当前队列不为空 */
			{
				DeQueue(&Q,&i);	/* 将队对元素出队列，赋值给i */
				for(j=0;j<G.numVertexes;j++) 
				{ 
					/* 判断其它顶点若与当前顶点存在边且未访问过  */
					if(G.arc[i][j] == 1 && !visited[j]) 
					{ 
 						visited[j]=TRUE;			/* 将找到的此顶点标记为已访问 */
						printf("%c ", G.vexs[j]);	/* 打印顶点 */
						EnQueue(&Q,j);				/* 将找到的此顶点入队列  */
					} 
				} 
			}
		}
	}
}
int main(void)
{    
	MGraph G;
	CreateMGraph(&G);
	printf("\n深度遍历：");
	DFSTraverse(G);
	printf("\n广度遍历：");
	BFSTraverse(G);
	return 0;
}

最终的结果是

A B F C I G E D H

总结

最后发现深度优先和广度优先遍历的时间复杂度是一样的，他们的适用场景不一样，深度优先更适合目标比较明确，已找到目标为主要目的的情况，而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况

快乐源于分享，总结溢于提高

热评文章