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

74 阅读 0 评论 49 点赞

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

概述

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

 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 
初始条件：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 
初始条件：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 
初始条件：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 //初始条件：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 //初始条件：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 //初始条件：图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 }