大话数据结构--图的遍历 74图的遍历

发表于

「这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战」。

7.4图的遍历

图的遍历是和树的遍历类似，我们希望从图中某一顶点出 发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍(Traversing Graph)。

7.4.1深度优先遍历

深度优先遍历（Deep_First_Search），称为简称DFS。

主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。

实例如下，序号代表的是遍历的顺序

从根节点 1 开始遍历，它相邻的节点有 2，3，4，先遍历节点 2，再遍历 2 的子节点 5，然后再遍历 5 的子节点 9

此时就从 9 回退到上一个节点 5，看下节点 5 是否还有除 9 以外的节点，没有继续回退到 2，2 也没有除 5 以外的节点，回退到 1，1 有除 2 以外的节点 3，所以从节点 3 开始进行深度优先遍历

同理从 10 开始往上回溯到 6, 6 没有除 10 以外的子节点，再往上回溯，发现 3 有除 6 以外的子点 7，所以此时会遍历 7

从 7 往上回溯到 3， 1，发现 1 还有节点 4 未遍历，所以此时沿着 4， 8 进行遍历,这样就遍历完成了

img

这好像就是树的前序前序遍历啊实际上不管是前序遍历，还是中序遍历，亦或是后序遍历，都属于深度优先遍历。

7.4.2广度优先遍历

广度优先遍历(Breadth_ First Search)， 又称为广度优先搜索，简称BFS

指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点

广度优先便利

它这个遍历类似图中的层序遍历

DFS 一般是解决连通性问题，而 BFS 一般是解决最短路径问题

#include<stdio.h>
#include<stdlib.h>
#define max 20
//边表节点
typedef struct node{
int adjvex;
struct node *next;
}eNode;
//头节点
typedef struct headnode{
char vertex;
eNode *firstedge;
}hNode;
//邻接表
typedef struct{
hNode adjlist[max];
int n,e; //顶点数，边数
}linkG;

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
js复制代码#include<stdio.h>
#include<stdlib.h> 
#define max 20
//边表节点 
typedef struct node{
	int adjvex;
	struct node *next; 
}eNode;
//头节点
typedef struct headnode{
	char vertex;
	eNode *firstedge;
}hNode; 
//邻接表
typedef struct{
	hNode adjlist[max];
	int n,e;   //顶点数，边数 
}linkG; 

//创建（邻接表） 
linkG *creat(linkG *g,int c) //c为0表示无向图 
{
	int i,j,k;
	eNode *s;
	int n1,e1;
	char ch;
	g=(linkG *)malloc(sizeof(linkG));
	printf("请输入顶点数及边数: ");
	scanf("%d%d",&n1,&e1);
	g->n=n1;g->e=e1;
	printf("请输入顶点信息：");
	getchar();
	for(i=0;i<n1;i++)
	{
		scanf("%c",&ch);
		g->adjlist[i].vertex=ch;
		g->adjlist[i].firstedge=NULL;
	 } 
	 getchar();
	 int i1,j1;
	 for(k=0;k<e1;k++)
	 {
	 	printf("请输入对（i,j）: ");
	 	scanf("%d%d",&i1,&j1);
	 	s=(eNode *)malloc(sizeof(eNode));
	 	s->adjvex=j1;
	 	s->next=g->adjlist[i1].firstedge;
	 	g->adjlist[i1].firstedge=s;
	 	if(c==0)
	 	{
	 		s=(eNode *)malloc(sizeof(eNode));
	 		s->adjvex=i1;
	 		s->next=g->adjlist[j1].firstedge;
	 		g->adjlist[j1].firstedge=s;
		  } 
	 }
	 return g;
}

int visited[max]; //标记是否访问 

//深度优先遍历DFS
void dfs(linkG *g,int i) //顶点i
{
	eNode *p;
	printf("%c ",g->adjlist[i].vertex);
	visited[i]=1;
	p=g->adjlist[i].firstedge;
	while(p)
	{
		if(!visited[p->adjvex])
			dfs(g,p->adjvex);
		p=p->next;
	}

}

void dfstravel(linkG *g)
{
	int i;
	for(i=0;i<g->n;i++)
		visited[i]=0;
	for(i=0;i<g->n;i++)
		if(!visited[i])
			dfs(g,i);
 } 

//广度优先遍历BFS
void bfs(linkG *g,int i) 
{
	int j;
	eNode *p;
	int q[max],front,rear;
	front=rear=0;
	printf("%c ",g->adjlist[i].vertex);
	visited[i]=1;
	q[rear++]=i;
	while(rear>front)
	{
		j=q[front++];
		p=g->adjlist[j].firstedge;
		while(p)
		{
			if(visited[p->adjvex]==0)
			{
				printf("%c ",g->adjlist[p->adjvex].vertex);
				q[rear++]=p->adjvex;
				visited[p->adjvex]=1;
			}
			p=p->next;
		}
	}
}

void bfstravel(linkG *g)
{
	int i,count=0;
	for(i=0;i<g->n;i++)
		visited[i]=0;
	for(i=0;i<g->n;i++)
		if(!visited[i])
			bfs(g,i);
}
 
//主函数 
int main()
{
	linkG *g;
	g=creat(g,0);
	printf("DFS：");
	dfstravel(g);
	printf("\n");
	printf("BFS：");
	bfstravel(g);
	printf("\n");
	
	
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%