数据结构(6)_图
引言
图(Graph)是一种比线性表和树更为复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
基础概念看书，不再赘述
图的存储结构
注意，之前线性表和树都有两类不同的存储结构，顺序映像和链式映像。由于图的结构比较复杂，任意两个定点之间都可能存在关系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序映像的存储结构，但可以借助数组的数据类型表示元素之间的关系。
数组表示法(邻接矩阵)
用两个数组分别存储数据元素的信息和数据元素之间的关系(边或弧)的信息。代码如下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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define INFINITY INT_MAX // 最大值 包含在头文件limits.h
#define MAX_VERTER_NUM 20 // 最大顶点数
typedef enum {DG, DN, UDG, UDN} GraphKind; // {有向图，有向网，无向图，无向网}
typedef int VRType; // VRType是顶点关系类型， 对无权图 用1或0表示是否相邻；对于带权图则直接记录权重
typedef char VerterType; // 顶点存字符吧
typedef struct ArcCell{
VRType adj;
// InfoType *info; //该弧相关信息的指针(一般没啥附加信息)
}ArcCell, AdjMatrix[MAX_VERTER_NUM][MAX_VERTER_NUM];
typedef struct{
VerterType vexs[MAX_VERTER_NUM]; // 记录顶点
AdjMatrix arcs; // 邻接矩阵
int vexnum, arcnum; // 顶点数 弧数
GraphKind kind; // 图类型
}MGraph;
int findVex(MGraph G, VerterType v){ // 遍历图的顶点数组，找到顶点v的下标，如果没有返回-1
for(int i=0;i<G.vexnum;i++){
if(G.vexs[i] == v)
return i;
}
return -1;
}
void CreateDG(MGraph &G){ // 创建有向图
int i,j,k;
scanf("%d",&G.vexnum); // 图的顶点数
scanf("%d",&G.arcnum); // 图的边数
for(i = 0;i<G.vexnum;i++){ // 构造顶点向量
getchar();
scanf("%c",&G.vexs[i]);
}
for(i = 0;i<G.arcnum;i++){ // 初始化邻接矩阵 因为是有向图，所以用0表示没有关系，1表示从i到j 初始化边全为0
for(j = 0;j<G.arcnum;j++){
G.arcs[i][j].adj = 0;
}
}
VerterType v1,v2; //用来接收输入的两个顶点
for(k=0;k<G.arcnum;k++){ // 输入边信息，构造邻接矩阵
getchar();
scanf("%c %c",&v1,&v2);
i = findVex(G,v1);
j = findVex(G,v2);
G.arcs[i][j].adj = 1; // 有向的 所以只有i到j
}
}
void CreateDN(MGraph &G){ // 创建有向网
int i,j,k;
scanf("%d",&G.vexnum); // 图的顶点数
scanf("%d",&G.arcnum); // 图的边数
for(i = 0;i<G.vexnum;i++){ // 构造顶点向量
getchar();
scanf("%c",&G.vexs[i]);
}
for(i = 0;i<G.arcnum;i++){ // 初始化邻接矩阵 因为是有向网，所以用INFINITY表示没有关系，其他浮点数表示网的权重。初始化全为INFINITY
for(j = 0;j<G.arcnum;j++){
G.arcs[i][j].adj = INFINITY;
}
}
VerterType v1,v2; //用来接收输入的两个顶点
VRType info; // 网的边有权重 用来接收权重
for(k=0;k<G.arcnum;k++){ // 输入边信息，构造邻接矩阵
getchar();
scanf("%c %c %d",&v1,&v2,&info);
i = findVex(G,v1);
j = findVex(G,v2);
G.arcs[i][j].adj = info; // 有向的 所以只有i到j
}
}
void CreateUDG(MGraph &G){ // 创建无向图
int i,j,k;
scanf("%d",&G.vexnum); // 图的顶点数
scanf("%d",&G.arcnum); // 图的边数
for(i = 0;i<G.vexnum;i++){ // 构造顶点向量
getchar();
scanf("%c",&G.vexs[i]);
}
for(i = 0;i<G.arcnum;i++){ // 初始化邻接矩阵 因为是无向图，所以用0表示没有关系，1表示从i到j 初始化边全为0
for(j = 0;j<G.arcnum;j++){
G.arcs[i][j].adj = 0;
}
}
VerterType v1,v2; //用来接收输入的两个顶点
for(k=0;k<G.arcnum;k++){ // 输入边信息，构造邻接矩阵
getchar();
scanf("%c %c",&v1,&v2);
i = findVex(G,v1);
j = findVex(G,v2);
G.arcs[i][j].adj = 1;
G.arcs[j][i].adj = 1; // 无向的 所以i到j 和j到i一样的
}
}
void CreateUDN(MGraph &G){ // 创建无向网
int i,j,k;
scanf("%d",&G.vexnum); // 图的顶点数
scanf("%d",&G.arcnum); // 图的边数
for(i = 0;i<G.vexnum;i++){ // 构造顶点向量
getchar();
scanf("%c",&G.vexs[i]);
}
for(i = 0;i<G.arcnum;i++){ // 初始化邻接矩阵 因为是无向网，所以用INFINITY表示没有关系，其他浮点数表示网的权重。初始化全为INFINITY
for(j = 0;j<G.arcnum;j++){
G.arcs[i][j].adj = INFINITY;
}
}
VerterType v1,v2; //用来接收输入的两个顶点
VRType info; // 网的边有权重 用来接收权重
for(k=0;k<G.arcnum;k++){ // 输入边信息，构造邻接矩阵
getchar();
scanf("%c %c %d",&v1,&v2,&info);
i = findVex(G,v1);
j = findVex(G,v2);
G.arcs[i][j].adj = info;
G.arcs[j][i].adj = info; // 无向的 所以i到j 和j到i一样的
}
}
void print_G(MGraph G){ // 打印邻接矩阵
int i,j;
printf(" ");
for(i=0;i<G.vexnum;i++){
printf("%c ",G.vexs[i]);
}
printf("\n");
for(i=0;i<G.vexnum;i++){
printf("%c ",G.vexs[i]);
for(j=0;j<G.vexnum;j++){
if(G.arcs[i][j].adj == INFINITY){
printf("# ");
}else{
printf("%d ",G.arcs[i][j].adj);
}
}
printf("\n");
}
}
int main(){
MGraph G;
int k;
scanf("%d",&k); //0 1 2 3
G.kind = (GraphKind)k;
switch(G.kind){
case DG: CreateDG(G); break; // 有向图
case DN: CreateDN(G); break; // 有向网
case UDG: CreateUDG(G); break; // 无向图
case UDN: CreateUDN(G); break; // 无向网
}
print_G(G);
return 0;
}
邻接表
邻接表是图的一种链式存储结构，在表中，对图中每个顶点建立一个但链表，表示依附于该顶点的边。每个边(弧)结点包含三个域，邻接点域(adjvex)表示边邻接的另一个顶点在顶点数组中的位置（下标）。该顶点的下一个边（类似线性表的next）。该边的信息（权重啥的）。代码如下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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define MAX_VERTER_NUM 20 // 最大顶点数
typedef int Infotype; // 弧上权重，如果是图则是0，网则是权重
typedef char VertexType; // 顶点存字符吧
typedef enum {DG, DN, UDG, UDN} GraphKind; // {有向图，有向网，无向图，无向网}
typedef struct ArcNode{
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc; // 同顶点下一条弧
Infotype info;
}ArcNode;
typedef struct VNode{
VertexType data; //顶点信息
ArcNode *firstarc; // 指向依附该顶点的第一条边
}VNode, AdjList[MAX_VERTER_NUM];
typedef struct{
AdjList vertices;
int vexnum, arcnum;
GraphKind kind; // 图类型
}ALGraph;
int findVex(ALGraph G, VertexType v){ // 遍历图的顶点数组，找到顶点v的下标，如果没有返回-1
for(int i=0;i<G.vexnum;i++){
if(G.vertices[i].data == v)
return i;
}
return -1;
}
void CreateDG(ALGraph &G){ // 创建有向图
int i,j,k;
scanf("%d",&G.vexnum); // 图的顶点数
scanf("%d",&G.arcnum); // 图的边数
for(i = 0;i<G.vexnum;i++){ // 构造顶点向量
getchar();
scanf("%c",&G.vertices[i].data);
G.vertices[i].firstarc = NULL;
}
VertexType v1,v2; //用来接收输入的两个顶点
ArcNode *p,*q;
for(k=0;k<G.arcnum;k++){ // 输入边信息，构造邻接表，逆序创建边结点
getchar();
scanf("%c %c",&v1,&v2);
i = findVex(G,v1);
j = findVex(G,v2);
q = G.vertices[i].firstarc; //找到依附的结点，把结点已有的边链表用q指着
p = (ArcNode*)malloc(sizeof(ArcNode)); // 创建一个新的边结点
p->adjvex = j;
p->nextarc = q; //把p插入到边链表的最前面
p->info = 0;
G.vertices[i].firstarc = p;
}
}
void CreateDN(ALGraph &G){ // 创建有向网
int i,j,k;
scanf("%d",&G.vexnum); // 图的顶点数
scanf("%d",&G.arcnum); // 图的边数
for(i = 0;i<G.vexnum;i++){ // 构造顶点向量
getchar();
scanf("%c",&G.vertices[i].data);
G.vertices[i].firstarc = NULL;
}
VertexType v1,v2; //用来接收输入的两个顶点
ArcNode *p,*q;
Infotype info;
for(k=0;k<G.arcnum;k++){ // 输入边信息，构造邻接表，逆序创建边结点
getchar();
scanf("%c %c %d",&v1,&v2,&info);
i = findVex(G,v1);
j = findVex(G,v2);
q = G.vertices[i].firstarc; //找到依附的结点，把结点已有的边链表用q指着
p = (ArcNode*)malloc(sizeof(ArcNode)); // 创建一个新的边结点
p->adjvex = j;
p->nextarc = q; //把p插入到边链表的最前面
p->info = info;
G.vertices[i].firstarc = p;
}
}
void CreateUDG(ALGraph &G){ // 创建无向图
int i,j,k;
scanf("%d",&G.vexnum); // 图的顶点数
scanf("%d",&G.arcnum); // 图的边数
for(i = 0;i<G.vexnum;i++){ // 构造顶点向量
getchar();
scanf("%c",&G.vertices[i].data);
G.vertices[i].firstarc = NULL;
}
VertexType v1,v2; //用来接收输入的两个顶点
ArcNode *p,*q;
for(k=0;k<G.arcnum;k++){ // 输入边信息，构造邻接表，逆序创建边结点
getchar();
scanf("%c %c",&v1,&v2);
i = findVex(G,v1);
j = findVex(G,v2);
// i顶点结点建立边结点
q = G.vertices[i].firstarc; //找到依附的结点，把结点已有的边链表用q指着
p = (ArcNode*)malloc(sizeof(ArcNode)); // 创建一个新的边结点
p->adjvex = j;
p->nextarc = q; //把p插入到边链表的最前面
p->info = 0;
G.vertices[i].firstarc = p;
// j顶点结点建立边结点（可以看出，边结点信息冗余了）
q = G.vertices[j].firstarc; //找到依附的结点，把结点已有的边链表用q指着
p = (ArcNode*)malloc(sizeof(ArcNode)); // 创建一个新的边结点
p->adjvex = i;
p->nextarc = q; //把p插入到边链表的最前面
p->info = 0;
G.vertices[j].firstarc = p;
}
}
void CreateUDN(ALGraph &G){ // 创建无向网
int i,j,k;
scanf("%d",&G.vexnum); // 图的顶点数
scanf("%d",&G.arcnum); // 图的边数
for(i = 0;i<G.vexnum;i++){ // 构造顶点向量
getchar();
scanf("%c",&G.vertices[i].data);
G.vertices[i].firstarc = NULL;
}
VertexType v1,v2; //用来接收输入的两个顶点
ArcNode *p,*q;
Infotype info;
for(k=0;k<G.arcnum;k++){ // 输入边信息，构造邻接表，逆序创建边结点
getchar();
scanf("%c %c %d",&v1,&v2,&info);
i = findVex(G,v1);
j = findVex(G,v2);
q = G.vertices[i].firstarc; //找到依附的结点，把结点已有的边链表用q指着
p = (ArcNode*)malloc(sizeof(ArcNode)); // 创建一个新的边结点
p->adjvex = j;
p->nextarc = q; //把p插入到边链表的最前面
p->info = info;
G.vertices[i].firstarc = p;
q = G.vertices[j].firstarc; //找到依附的结点，把结点已有的边链表用q指着
p = (ArcNode*)malloc(sizeof(ArcNode)); // 创建一个新的边结点
p->adjvex = i;
p->nextarc = q; //把p插入到边链表的最前面
p->info = info;
G.vertices[j].firstarc = p;
}
}
void print_G(ALGraph &G){ // 打印邻接表
ArcNode *p;
for(int i = 0;i<G.vexnum;i++){
printf("%c",G.vertices[i].data);
p = G.vertices[i].firstarc;
while(p!=NULL){
printf("->%c:%d",G.vertices[p->adjvex].data,p->info);
p=p->nextarc;
}
printf("\n");
}
}
int main(){
ALGraph G;
int k;
scanf("%d",&k); //0 1 2 3
G.kind = (GraphKind)k;
switch(G.kind){
case DG: CreateDG(G); break; // 有向图
case DN: CreateDN(G); break; // 有向网
case UDG: CreateUDG(G); break; // 无向图
case UDN: CreateUDN(G); break; // 无向网
}
print_G(G);
return 0;
}
十字链表
十字链表是有向图(网)的另外一种链式存储结构，可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表。在十字链表中，顶点结点包含三个域，顶点数据域(data)，firstin指向它的第一个边(入度)，firstout它指出去的第一个边(出度)。每一个弧结点有五个域，(tailvex)尾域指向弧尾结点，(headvex)头域指向弧头结点。链域(hlink)指向同弧头的下一条弧，链域(tlink)指向同弧头的下一条弧，(info)记录弧信息
代码如下：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#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define MAX_VERTER_NUM 20 // 最大顶点数
typedef int Infotype; // 弧上权重，如果是图则是0，网则是权重
typedef char VertexType; // 顶点存字符吧
typedef struct ArcNode{ // 弧结点
int tailvex,headvex; // 该弧的弧头 弧尾结点位置
struct ArcNode *hlink, *tlink; // 同弧头 同弧尾的下一个弧
Infotype info; //如果是网 则放0
}ArcNode;
typedef struct VexNode{ // 顶点结点
VertexType data;
ArcNode *firstin,*firstout;
}VexNode;
typedef struct{
VexNode xlist[MAX_VERTER_NUM]; // 头结点向量
int vexnum, arcnum;
}OLGraph;
int findVex(OLGraph G, VertexType v){ // 遍历图的顶点数组，找到顶点v的下标，如果没有返回-1
for(int i=0;i<G.vexnum;i++){
if(G.xlist[i].data == v)
return i;
}
return -1;
}
void CreateOLG(OLGraph &G){ // 创建有向图
int i,j,k;
scanf("%d",&G.vexnum); // 图的顶点数
scanf("%d",&G.arcnum); // 图的边数
for(i = 0;i<G.vexnum;i++){ // 构造顶点向量
getchar();
scanf("%c",&G.xlist[i].data);
G.xlist[i].firstin = NULL;
G.xlist[i].firstout = NULL;
}
VertexType v1,v2; //用来接收输入的两个顶点
ArcNode *in,*out,*p;
Infotype info;
for(k=0;k<G.arcnum;k++){ // 输入边信息，构造邻接表，逆序创建边结点
getchar();
scanf("%c %c %d",&v1,&v2,&info); // 从v1出 到 v2入 如果是图
i = findVex(G,v1);
j = findVex(G,v2);
out = G.xlist[i].firstout; //找到v1的出度边链表，用in指着
in = G.xlist[j].firstin; //找到v2的出度边链表，用in指着
p = (ArcNode*)malloc(sizeof(ArcNode)); // 创建一个新的边结点
p->tailvex = i;
p->headvex = j;
p->hlink = in;
p->tlink = out;
p->info = info;
G.xlist[i].firstout = p;
G.xlist[j].firstin = p;
}
}
int main(){
OLGraph G;
CreateOLG(G); // 有向图
return 0;
}
邻接多重表
邻接多重表是无向图的另一种链式存储结构。虽然邻接表是无向图的一种很有效的存储结构，在邻接表中容易求的顶点和边的信息，但边结点冗余，同一个边结点存在两个一样的，这对一些搜索操作不方便（比如搜索时要记录哪些边搜索过）。
邻接多重表的形式与十字链表类似。十字链表是用于有向图 所以无论顶点结点还是弧结点都要考虑出度与入度，而邻接多重表则不需要，所以其结构更简单，可由以下几个域构成。mark标志域用来记录是否被搜索过，该域同样也可以加入到十字链表中。ivex和jvex记录这条边的两个顶点。ilink,jlink记录依附的两个顶点的下一个边，info边信息比如权重。
顶点结点因为不用考虑出入度，所有边都一样，所以只有两个域，数据域(data)和边域(firstedge)指向第一条边。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#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define MAX_VERTER_NUM 20 // 最大顶点数
typedef int Infotype; // 弧上权重，如果是图则是0，网则是权重
typedef char VertexType; // 顶点存字符吧
typedef enum {unvisited, visited} VisitIf; //枚举是否已经访问
typedef struct EdgeNode{
VisitIf mark; // 记录遍历时该边是否走过
int ivex, jvex; // 边的两个顶点
struct EdgeNode *ilink, *jlink;// 两个顶点的下一个边
Infotype info; // 边权重
}EdgeNode;
typedef struct VexNode{
VertexType data;
EdgeNode *firstedge;
}VexNode;
typedef struct{
VexNode adjmulist[MAX_VERTER_NUM];
int vexnum,edgenum;
}AMLGraph;
int findVex(AMLGraph G, VertexType v){ // 遍历图的顶点数组，找到顶点v的下标，如果没有返回-1
for(int i=0;i<G.vexnum;i++){
if(G.adjmulist[i].data == v)
return i;
}
return -1;
}
void CreateAMLG(AMLGraph &G){ // 创建无向图
int i,j,k;
scanf("%d",&G.vexnum); // 图的顶点数
scanf("%d",&G.edgenum); // 图的边数
for(i = 0;i<G.vexnum;i++){ // 构造顶点向量
getchar();
scanf("%c",&G.adjmulist[i].data);
G.adjmulist[i].firstedge = NULL;
}
VertexType v1,v2; //用来接收输入的两个顶点
EdgeNode *qi,*qj,*p;
Infotype info;
for(k=0;k<G.edgenum;k++){ // 输入边信息，构造邻接表，逆序创建边结点
getchar();
scanf("%c %c %d",&v1,&v2,&info); // 从v1出 到 v2入 如果是图
i = findVex(G,v1);
j = findVex(G,v2);
qi = G.adjmulist[i].firstedge;
qj = G.adjmulist[j].firstedge;
p = (EdgeNode*)malloc(sizeof(EdgeNode)); // 创建一个新的边结点
p->mark = unvisited;
p->ivex = i;
p->jvex = j;
p->ilink = qi;
p->jlink = qj;
p->info = info;
G.adjmulist[i].firstedge = p;
G.adjmulist[j].firstedge = p;
}
}
int main(){
AMLGraph G;
CreateAMLG(G); // 有向图
return 0;
}
图的遍历
图的遍历与树类似，从某一结点开始把连通的所有结点访问(且仅访问一次)则是一次遍历。其根据遍历方式不一样，分为深度优先遍历和广度优先遍历。
深度优先搜索遍历
深度优先搜索遍历类似树的先根遍历，先遍历当前结点，然后找他的一个邻居结点，再以邻居结点作为新的结点去找它的一个邻居结点。可以看出来这是个递归算法。结束条件就是这个结点的所有邻居都被访问过了，则返回上一个结点。找它的其他的未访问的邻居结点。
这里需要一个数组辅助，记录每个顶点结点是否被访问过，避免重复访问，当然也可以在顶点结点中增加一个mark域来记录访问情况。这里采用数组辅助的形式。图采用邻接表 代码如下1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25void DFS(ALGraph G,int v,bool visited[]){ //从结点v开始深度遍历
printf("%c\n",G.vertices[v].data); // 打印出这个结点，表示已经访问
visited[v] = true;
// 根据邻接表的弧 找顶点i的邻接但没访问的结点
ArcNode *p = G.vertices[v].firstarc; //依附的弧
while(p!=NULL){
if(!visited[p->adjvex]){ // 这个弧连接的顶点还没访问则
DFS(G,p->adjvex,visited);
}
p = p->nextarc;
}
}
void DFSTraverse(ALGraph G){ // 深度搜索图G
bool visited[MAX_VERTER_NUM];
int v;
for(v=0;v<G.vexnum;v++){
visited[v] = false;
}
// 开始搜索
for(v=0;v<G.vexnum;v++){
if(!visited[v]){ // 如果该结点没被遍历过
DFS(G,v,visited);
}
}
}
广度优先搜索遍历
广度优先搜索遍历类似于树的层次遍历的过程，从某个结点开始，先将该结点访问，然后将该结点的所有邻居结点也访问，再根据邻居结点的访问顺序把它们没被访问的邻居结点访问一次，这里为了记录邻居结点访问顺序，需要用一个队列，先访问的入队，等访问完了，根据队列的出队顺序访问它的未访问邻居结点。
同样这里采用数组辅助的形式。图采用邻接表 代码如下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
32void BFSTraverse(ALGraph G){ // 广度搜索图G
bool visited[MAX_VERTER_NUM];
int v,u;
ArcNode *p;
for(v=0;v<G.vexnum;v++){
visited[v] = false;
}
LinkQueue q; //定义一个队列用于记录访问先后顺序
init_Queue(q);
// 开始搜索
for(v=0;v<G.vexnum;v++){
if(!visited[v]){ // 如果该结点没被遍历过
visited[v] = true;
printf("%c",G.vertices[v].data);
EnQueue(q,v); //当前结点入队
while(q.front!=q.rear){ //站不空
DeQueue(q,u); //出站站顶元素
//访问这个元素
// 找这个结点的没被访问的结点入站
p = G.vertices[u].firstarc; //依附的弧
while(p!=NULL){
if(!visited[p->adjvex]){ // 这个弧连接的顶点还没访问则
visited[p->adjvex] = true;
printf("%c",G.vertices[p->adjvex].data);
EnQueue(q,p->adjvex); //当前结点入队
}
p = p->nextarc;
}
}
}
}
}
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！