数据结构之图(图的基本操作)

139 阅读 0 评论 92 点赞

我是靠谱客的博主喜悦鞋垫，这篇文章主要介绍数据结构之图(图的基本操作)，现在分享给大家，希望可以做个参考。

由于图的基本操作的代码较多，我放到这一章来写。图可以用两种方法来存储，但是本人偏爱链表的表示方法，所以以下代码也都是是基于邻接链表的存储方式。

复制代码

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
 1 /*
 2 
以下存储结构参考严蔚敏版数据结构，不懂的可以翻阅查看
 3 */
 4 const int UNDIGRAPH = 0;　　　　//无向图
 5 const int DIGRAPH
= 1;　　　 //有向图
 6 const int MAX_VERTEX_NUM = 20;
 7
 8 typedef struct ArchNode
 9 {
10
int
vertexIndex;
//该弧指向顶点在图中顶点数组的索引，对应vertexs[20]的下标
11
ArchNode *nextarc;
//指向下一条弧的指针
12
InfoTypde info;
//比如弧的权重
13 }ArchNode;
14
15 typedef struct Vertex
16 {
17
VertexType data;
//顶点信息
18
ArchNode
*firstarc;
//指向第一条弧的指针
19 }Vertex;
20
21 //这样定义图有个坏处，一旦定义好，图中结点的个数就固定了！
22 typedef struct Graph
23 {
24
Vertex *vertexs[MAX_VERTEX_NUM];
//存储顶点的数组,存放的是指向顶点的指针
25
int vexNum;
//当前图中的定点数
26
int arcNum;
　　　　　　　 //当前图中的弧的个数
27
int kind;
　　　　　　　　　//图的种类，有向图还是无向图
28 }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
 1 /*
 2 
初始条件：kind是图的类型，目前有有向图和无向图 两种.
 3 
返回值
：无。---大部分函数都无返回值，是对图的引用进行操作的
 4 */
 5 void createGraph(Graph *&G,int kind)
 6 {
 7
if(G) G = NULL;
 8
G = (Graph *)malloc(sizeof(struct Graph));
 9
assert(NULL != G);
10
for(int i = 0; i < MAX_VERTEX_NUM; ++i)
11 
{
12
G->vertexs[i] = NULL;
//初始化指向顶点的指针为NULL
13 
}
14
G->kind = kind;
//设置图的种类
15
G->vexNum = 0;
//初始化图中顶点的个数
16
G->arcNum = 0;
//初始化图中弧的个数
17 }

//图的销毁

复制代码

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
 1 /*
 2 
初始条件：G存在
 3 
返回值
：无。---大部分函数都无返回值，是对图的引用进行操作的
 4 */
 5 void destoryGraph(Graph *&G)
 6 {
 7
ArchNode *cur,*next;
 8
if(NULL == G)
 9
return;
10
//遍历顶点
11
for(int i = 0; i < G->vexNum; ++i)
12 
{
13
if(!G->vertexs[i])
14
continue;
15
next = G->vertexs[i]->firstarc;
16
cur
= G->vertexs[i]->firstarc;
17
while(cur)
18 
{
19
next = cur->nextarc;
20 
free(cur);
21
cur = next;
22 
}
23
G->vertexs[i]->firstarc = NULL;
24 
}
25 
free(G);
26
G = NULL;
27 }

//向图中增加结点

复制代码

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
 1 //向图中增加结点
 2 /*
 3 
初始条件：G存在，data是结点的数据值
 4 */
 5 void addVertexToGraph(Graph *&G,VertexType data)
 6 {
 7
if(G->vexNum >= MAX_VERTEX_NUM)
 8 
{
 9
cout << "Too many vertex!" << endl;
10
return ;
11 
}
12
for(int i = 0; i < G->vexNum; ++i)
13 
{
14
if(!G->vertexs[i])
15
continue;
16
if(G->vertexs[i]->data == data)
17 
{
18
cout << "Already exists!" << endl;
19
return;
//不允许重复

20 
}
21 
}
22
Vertex *pVeterx;
23
pVeterx = (Vertex *)malloc(sizeof(struct Vertex));
24
pVeterx->data = data;
25
pVeterx->firstarc = NULL;
26
G->vertexs[G->vexNum] = pVeterx;
27
G->vexNum++;
28 }

//从图中删除一个结点

复制代码

1 void delVertexFromGraph(Graph *&G,VertexType data)
 2 {
 3
bool haveThisVertex = false;
 4
ArchNode *cur,*next,*temp,*pre;
 5
Vertex *anotherVertex;
 6
if(NULL == G)
 7
return;
 8
if(G->vexNum <= 0)
 9 
{
10
cout << "Have no vertex!" << endl;
11
return ;
12 
}
13
for(int i = 0; i < G->vexNum; ++i)
14 
{
15
if(!G->vertexs[i])
16
continue;
17
if(G->vertexs[i]->data == data)
18 
{
19
haveThisVertex = true;
20
//以下循环用来删除顶点所指向的弧链表
21
next = cur = G->vertexs[i]->firstarc;
22
if(G->kind == DIGRAPH)
//如果是有向图
23 
{
24
while(cur)
25 
{
26
next = cur->nextarc;
27 
free(cur);
28
G->arcNum --;
//弧的个数减一
29
cur = next;
30 
}
31
G->vertexs[i] = NULL;
32 
}
33
else if(G->kind == UNDIGRAPH)
//如果是无向图，这个麻烦点
34 
{
35
while(cur)
36 
{
37
//找到待删除的弧的另一个结点，将它的弧链表中指向被删除结点的弧也删掉
38
anotherVertex = G->vertexs[cur->vertexIndex];
//找到待删除弧对应的另一个结点
39
temp = anotherVertex->firstarc,pre = NULL;
40
while(temp)
//这个循环是为了删除另一个结点中保存弧信息
41 
{
42
if(temp->vertexIndex == i)
43 
{
44
//如果是首节点
45
if(NULL == pre)
//或者if(NULL == pre)
46 
{
47
anotherVertex->firstarc = temp->nextarc;
48 
free(temp);
49 
}
50
else
51 
{
52
pre->nextarc = temp->nextarc;
53 
free(temp);
54 
}
55
break;
//找到即停止循环
56 
}
57
pre = temp;
58
temp = temp->nextarc;
59 
}
60
next = cur->nextarc;
61 
free(cur);
62
G->arcNum --;
//弧的个数减一
63
cur = next;
64 
}
65
G->vertexs[i] = NULL;
66 
}
67
for(int j = i; j < G->vexNum - 1; ++j)
68 
{
69
G->vertexs[j] = G->vertexs[j + 1];
70 
}
71
G->vertexs[j] = NULL;
//
72
G->vexNum-- ;
//结点的个数减一
73
break;
74 
}
75 
}
76
if(!haveThisVertex)
77
cout << "没有该结点！" << endl;
78 }

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
 1 void delVertexFromGraph(Graph *&G,VertexType data)
 2 {
 3
bool haveThisVertex = false;
 4
ArchNode *cur,*next,*temp,*pre;
 5
Vertex *anotherVertex;
 6
if(NULL == G)
 7
return;
 8
if(G->vexNum <= 0)
 9 
{
10
cout << "Have no vertex!" << endl;
11
return ;
12 
}
13
for(int i = 0; i < G->vexNum; ++i)
14 
{
15
if(!G->vertexs[i])
16
continue;
17
if(G->vertexs[i]->data == data)
18 
{
19
haveThisVertex = true;
20
//以下循环用来删除顶点所指向的弧链表
21
next = cur = G->vertexs[i]->firstarc;
22
if(G->kind == DIGRAPH)
//如果是有向图
23 
{
24
while(cur)
25 
{
26
next = cur->nextarc;
27 
free(cur);
28
G->arcNum --;
//弧的个数减一
29
cur = next;
30 
}
31
G->vertexs[i] = NULL;
32 
}
33
else if(G->kind == UNDIGRAPH)
//如果是无向图，这个麻烦点
34 
{
35
while(cur)
36 
{
37
//找到待删除的弧的另一个结点，将它的弧链表中指向被删除结点的弧也删掉
38
anotherVertex = G->vertexs[cur->vertexIndex];
//找到待删除弧对应的另一个结点
39
temp = anotherVertex->firstarc,pre = NULL;
40
while(temp)
//这个循环是为了删除另一个结点中保存弧信息
41 
{
42
if(temp->vertexIndex == i)
43 
{
44
//如果是首节点
45
if(NULL == pre)
//或者if(NULL == pre)
46 
{
47
anotherVertex->firstarc = temp->nextarc;
48 
free(temp);
49 
}
50
else
51 
{
52
pre->nextarc = temp->nextarc;
53 
free(temp);
54 
}
55
break;
//找到即停止循环
56 
}
57
pre = temp;
58
temp = temp->nextarc;
59 
}
60
next = cur->nextarc;
61 
free(cur);
62
G->arcNum --;
//弧的个数减一
63
cur = next;
64 
}
65
G->vertexs[i] = NULL;
66 
}
67
for(int j = i; j < G->vexNum - 1; ++j)
68 
{
69
G->vertexs[j] = G->vertexs[j + 1];
70 
}
71
G->vertexs[j] = NULL;
//
72
G->vexNum-- ;
//结点的个数减一
73
break;
74 
}
75 
}
76
if(!haveThisVertex)
77
cout << "没有该结点！" << endl;
78 }

复制代码

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
 1 //初始条件：G存在，data是指定结点的数据值
 2 int findVertexIndexInGraph(const Graph *G,VertexType data)
 3 {
 4
if(NULL == G)
 5
return -1;
 6
for(int i = 0; i < G->vexNum; ++i)
 7 
{
 8
if(!G->vertexs[i])
 9
continue;
10
if(G->vertexs[i]->data == data)
11 
{
12
return i;
13
break;
14 
}
15 
}
16
return -1;
17 }

//向图中增加一条弧，有有向图和无向图之分

复制代码

1 //初始条件：G存在，指定起始点，和弧的权重
 2 void addArchToGraph(Graph *&G,VertexType startData,VertexType endData,InfoTypde weight = 0)
 3 {
 4
ArchNode *pArchNode,*cur;
 5
//先要找到start和end
 6
if(NULL == G)
 7
return;
 8
int startVertexIndex = findVertexIndexInGraph(G,startData);
 9
int endVertexIndex = findVertexIndexInGraph(G,endData);
10
cur = G->vertexs[startVertexIndex]->firstarc;
11
while(cur)
12 
{
13
if(cur->vertexIndex == endVertexIndex)
14 
{
15
cout << "Already have this arch!" << endl;
16
return ;
17 
}
18
cur = cur->nextarc;
19 
}
20
if(startVertexIndex >= 0 && endVertexIndex >= 0)
21 
{
22
if(G->kind == DIGRAPH)
//如果是有向图
23 
{
24
pArchNode = (ArchNode *)malloc(sizeof(struct ArchNode));
//创建一个弧结点
25
pArchNode->info = weight;
26
pArchNode->nextarc = NULL;
27
pArchNode->vertexIndex = endVertexIndex;
28
cur = G->vertexs[startVertexIndex]->firstarc;
29
if(NULL == cur)
30 
{
31
G->vertexs[startVertexIndex]->firstarc = pArchNode;
32 
}
33
else
34 
{
35
while(cur->nextarc)
36 
{
37
cur = cur->nextarc;
38 
}
39
cur->nextarc = pArchNode;
40 
}
41
G->arcNum ++;
//弧的条数加一
42 
}
43
else if(G->kind == UNDIGRAPH)
//如果是无向图
44 
{
45
pArchNode = (ArchNode *)malloc(sizeof(struct ArchNode));
//创建一个弧结点
46
pArchNode->info = weight;
47
pArchNode->nextarc = NULL;
48
pArchNode->vertexIndex = endVertexIndex;
49
cur = G->vertexs[startVertexIndex]->firstarc;
50
if(NULL == cur)
51 
{
52
G->vertexs[startVertexIndex]->firstarc = pArchNode;
53 
}
54
else
55 
{
56
while(cur->nextarc)
57 
{
58
cur = cur->nextarc;
59 
}
60
cur->nextarc = pArchNode;
61 
}
62
pArchNode = (ArchNode *)malloc(sizeof(struct ArchNode));
//再创建一个弧结点
63
pArchNode->info = weight;
64
pArchNode->nextarc = NULL;
65
pArchNode->vertexIndex = startVertexIndex;
66
cur = G->vertexs[endVertexIndex]->firstarc;
67
if(NULL == cur)
68 
{
69
G->vertexs[endVertexIndex]->firstarc = pArchNode;
70 
}
71
else
72 
{
73
while(cur->nextarc)
74 
{
75
cur = cur->nextarc;
76 
}
77
cur->nextarc = pArchNode;
78 
}
79
G->arcNum ++;
//弧的条数加一
80 
}
81 
}
82
else
83 
{
84
cout << "起点或终点不存在！" << endl;
85
return ;
86 
}
87 }

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
 1 //初始条件：G存在，指定起始点，和弧的权重
 2 void addArchToGraph(Graph *&G,VertexType startData,VertexType endData,InfoTypde weight = 0)
 3 {
 4
ArchNode *pArchNode,*cur;
 5
//先要找到start和end
 6
if(NULL == G)
 7
return;
 8
int startVertexIndex = findVertexIndexInGraph(G,startData);
 9
int endVertexIndex = findVertexIndexInGraph(G,endData);
10
cur = G->vertexs[startVertexIndex]->firstarc;
11
while(cur)
12 
{
13
if(cur->vertexIndex == endVertexIndex)
14 
{
15
cout << "Already have this arch!" << endl;
16
return ;
17 
}
18
cur = cur->nextarc;
19 
}
20
if(startVertexIndex >= 0 && endVertexIndex >= 0)
21 
{
22
if(G->kind == DIGRAPH)
//如果是有向图
23 
{
24
pArchNode = (ArchNode *)malloc(sizeof(struct ArchNode));
//创建一个弧结点
25
pArchNode->info = weight;
26
pArchNode->nextarc = NULL;
27
pArchNode->vertexIndex = endVertexIndex;
28
cur = G->vertexs[startVertexIndex]->firstarc;
29
if(NULL == cur)
30 
{
31
G->vertexs[startVertexIndex]->firstarc = pArchNode;
32 
}
33
else
34 
{
35
while(cur->nextarc)
36 
{
37
cur = cur->nextarc;
38 
}
39
cur->nextarc = pArchNode;
40 
}
41
G->arcNum ++;
//弧的条数加一
42 
}
43
else if(G->kind == UNDIGRAPH)
//如果是无向图
44 
{
45
pArchNode = (ArchNode *)malloc(sizeof(struct ArchNode));
//创建一个弧结点
46
pArchNode->info = weight;
47
pArchNode->nextarc = NULL;
48
pArchNode->vertexIndex = endVertexIndex;
49
cur = G->vertexs[startVertexIndex]->firstarc;
50
if(NULL == cur)
51 
{
52
G->vertexs[startVertexIndex]->firstarc = pArchNode;
53 
}
54
else
55 
{
56
while(cur->nextarc)
57 
{
58
cur = cur->nextarc;
59 
}
60
cur->nextarc = pArchNode;
61 
}
62
pArchNode = (ArchNode *)malloc(sizeof(struct ArchNode));
//再创建一个弧结点
63
pArchNode->info = weight;
64
pArchNode->nextarc = NULL;
65
pArchNode->vertexIndex = startVertexIndex;
66
cur = G->vertexs[endVertexIndex]->firstarc;
67
if(NULL == cur)
68 
{
69
G->vertexs[endVertexIndex]->firstarc = pArchNode;
70 
}
71
else
72 
{
73
while(cur->nextarc)
74 
{
75
cur = cur->nextarc;
76 
}
77
cur->nextarc = pArchNode;
78 
}
79
G->arcNum ++;
//弧的条数加一
80 
}
81 
}
82
else
83 
{
84
cout << "起点或终点不存在！" << endl;
85
return ;
86 
}
87 }

//从图中删除一条弧

复制代码

1 //初始条件：G存在，指定要删除弧连接的两个顶点
 2 void delArchFromGraph(Graph *&G,VertexType startData,VertexType endData)
 3 {
 4
ArchNode *cur,*pre;
 5
//先要找到start和end
 6
if(NULL == G)
 7
return;
 8
int startVertexIndex = findVertexIndexInGraph(G,startData);
 9
int endVertexIndex = findVertexIndexInGraph(G,endData);
10
if(startVertexIndex >= 0 && endVertexIndex >= 0)
11 
{
12
if(G->kind == DIGRAPH)
13 
{
14
cur = G->vertexs[startVertexIndex]->firstarc,pre = NULL;
15
while(cur)
16 
{
17
if(cur->vertexIndex == endVertexIndex)
18 
{
19
break;
20 
}
21
pre = cur;
22
cur = cur->nextarc;
23 
}
24
if(NULL == cur)
25 
{
26
cout << "这两个结点之间没有弧！" << endl;
27
return ;
28 
}
29
else
30 
{
31
if(NULL == pre)
//是首节点
32
G->vertexs[startVertexIndex]->firstarc = cur->nextarc;
33
else
34
pre->nextarc = cur->nextarc;
35 
free(cur);
36
G->arcNum --;
37 
}
38 
}
39
else if(G->kind == UNDIGRAPH)
40 
{
41
cur = G->vertexs[startVertexIndex]->firstarc,pre = NULL;
42
while(cur)
43 
{
44
if(cur->vertexIndex == endVertexIndex)
45 
{
46
break;
47 
}
48
pre = cur;
49
cur = cur->nextarc;
50 
}
51
if(NULL == cur)
52 
{
53
cout << "这两个结点之间没有弧！" << endl;
54
return ;
55 
}
56
else
57 
{
58
if(NULL == pre)
//是首节点
59
G->vertexs[startVertexIndex]->firstarc = cur->nextarc;
60
else
61
pre->nextarc = cur->nextarc;
62 
free(cur);
63
//G->arcNum --;
64 
}
65
66
cur = G->vertexs[endVertexIndex]->firstarc,pre = NULL;
67
while(cur)
68 
{
69
if(cur->vertexIndex == startVertexIndex)
70 
{
71
break;
72 
}
73
pre = cur;
74
cur = cur->nextarc;
75 
}
76
if(NULL == cur)
77 
{
78
cout << "这两个结点之间没有弧！" << endl;
79
return ;
80 
}
81
else
82 
{
83
if(NULL == pre)
//是首节点
84
G->vertexs[endVertexIndex]->firstarc = cur->nextarc;
85
else
86
pre->nextarc = cur->nextarc;
87 
free(cur);
88
G->arcNum --;
89 
}
90 
}
91 
}
92
else
93 
{
94
cout << "起点或终点不存在！" << endl;
95
return ;
96 
}
97 }

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
182
183
184
185
186
187
188
189
190
191
192
 1 //初始条件：G存在，指定要删除弧连接的两个顶点
 2 void delArchFromGraph(Graph *&G,VertexType startData,VertexType endData)
 3 {
 4
ArchNode *cur,*pre;
 5
//先要找到start和end
 6
if(NULL == G)
 7
return;
 8
int startVertexIndex = findVertexIndexInGraph(G,startData);
 9
int endVertexIndex = findVertexIndexInGraph(G,endData);
10
if(startVertexIndex >= 0 && endVertexIndex >= 0)
11 
{
12
if(G->kind == DIGRAPH)
13 
{
14
cur = G->vertexs[startVertexIndex]->firstarc,pre = NULL;
15
while(cur)
16 
{
17
if(cur->vertexIndex == endVertexIndex)
18 
{
19
break;
20 
}
21
pre = cur;
22
cur = cur->nextarc;
23 
}
24
if(NULL == cur)
25 
{
26
cout << "这两个结点之间没有弧！" << endl;
27
return ;
28 
}
29
else
30 
{
31
if(NULL == pre)
//是首节点
32
G->vertexs[startVertexIndex]->firstarc = cur->nextarc;
33
else
34
pre->nextarc = cur->nextarc;
35 
free(cur);
36
G->arcNum --;
37 
}
38 
}
39
else if(G->kind == UNDIGRAPH)
40 
{
41
cur = G->vertexs[startVertexIndex]->firstarc,pre = NULL;
42
while(cur)
43 
{
44
if(cur->vertexIndex == endVertexIndex)
45 
{
46
break;
47 
}
48
pre = cur;
49
cur = cur->nextarc;
50 
}
51
if(NULL == cur)
52 
{
53
cout << "这两个结点之间没有弧！" << endl;
54
return ;
55 
}
56
else
57 
{
58
if(NULL == pre)
//是首节点
59
G->vertexs[startVertexIndex]->firstarc = cur->nextarc;
60
else
61
pre->nextarc = cur->nextarc;
62 
free(cur);
63
//G->arcNum --;
64 
}
65
66
cur = G->vertexs[endVertexIndex]->firstarc,pre = NULL;
67
while(cur)
68 
{
69
if(cur->vertexIndex == startVertexIndex)
70 
{
71
break;
72 
}
73
pre = cur;
74
cur = cur->nextarc;
75 
}
76
if(NULL == cur)
77 
{
78
cout << "这两个结点之间没有弧！" << endl;
79
return ;
80 
}
81
else
82 
{
83
if(NULL == pre)
//是首节点
84
G->vertexs[endVertexIndex]->firstarc = cur->nextarc;
85
else
86
pre->nextarc = cur->nextarc;
87 
free(cur);
88
G->arcNum --;
89 
}
90 
}
91 
}
92
else
93 
{
94
cout << "起点或终点不存在！" << endl;
95
return ;
96 
}
97 }

//深度优先遍历

复制代码

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
 1 //初始条件：图G存在
 2 void DFSdetails(const Graph *G,int i,int satusArr[])
 3 {
 4
ArchNode *cur;
 5
if(satusArr[i] == 1 )
 6
return;
 7
cout << G->vertexs[i]->data << " ";
 8
satusArr[i] = 1;
 9
cur = G->vertexs[i]->firstarc;
10
while(cur)
11 
{
12
DFSdetails(G,cur->vertexIndex,satusArr);
13
cur = cur->nextarc;
14 
}
15 }
16
17 void DFS(const Graph *G)
18 {
19
int satusArr[MAX_VERTEX_NUM] = {0};
20
cout << "深度优先遍历：";
21
if(NULL == G)
22
return;
23
for(int i = 0; i < G->vexNum; ++i)
24 
{
25 
DFSdetails(G,i,satusArr);
26 
}
27
cout << endl;
28 }