数据结构实验9：图的相关操作实验9

109 阅读 0 评论 72 点赞

我是靠谱客的博主糟糕玉米，最近开发中收集的这篇文章主要介绍数据结构实验9：图的相关操作实验9，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

实验9

姓名：学号：班级：

8.1 实验目的

(1) 掌握图的基本概念。

(2) 掌握图的存储结构的设计与实现，基本运算的实现。

(3) 熟练掌握图的两种遍历算法、遍历生成树及遍历算法的应用。

8.2 实验任务

分别设计图（网）的邻接矩阵、邻接表存储结构，编写算法实现下列问题的求解。、

数据要求：可利用8.3中的数据，也可自行编写数据。

1．打印出图（网）的两种遍历序列。

2．求给定图中的边（或弧）的数目。

3．对给定的图G及出发点v0，设计算法从V0出发深度优先遍历图G，并构造出相应的生成树或生成森林。

4．对给定的图G及出发点v0，设计算法从V0出发广度优先遍历图G，并构造出相应的生成树或生成森林。

8.3 实验说明

这里介绍一种从文本文件读入图的数据创建图的方法，这样我们可以按照指定的格式，先从容地准备好数据，然后由程序自动读入数据来创建图。

createGrpAdjMatrix.h，文件创建邻接矩阵表示的图。

createGrpAdjLinkedList.h，文件创建邻接表表示的图。

（以下给出的图的创建方法仅供参考，实验者可自行设计其它创建方法）

1. 数据文件格式设计

这里数据用文本文件保存，文件扩展名可自行指定，比如g8.grp，只要数据按文本文件格式读写即可。下面给出一种数据文件格式，其实读者可以自行设计图的数据文件格式。

①标识行1：Graph

标识这是一个图的数据文件，这一行也可以不要。

②标识行2：UDG、或UDN、或DG、或DN

这一行用来标识此图是无向图（UDG）、无向网（UDN）、有向图（DG）、还是有向网（DN）。

③顶点行

这一行将图中所有顶点列出，顶点之间用空格进行分割。这些顶点数据读出后存放到图的顶点数组中。

例如，图6-21(a)所示的图的顶点行数据为：a b c d。

图的各种算法都是用顶点的编号来引用顶点的，所以这一行顶点的排列顺序是很重要的，顶点的排列顺序决定了顶点的编号。比如上例中，顶点a、b、c、d对应的编号就为1、2、3、4。

④边数据行

一条边一行，边的2个顶点之间用空格分割。如果是网，每一行再加边的权值，也以空格分割。如果是无向图和无向网，每条边会重复一次。

例如图6-18(a)无向图的边的数据为：

a b

a c

a d

b a

b c

c a

c b

c d

d a

d c

图6-21(a)无向网边的数据为：

a b 4

a c 5

a d 3

b a 4

b c 2

c a 5

c b 2

c d 6

d a 3

d c 6

⑤其它行

如果程序强大一点，还可以在文件中加注释行，允许出现空行等，当然这是非必须的。

举一个完整的图的数据文件的例子，对图6-18(a)的无向图，完整的数据文件如下：

//文件可以加注释行，注释以“//”开始

//Graph为图标志，否则判定格式不对

//标志行后，第一行为图的类型。UDG--无向图；UDN--无向网；DG--有向图；DN--有向网

//标志行后，第二行为顶点元素

//顶点行以下图的边或弧。用顶点表示，第一列为起始顶点；第二列为邻接点；在网中再增加一列表示权值。

//本图具有4个顶点5条边

//下一行为图的标识行

Graph

//图的类型标识，此为无向图

UDG

//顶点元素数据

a b c d

//以下为边的数据，共10行数据，表示5条边

a b

a c

a d

b a

b c

c a

c b

c d

d a

d c

文件名不妨叫做Gudg4.grp。

再举一个有向网的例子，对图6-22所示的有向网，完整的数据文件如下：

图1 一个有向网实例

//标识为图数据

Graph

//标识有向网

//顶点数据

a b c d e f g h i j

//以下为边数据，共15条边

a b 2

a d 20

b e 1

c a 3

d c 8

d f 6

d g 4

e c 7

e h 3

f c 1

g h 1

h f 2

h j 2

i g 2

j i 1

不妨设文件名为Gdn10.grp

2. 从数据文件创建邻接矩阵表示的图

指定图的数据文件名，然后逐行读出数据并处理，自动创建邻接矩阵表示的图。本程序可以自动处理注释行和空行，程序实现如下：


1 //****************************文件创建图*****************************//

2 //* 函数功能：从文本文件创建邻接矩阵表示的图
*//

3 //* 入口参数
char fileName[]，文件名
*//

4 //* 出口参数：Graph &G，即创建的图
*//

5 //* 返回值：bool，true创建成功；false创建失败
*//

6 //* 函数名：CreateGraphFromFile(char fileName[], Graph &G)
*//

7 //*******************************************************************//

8 int CreateGraphFromFile(char fileName[], Graph &G)

9 {
 10
FILE* pFile;
//定义文件指针
 11
char str[1000];
//存放读出一行文本的字符串
 12
char strTemp[10];
//判断是否注释行
 13
cellType eWeight;
//边的信息，常为边的权值
 14
GraphKind graphType;
//图类型枚举变量
 15
pFile=fopen(fileName,"r");
 16
if(!pFile)
 17 
{
 18
printf("错误：文件%s打开失败。n",fileName);
 19
return false;
 20 
}
 21
while(fgets(str,1000,pFile)!=NULL)
 22 
{
 23
strLTrim(str);
//删除字符串左边空格，这是一个自定义的函数
 24
if (str[0]=='n')
//空行，继续读取下一行
 25
continue;
 26
strncpy(strTemp,str,2);
 27
if(strstr(strTemp,"//")!=NULL)
//跳过注释行
 28
continue;
 29
else
//非注释行、非空行，跳出循环
 30
break;
 31 
}
 32
//循环结束，str中应该已经是图的标识Graph，判断标识是否正确
 33
if(strstr(str,"Graph")==NULL)
 34 
{
 35
printf("错误：打开的文件格式错误！n");
 36
fclose(pFile); //关闭文件
 37
return false;
 38 
}
 39
//读取图的类型，跳过空行
 40
while(fgets(str,1000,pFile)!=NULL)
 41 
{
 42
strLTrim(str);
//删除字符串左边空格，这是一个自定义函数
 43
if (str[0]=='n')
//空行，继续读取下一行
 44
continue;
 45
strncpy(strTemp,str,2);
 46
if(strstr(strTemp,"//")!=NULL)
//注释行，跳过，继续读取下一行
 47
continue;
 48
else
//非空行，也非注释行，即图的类型标识
 49
break;
 50 
}
 51
//设置图的类型
 52
if(strstr(str,"UDG"))
 53
graphType=UDG;
//无向图
 54
else if(strstr(str,"UDN"))
 55
graphType=UDN;
//无向网
 56
else if(strstr(str,"DG"))
 57
graphType=DG;
//有向图
 58
else if(strstr(str,"DN"))
 59
graphType=DN;
//有向网
 60
else
 61 
{
 62
printf("错误：读取图的类型标记失败！n");
 63
fclose(pFile);
//关闭文件
 64
return false;
 65 
}
 66
//读取顶点行数据到str。跳过空行
 67
while(fgets(str,1000,pFile)!=NULL)
 68 
{
 69
strLTrim(str);
//删除字符串左边空格，这是一个自定义函数
 70
if (str[0]=='n')
//空行，继续读取下一行
 71
continue;
 72
strncpy(strTemp,str,2);
 73
if(strstr(strTemp,"//")!=NULL)
//注释行，跳过，继续读取下一行
 74
continue;
 75
else
//非空行，也非注释行，即图的顶点元素行
 76
break;
 77 
}
 78
 79
//顶点数据放入图的顶点数组

 80
char* token=strtok(str," ");
 81
int nNum=0;
 82
while(token!=NULL)
 83 
{
 84
G.Data[nNum]=*token;
 85
token = strtok( NULL, " ");
 86
nNum++;
 87 
}
 88
//图的邻接矩阵初始化
 89
int nRow=0;
//矩阵行下标
 90
int nCol=0;
//矩阵列下标
 91
if(graphType==UDG || graphType==DG)
 92 
{
 93
for(nRow=0;nRow<nNum;nRow++)
 94
for(nCol=0;nCol<nNum;nCol++)
 95
G.AdjMatrix[nRow][nCol]=0;
 96 
}
 97
else
 98 
{
 99
for(nRow=0;nRow<nNum;nRow++)
100
for(nCol=0;nCol<nNum;nCol++)
101
G.AdjMatrix[nRow][nCol]=INF;
//INF表示无穷大
102 
}
103
//循环读取边的数据到邻接矩阵
104
int edgeNum=0;
//边的数量
105
elementType Nf, Ns;
//边或弧的2个相邻顶点
106
while(fgets(str,1000,pFile)!=NULL)
107 
{
108
strLTrim(str);
//删除字符串左边空格，这是一个自定义函数
109
if (str[0]=='n')
//空行，继续读取下一行
110
continue;
111
strncpy(strTemp,str,2);
112
if(strstr(strTemp,"//")!=NULL)
//注释行，跳过，继续读取下一行
113
continue;
114
char* token=strtok(str," ");
//以空格为分隔符，分割一行数据，写入邻接矩阵
115
if(token==NULL)
//分割为空串，失败退出
116 
{
117
printf("错误：读取图的边数据失败！n");
118
fclose(pFile);
//关闭文件
119
return false;
120 
}
121
Nf=*token;
//获取边的第一个顶点
122
token = strtok( NULL, " ");
//读取下一个子串，即第二个顶点
123
if(token==NULL)
//分割为空串，失败退出
124 
{
125
printf("错误：读取图的边数据失败！n");
126
fclose(pFile);
//关闭文件
127
return false;
128 
}
129
Ns=*token;
//获取边的第二个顶点
130
//从第一个顶点获取行号

131
for(nRow=0;nRow<nNum;nRow++)
132 
{
133
if(G.Data[nRow]==Nf)
//从顶点列表找到第一个顶点的编号
134
break;
135 
}
136
//从第二个顶点获取列号
137
for(nCol=0;nCol<nNum;nCol++)
138 
{
139
if(G.Data[nCol]==Ns)
//从顶点列表找到第二个顶点的编号
140
break;
141 
}
142
//如果为网，读取权值
143
if(graphType==UDN || graphType==DN)
144
{
//读取下一个子串，即边的附加信息，常为边的权重
145
token = strtok( NULL, " ");
146
if(token==NULL)
//分割为空串，失败退出
147 
{
148
printf("错误：读取图的边数据失败！n");
149
fclose(pFile);
//关闭文件
150
return false;
151 
}
152
eWeight=atoi(token);
//取得边的附加信息
153 
}
154
if(graphType==UDN || graphType==DN)
155
G.AdjMatrix[nRow][nCol]=eWeight;
156 //如果为网，邻接矩阵中对应的边设置权值，否则置为1
157
else
158
G.AdjMatrix[nRow][nCol]=1;
159
edgeNum++;
//边数加1
160 
}
161
G.VerNum=nNum;
//图的顶点数
162
if(graphType==UDG || graphType==UDN)
163
G.ArcNum=edgeNum / 2;
//无向图或网的边数等于统计的数字除2

164
else
165
G.ArcNum=edgeNum;
166
G.gKind=graphType;
//图的类型
167
fclose(pFile);
//关闭文件
168
return true;
169 }

3. 从数据文件创建邻接表表示的图

程序实现如下：


1 //****************************文件创建图*****************************//

2 //* 函数功能：从文本文件创建邻接表表示的图
*//

3 //* 入口参数
char fileName[]，文件名
*//

4 //* 出口参数：Graph &G，即创建的图
*//

5 //* 返回值：bool，true创建成功；false创建失败
*//

6 //* 函数名：CreateGraphFromFile(char fileName[], Graph &G)
*//

7 //* 备注：本函数使用的数据文件格式以边（顶点对）为基本数据
*//

8 //*******************************************************************//

9 int CreateGraphFromFile(char fileName[], Graph &G)
 10 {
 11
FILE* pFile;
//定义文件指针
 12
char str[1000];
//存放读出一行文本的字符串
 13
char strTemp[10];
//判断是否注释行
 14
char* ss;
 15 int i=0, j=0;
 16
int edgeNum=0;
//边的数量
 17
eInfoType eWeight;
//边的信息，常为边的权值
 18
GraphKind graphType;
//图类型枚举变量
 19
pFile=fopen(fileName,"r");
 20
if(!pFile)
 21 
{
 22
printf("错误：文件%s打开失败。n",fileName);
 23
return false;
 24 
}
 25
while(fgets(str,1000,pFile)!=NULL)
//跳过空行和注释行
 26 
{
 27
strLTrim(str);
//删除字符串左边空格，这是一个自定义函数
 28
if (str[0]=='n')
//空行，继续读取下一行
 29
continue;
 30
strncpy(strTemp,str,2);
 31
if(strstr(strTemp,"//")!=NULL)
//跳过注释行
 32
continue;
 33
else
//非注释行、非空行，跳出循环
 34
break;
 35 
}
 36
//循环结束，str中应该已经是图的标识Graph，判断标识是否正确
 37
if(strstr(str,"Graph")==NULL)
 38 
{
 39
printf("错误：打开的文件格式错误！n");
 40
fclose(pFile);
//关闭文件
 41
return false;
 42 
}
 43
//读取图的类型，跳过空行及注释行
 44
while(fgets(str,1000,pFile)!=NULL)
 45 
{
 46
strLTrim(str);
//删除字符串左边空格，这是一个自定义函数
 47
if (str[0]=='n')
//空行，继续读取下一行
 48
continue;
 49
strncpy(strTemp,str,2);
 50
if(strstr(strTemp,"//")!=NULL)
//注释行，跳过，继续读取下一行
 51
continue;
 52
else
//非空行，也非注释行，即图的类型标识
 53
break;
 54 
}
 55
//设置图的类型
 56
if(strstr(str,"UDG"))
 57
graphType=UDG;
//无向图
 58
else if(strstr(str,"UDN"))
 59
graphType=UDN;
//无向网
 60
else if(strstr(str,"DG"))
 61
graphType=DG;
//有向图
 62
else if(strstr(str,"DN"))
 63
graphType=DN;
//有向网
 64
else
 65 
{
 66
printf("错误：读取图的类型标记失败！n");
 67
fclose(pFile);
//关闭文件
 68
return false;
 69 
}
 70
//读取顶点数据到str。跳过空行
 71
while(fgets(str,1000,pFile)!=NULL)
 72 
{
 73
strLTrim(str);
//删除字符串左边空格，这是一个自定义函数
 74
if (str[0]=='n')
//空行，继续读取下一行
 75
continue;
 76
strncpy(strTemp,str,2);
 77
if(strstr(strTemp,"//")!=NULL)
//注释行，跳过，继续读取下一行
 78
continue;
 79
else
//非空行，也非注释行，即图的顶点元素行
 80
break;
 81 
}
 82
//顶点数据放入图的顶点数组

 83
char* token=strtok(str," ");
 84
int nNum=0;
 85
while(token!=NULL)
 86 
{
 87
G.VerList[nNum].data=*token;
 88
G.VerList[nNum].firstEdge=NULL;
 89 token = strtok( NULL, " ");
 90
nNum++;
 91 
}
 92
//循环读取边（顶点对）数据
 93
int nRow=0;
//矩阵行下标
 94
int nCol=0;
//矩阵列下标
 95
EdgeNode* eR;
//边链表尾指针
 96
EdgeNode* p;
 97
elementType Nf, Ns;
//边或弧的2个相邻顶点
 98
while(fgets(str,1000,pFile)!=NULL)
 99 
{
100
strLTrim(str);
//删除字符串左边空格，这是一个自定义函数
101
if (str[0]=='n')
//空行，继续读取下一行
102
continue;
103
strncpy(strTemp,str,2);
104
if(strstr(strTemp,"//")!=NULL)
//注释行，跳过，继续读取下一行
105
continue;
106
char* token=strtok(str," ");
//以空格为分隔符，分割一行数据
107
if(token==NULL)
//分割为空串，失败退出
108 
{
109
printf("错误：读取图的边数据失败！n");
110
fclose(pFile);
//关闭文件
111
return false;
112 
}
113
Nf=*token;
//获取边的第一个顶点
114
token = strtok( NULL, " ");
//读取下一个子串，即第二个顶点
115
if(token==NULL)
//分割为空串，失败退出
116 
{
117
printf("错误：读取图的边数据失败！n");
118
fclose(pFile);
//关闭文件
119
return false;
120 
}
121
Ns=*token;
//获取边的第二个顶点
122
//从第一个顶点获取行号
123
for(nRow=0;nRow<nNum;nRow++)
124 
{
125
if(G.VerList[nRow].data==Nf)
//从顶点列表找到第一个顶点的编号
126
break;
127 
}
128
//从第二个顶点获取列号
129
for(nCol=0;nCol<nNum;nCol++)
130 
{
131
if(G.VerList[nCol].data==Ns)
//从顶点列表找到第二个顶点的编号
132
break;
133 
}
134
//如果为网，读取权值
135
if(graphType==UDN || graphType==DN)
136
{
//读取下一个子串，即边的附加信息，常为边的权重
137
token = strtok( NULL, " ");
138
if(token==NULL)
//分割为空串，失败退出
139 
{
140
printf("错误：读取图的边数据失败！n");
141
fclose(pFile);
//关闭文件
142
return false;
143 
}
144
eWeight=atoi(token);
//取得边的附加信息，即权值
145 
}
146
eR=G.VerList[nRow].firstEdge;
147
while(eR!=NULL && eR->next!=NULL)
148 
{
149
eR=eR->next;
//后移边链表指针，直至尾节点
150 
}
151
p=new EdgeNode;
//申请一个边链表结点
152
p->adjVer=nCol+1;
//顶点的编号，从1开始
153
//边的附加信息（权值），对有权图保存权值，无权图为1
154 if(graphType==UDN || graphType==DN)
155
p->eInfo=eWeight;
156
else
157
p->eInfo=1;
158
p->next=NULL;
159
if(G.VerList[nRow].firstEdge==NULL)
160 
{
161
G.VerList[nRow].firstEdge=p;
162
eR=p;
163 
}
164
else
165 
{
166
eR->next=p;
167
eR=p;
//新的尾指针

168 
}
169
edgeNum++;
//边数加1
170 
}
171
G.VerNum=nNum;
//图的顶点数
172
if(graphType==UDG || graphType==UDN)
173
G.ArcNum=edgeNum / 2;
//无向图或网的边数等于统计的数字除2

174
else
175
G.ArcNum=edgeNum;
176
G.gKind=graphType;
//图的类型
177
fclose(pFile);
//关闭文件
178
return true;
179 }

4. 图的销毁

以邻接矩阵为存储结构的图，因为使用矩阵存储图的数据，不存在销毁（释放内存）问题。但是以邻接表为存储结构的图，由于在创建图的过程中使用malloc()函数或new操作符动态申请了内存，当这个图不再需要时，必须手工释放动态申请的内存，否则造成内存泄漏。下面给出一个销毁邻接表表示的图的程序。

　　8.4 运行截图

图2 运行结果

图3 运行结果

图4 遍历图dn10.grp

图5 求图dn10.grp的边数

图6 深度优先遍历图dn10.grp

图7 广度优先遍历图dn10.grp

图8 遍历森林ung114.grp

图9 求森林ung114.grp的边数

图10 深度优先遍历森林ung114.grp

图11 广度优先遍历森林ung114.grp

图12 遍历图ung8.grp

图13 求图ung8.grp的边数

图14 深度优先遍历图ung8.grp

图15 广度优先遍历图ung8.grp

部分测试数据与数据文件对照图：

数据文件dn10.grp：

//文件可以加注释行，注释以//开始，且必须顶头开始，不能有空格

//文件不能有空行

//Graph为图标志，否则判定格式不对

//标志行后，第一行为图的类型。UDG--无向图；UDN--无向网；DG--有向图；DN--有向网

//标志行后，第二行为顶点元素

//顶点行以下图的边或弧。用顶点表示，第一列以顶点编号排列；第二列为邻接点；在网中增加一列表示权值。

//此图为一个10个顶点、15条边的有向网。

//标识为图数据

Graph

//标识有向网

//顶点数据列表，对应的编号为1，2，3，4,...

a b c d e f g h i j

//以下为边数据，共15条边

a b 2

a d 20

b e 1

c a 3

d c 8

d f 6

d g 4

e c 7

e h 3

f c 1

g h 1

h f 2

h j 2

i g 2

j i 1

图16 数据dn10.grp对照图

数据文件ung114.grp：

//文件可以加注释行，注释以//开始，且必须顶头开始，不能有空格

//文件不能有空行

//Graph为图标志，否则判定格式不对

//标志行后，第一行为图的类型。UDG--无向图；UDN--无向网；DG--有向图；DN--有向网

//标志行后，第二行为顶点元素

//顶点行以下图的边或弧。用顶点表示，第一列以顶点编号排列；第二列为邻接点；在网中增加一列表示权值。

//此图为一个有11个顶点、9条边的非连通的无向图。

Graph

UDG

//下面为顶点列表，对应的编号为1，2，3，4,...

a b c d e f g h i j k

//以下为邻接点（边）信息

//第一连通分量

a b

a d

b a

b c

c b

c d

d a

d c

//第二连通分量

e f

f e

f g

g f

//第三连通分量

h i

h k

i h

i j

j i

k h

图17 数据ung114.grp对照图

数据文件udg8.grp：

//文件可以加注释行，注释以//开始，且必须顶头开始，不能有空格

//文件不能有空行

//Graph为图标志，否则判定格式不对

//标志行后，第一行为图的类型。UDG--无向图；UDN--无向网；DG--有向图；DN--有向网

//标志行后，第二行为顶点元素

//顶点行以下图的边或弧。用顶点表示，第一列以顶点编号排列；第二列为邻接点；在网中增加一列表示权值。

//此图为一个有8个顶点、9条边的无向图。

Graph

UDG

//下面为顶点列表，对应的编号为1，2，3，4,...

a b c d e f g h

//以下为邻接点（边）信息

a b

a c

b a

b d

b e

c a

c g

c h

d b

d f

e b

e f

f d

f e

g c

g h

h c

h g

图18 数据udg8.grp对照图

8.5 附源代码

　　严正声明：此部分代码完全非本人所写，而是某个不具名大佬的手笔。本人秉着方便学习、互相交流的精神将代码贴在此处，原作者如有异议，请联系本人，即刻删除。

　　头文件 vNode.h：

 1 #ifndef VNODE_H
 2 #define VNODE_H
 3
 4 class vNode
 5 {
 6 public:
 7
vNode(int r_id, char r_data);
 8
int id();
 9
char data();
10
bool flag1();
11
void T_flag1();
12
void F_flag1();
13
bool flag2();
14
void T_flag2();
15
void F_flag2();
16
bool flag3();
17
void T_flag3();
18
void F_flag3();
19
void clear_flag();
20
~vNode();
21 private:
22
int V_id;
23
char V_data;
24
bool V_flag1;
25
bool V_flag2;
26
bool V_flag3;
27 };
28
29 #endif

View Code

　　源文件 vNode.h：

 1 #include "pch.h"
 2
 3 #ifndef VNODE_CPP
 4 #define VNODE_CPP
 5
 6 #include "vNode.h"
 7
 8 vNode::vNode(int r_id, char r_data)
 9 {
10
this->V_id = r_id;
11
this->V_data = r_data;
12
this->V_flag1 = false;
13
this->V_flag2 = false;
14
this->V_flag3 = false;
15 }
16
17 int vNode::id()
18 {
19
return this->V_id;
20 }
21
22 char vNode::data()
23 {
24
return this->V_data;
25 }
26
27 bool vNode::flag1()
28 {
29
return this->V_flag1;
30 }
31
32 void vNode::T_flag1()
33 {
34
this->V_flag1 = true;
35 }
36
37 void vNode::F_flag1()
38 {
39
this->V_flag1 = false;
40 }
41
42 bool vNode::flag2()
43 {
44
return this->V_flag2;
45 }
46
47 void vNode::T_flag2()
48 {
49
this->V_flag2 = true;
50 }
51
52 void vNode::F_flag2()
53 {
54
this->V_flag2 = false;
55 }
56
57 bool vNode::flag3()
58 {
59
return this->V_flag3;
60 }
61
62 void vNode::T_flag3()
63 {
64
this->V_flag3 = true;
65 }
66
67 void vNode::F_flag3()
68 {
69
this->V_flag3 = false;
70 }
71
72 void vNode::clear_flag()
73 {
74
this->V_flag1 = false;
75
this->V_flag2 = false;
76
this->V_flag3 = false;
77 }
78
79
80 vNode::~vNode()
81 {
82 }
83
84 #endif

View Code

　　头文件 pch.h：

 1 #ifndef PCH_H
 2 #define PCH_H
 3
 4 // TODO: 添加要在此处预编译的标头
 5 #include <iostream>
 6 #include <fstream>
 7 #include <cstdlib>
 8 #include <cstring>
 9 #include <cctype>
10 #include <list>
11 #include <vector>
12 #include <stack>
13 #include <queue>
14
15 #endif //PCH_H

View Code

　　源文件 pch.cpp：

1 #include "pch.h"
2
3 #ifndef PCH_CPP
4 #define PCH_CPP
5
6
7
8 #endi

View Code

　　头文件 eNode.h：

 1 #ifndef ENODE_H
 2 #define ENODE_H
 3
 4 #include "vNode.cpp"
 5
 6 //#define INF 65535
 7
 8 class eNode
 9 {
10 public:
11
eNode(int r_id, vNode *v_begin, vNode *v_end, int r_len);
12
int id();
13
vNode *begin();
14
vNode *end();
15
int len();
16
bool flag1();
17
void T_flag1();
18
void F_flag1();
19
bool flag2();
20
void T_flag2();
21
void F_flag2();
22
bool flag3();
23
void T_flag3();
24
void F_flag3();
25
void clear_flag();
26
~eNode();
27 private:
28
int E_id;
29
vNode *E_begin;
30
vNode *E_end;
31
int E_len;
32
bool E_flag1;
33
bool E_flag2;
34
bool E_flag3;
35 };
36
37 #endif

View Code

　　源文件 eNode.cpp：

 1 #include "pch.h"
 2
 3 #ifndef ENODE_CPP
 4 #define ENODE_CPP
 5
 6 #include "eNode.h"
 7
 8 eNode::eNode(int r_id, vNode *v_begin, vNode *v_end, int r_len)
 9 {
10
this->E_id = r_id;
11
this->E_begin = v_begin;
12
this->E_end = v_end;
13
this->E_len = r_len;
14
this->E_flag1 = false;
15
this->E_flag2 = false;
16
this->E_flag3 = false;
17 }
18
19 int eNode::id()
20 {
21
return this->E_id;
22 }
23
24 vNode * eNode::begin()
25 {
26
return this->E_begin;
27 }
28
29 vNode * eNode::end()
30 {
31
return this->E_end;
32 }
33
34 int eNode::len()
35 {
36
return this->E_len;
37 }
38
39 bool eNode::flag1()
40 {
41
return this->E_flag1;
42 }
43
44 void eNode::T_flag1()
45 {
46
this->E_flag1 = true;
47 }
48
49 void eNode::F_flag1()
50 {
51
this->E_flag1 = false;
52 }
53
54 bool eNode::flag2()
55 {
56
return this->E_flag2;
57 }
58
59 void eNode::T_flag2()
60 {
61
this->E_flag2 = true;
62 }
63
64 void eNode::F_flag2()
65 {
66
this->E_flag2 = false;
67 }
68
69 bool eNode::flag3()
70 {
71
return this->E_flag3;
72 }
73
74 void eNode::T_flag3()
75 {
76
this->E_flag3 = true;
77 }
78
79 void eNode::F_flag3()
80 {
81
this->E_flag3 = false;
82 }
83
84 void eNode::clear_flag()
85 {
86
this->E_flag1 = false;
87
this->E_flag2 = false;
88
this->E_flag3 = false;
89 }
90
91
92 eNode::~eNode()
93 {
94 }
95
96 #endif

View Code

　　头文件 adjListNode.h：

 1 #ifndef ADJLISTNODE_H
 2 #define ADJLISTNODE_H
 3
 4 #include "vNode.cpp"
 5 #include "eNode.cpp"
 6
 7 class adjListNode
 8 {
 9 public:
10
adjListNode(vNode *r_v);
11
vNode *v();
12
std::list<eNode *> &eList();
13
void add_adj_e(eNode *r_e);
14
eNode *get_first_adj_e();
15
eNode *get_next_adj_e(eNode *e);
16
void clear();
17
~adjListNode();
18 private:
19
vNode *N_v;
20
std::list<eNode *> N_eList;
21 };
22
23 #endif

View Code

　　源文件 adjListNode.cpp：

 1 #include "pch.h"
 2
 3 #ifndef ADJLISTNODE_CPP
 4 #define ADJLISTNODE_CPP
 5
 6 #include "adjListNode.h"
 7
 8 adjListNode::adjListNode(vNode *r_v)
 9 {
10
this->N_v = r_v;
11 }
12
13 vNode * adjListNode::v()
14 {
15
return this->N_v;
16 }
17
18 std::list<eNode*>& adjListNode::eList()
19 {
20
// TODO: 在此处插入 return 语句
21
return this->N_eList;
22 }
23
24 void adjListNode::add_adj_e(eNode * r_e)
25 {
26
this->N_eList.push_back(r_e);
27 }
28
29 eNode * adjListNode::get_first_adj_e()
30 {
31
if (!this->N_eList.empty())
32 
{
33
return this->N_eList.front();
34 
}
35
return NULL;
36 }
37
38 eNode * adjListNode::get_next_adj_e(eNode * e)
39 {
40
std::list <eNode *>::iterator i = this->N_eList.begin();
41
while (i != this->N_eList.end())
42 
{
43
if (*i == e)
44 
{
45
++i;
46
break;
47 
}
48
i++;
49 
}
50
if (i != this->N_eList.end())
51 
{
52
return *i;
53 
}
54
return NULL;
55 }
56
57 void adjListNode::clear()
58 {
59
this->N_eList.clear();
60 }
61
62
63 adjListNode::~adjListNode()
64 {
65 }
66
67 #endif

View Code

　　头文件 graph.h：

 1 #include "pch.h"
 2
 3 #ifndef GRAPH_H
 4 #define GRAPH_H
 5
 6 #include "vNode.cpp"
 7 #include "eNode.cpp"
 8 #include "adjListNode.cpp"
 9
10 #ifndef MAX_V_NUM
11 #define MAX_V_NUM 40
12
13 #endif
14
15 class graph
16 {
17 public:
18 
graph();
19
graph(const char *fileName);
20
int init_list(void);
21
int dfsTraversal_l();
22
int dfsTraversal_l(vNode *V);
23
int dfs_l(vNode *V);
24
int bfsTraversal_l();
25
int bfsTraversal_l(vNode *V);
26
int bfs_l(vNode *V);
27
int dfsTraversal_t_l();
28
int dfsTraversal_t_l(vNode *V);
29
int dfs_t_l(vNode *V, std::list<vNode *>&Lv, std::list<eNode *>&Le);
30
int bfsTraversal_t_l();
31
int bfsTraversal_t_l(vNode *V);
32
int bfs_t_l(vNode *V, std::list<vNode *>&Lv, std::list<eNode *>&Le);
33
int get_Enum_l();
34
int Prim_l(vNode *V);
35
int Kruskal_l(void);
36
int Dijkstra_l(vNode *V);
37
int Floyd_l(void);
38
int AOV_l(void);
39
int AOE_l(void);
40
int dfsTraversal_m();
41
int dfs_m(vNode *V);
42
bool empty(void);
43
bool error(void);
44
vNode *getNode_for_data(const char n_data);
45
vNode *getNode_for_ID(const int id);
46
int clear_vFlag();
47
int clear_eFlag();
48
int clear_eFlag_l();
49
int coverGraph(const char *fileName);
50
int delete_G(void);
51
~graph();
52 private:
53
bool G_empty;
54
bool G_error;
55
bool G_U;
56
bool G_N;
57
int G_type;
58
int G_Vnum;
59
int G_Enum;
60
vNode *G_vList[MAX_V_NUM];
61
std::list<eNode *> G_eList;
62
eNode *G_adjMat[MAX_V_NUM][MAX_V_NUM];
63
std::list<adjListNode *> G_adjList;
64
std::list<adjListNode *> G_i_adjList;
65 };
66
67 #endif

View Code

　　源文件 graph.cpp：


1 #include "pch.h"

2

3 #ifndef GRAPH_CPP

4 #define GRAPH_CPP

5

6 #include "graph.h"

7

8 graph::graph()

9 {

10
this->G_empty = true;

11 }

12

13 graph::graph(const char *fileName)

14 {

15
int i;

16
int j;

17
i = 0;

18
while (i < MAX_V_NUM)

19 
{

20
this->G_vList[i] = NULL;

21
j = 0;

22
while (j < MAX_V_NUM)

23 
{

24
this->G_adjMat[i][j] = NULL;

25
j++;

26 
}

27
i++;

28 
}

29

30
this->coverGraph(fileName);

31 }

32

33 int graph::init_list(void)

34 {

35
int i;

36
adjListNode *pa = NULL;

37
std::list<eNode *>::iterator i_e;

38
std::list<adjListNode *>::iterator i_a;

39
std::list<adjListNode *>::iterator i_i_a;

40
i = 0;

41
while (i < this->G_Vnum)

42 
{

43
pa = new adjListNode(this->G_vList[i]);

44
if (pa != NULL)

45 
{

46
this->G_adjList.push_back(pa);

47 
}

48
pa = new adjListNode(this->G_vList[i]);

49
if (pa != NULL)

50 
{

51
this->G_i_adjList.push_back(pa);

52 
}

53
else

54 
{

55
return -1;

56 
}

57
i++;

58 
}

59
i_e = this->G_eList.begin();

60
while (i_e != this->G_eList.end())

61 
{

62
i_a = this->G_adjList.begin();

63
while (i_a != this->G_adjList.end())

64 
{

65
if ((*i_a)->v()->data() == (*i_e)->begin()->data())

66 
{

67
(*i_a)->add_adj_e(*i_e);

68
break;

69 
}

70
i_a++;

71 
}

72
i_i_a = this->G_i_adjList.begin();

73
while (i_i_a != this->G_i_adjList.end())

74 
{

75
if ((*i_i_a)->v()->data() == (*i_e)->end()->data())

76 
{

77
(*i_i_a)->add_adj_e(*i_e);

78
break;

79 
}

80
i_i_a++;

81 
}

82
if (i_a == this->G_adjList.end() || i_i_a == this->G_i_adjList.end())

83 
{

84
return -1;

85 
}

86
i_e++;

87 
}

88
return 0;

89 }

90

91 int graph::dfsTraversal_l()

92 {

93
int i;

94
std::cout << "深度优先遍历序列为:" << std::endl;

95
this->clear_vFlag();

96
i = 0;

97
while (i < this->G_Vnum)

98 
{

99
if (!this->G_vList[i]->flag1())
 100 
{
 101
dfs_l(this->G_vList[i]);
 102 
}
 103
i++;
 104 
}
 105
std::cout << std::endl;
 106
return 0;
 107 }
 108
 109 int graph::dfsTraversal_l(vNode * V)
 110 {
 111
int i;
 112
if (V == NULL)
 113 
{
 114
std::cout << "结点不存在!" << std::endl;
 115
return -1;
 116 
}
 117
std::cout << "深度优先遍历序列为:" << std::endl;
 118
this->clear_vFlag();
 119 
dfs_l(V);
 120
i = 0;
 121
while (i < this->G_Vnum)
 122 
{
 123
if (!this->G_vList[i]->flag1())
 124 
{
 125
dfs_l(this->G_vList[i]);
 126 
}
 127
i++;
 128 
}
 129
std::cout << std::endl;
 130
return 0;
 131 }
 132
 133 int graph::dfs_l(vNode *V)
 134 {
 135
std::list<adjListNode *>::iterator i_a;
 136
eNode *p_e;
 137
if (V == NULL)
 138 
{
 139
return -1;
 140 
}
 141
if (V->flag1())
 142 
{
 143
return 0;
 144 
}
 145
std::cout << V->data() << ' ';
 146
V->T_flag1();
 147
i_a = this->G_adjList.begin();
 148
while (i_a != this->G_adjList.end())
 149 
{
 150
if ((*i_a)->v() == V)
 151 
{
 152
break;
 153 
}
 154
i_a++;
 155 
}
 156
if (i_a == this->G_adjList.end())
 157 
{
 158
return -1;
 159 
}
 160
p_e = (*i_a)->get_first_adj_e();
 161
while (p_e != NULL)
 162 
{
 163
//std::cout << p_e->begin()->data() << ' ' << p_e->end()->data() << std::endl;
 164
dfs_l(p_e->end());
 165
p_e = (*i_a)->get_next_adj_e(p_e);
 166 
}
 167
return 0;
 168 }
 169
 170 int graph::bfsTraversal_l()
 171 {
 172
int i;
 173
std::cout << "广度优先遍历序列为:" << std::endl;
 174
this->clear_vFlag();
 175
i = 0;
 176
while (i < this->G_Vnum)
 177 
{
 178
if (!this->G_vList[i]->flag1())
 179 
{
 180
bfs_l(this->G_vList[i]);
 181 
}
 182
i++;
 183 
}
 184
std::cout << std::endl;
 185
return 0;
 186 }
 187
 188 int graph::bfsTraversal_l(vNode * V)
 189 {
 190
int i;
 191
if (V == NULL)
 192 
{
 193
std::cout << "结点不存在!" << std::endl;
 194
return -1;
 195 
}
 196
std::cout << "广度优先遍历序列为:" << std::endl;
 197
this->clear_vFlag();
 198 
bfs_l(V);
 199
i = 0;
 200
while (i < this->G_Vnum)
 201 
{
 202
if (!this->G_vList[i]->flag1())
 203 
{
 204
bfs_l(this->G_vList[i]);
 205 
}
 206
i++;
 207 
}
 208
std::cout << std::endl;
 209
return 0;
 210 }
 211
 212 int graph::bfs_l(vNode * V)
 213 {
 214
vNode *p;
 215
std::queue<vNode *> Q;
 216
std::list<adjListNode *>::iterator i_a;
 217
std::list<eNode *>::iterator i_e;
 218
if (V == NULL)
 219 
{
 220
return -1;
 221 
}
 222 
Q.push(V);
 223
while (!Q.empty())
 224 
{
 225
p = Q.front();
 226 
Q.pop();
 227
if (p->flag1())
 228 
{
 229
continue;
 230 
}
 231
std::cout << p->data() << ' ';
 232
p->T_flag1();
 233
i_a = this->G_adjList.begin();
 234
while (i_a != this->G_adjList.end())
 235 
{
 236
if ((*i_a)->v()->data() == p->data())
 237 
{
 238
break;
 239 
}
 240
i_a++;
 241 
}
 242
if (i_a == this->G_adjList.end())
 243 
{
 244
return -1;
 245 
}
 246
i_e = (*i_a)->eList().begin();
 247
while (i_e != (*i_a)->eList().end())
 248 
{
 249
if (!(*i_e)->end()->flag1())
 250 
{
 251
Q.push((*i_e)->end());
 252 
}
 253
i_e++;
 254 
}
 255 
}
 256
return 0;
 257 }
 258
 259 int graph::dfsTraversal_t_l()
 260 {
 261
int i;
 262
std::list<vNode*> Lv;
 263
std::list<eNode*> Le;
 264
std::list<vNode*>::iterator iv;
 265
std::list<eNode*>::iterator ie;
 266
std::cout << "深度优先遍历序列为:" << std::endl;
 267
this->clear_vFlag();
 268
i = 0;
 269
while (i < this->G_Vnum)
 270 
{
 271
if (!this->G_vList[i]->flag1())
 272 
{
 273
dfs_t_l(this->G_vList[i], Lv, Le);
 274 
}
 275
i++;
 276 
}
 277
std::cout << std::endl;
 278
std::cout << "深度优先遍历生成树(森林)如下:" << std::endl;
 279
std::cout << "点集:" << std::endl;
 280
iv = Lv.begin();
 281
while (iv != Lv.end())
 282 
{
 283
std::cout << (*iv)->data() << ' ';
 284
iv++;
 285 
}
 286
std::cout << std::endl;
 287
std::cout << "边集:" << std::endl;
 288
ie = Le.begin();
 289
while (ie != Le.end())
 290 
{
 291
std::cout << (*ie)->begin()->data();
 292
if (G_U)
 293 
{
 294
std::cout << '-';
 295 
}
 296
else
 297 
{
 298
std::cout << "->";
 299 
}
 300
std::cout << (*ie)->end()->data() << std::endl;
 301
ie++;
 302 
}
 303
std::cout << std::endl;
 304
return 0;
 305 }
 306
 307 int graph::dfsTraversal_t_l(vNode * V)
 308 {
 309
int i;
 310
std::list<vNode*> Lv;
 311
std::list<eNode*> Le;
 312
std::list<vNode*>::iterator iv;
 313
std::list<eNode*>::iterator ie;
 314
if (V == NULL)
 315 
{
 316
std::cout << "结点不存在!" << std::endl;
 317
return -1;
 318 
}
 319
std::cout << "深度优先遍历序列为:" << std::endl;
 320
this->clear_vFlag();
 321 
dfs_t_l(V, Lv, Le);
 322
i = 0;
 323
while (i < this->G_Vnum)
 324 
{
 325
if (!this->G_vList[i]->flag1())
 326 
{
 327
dfs_t_l(this->G_vList[i], Lv, Le);
 328 
}
 329
i++;
 330 
}
 331
std::cout << std::endl;
 332
std::cout << "深度优先遍历生成树(森林)如下:" << std::endl;
 333
std::cout << "点集:" << std::endl;
 334
iv = Lv.begin();
 335
while (iv != Lv.end())
 336 
{
 337
std::cout << (*iv)->data() << ' ';
 338
iv++;
 339 
}
 340
std::cout << std::endl;
 341
std::cout << "边集:" << std::endl;
 342
ie = Le.begin();
 343
while (ie != Le.end())
 344 
{
 345
std::cout << (*ie)->begin()->data();
 346
if (G_U)
 347 
{
 348
std::cout << '-';
 349 
}
 350
else
 351 
{
 352
std::cout << "->";
 353 
}
 354
std::cout << (*ie)->end()->data() << std::endl;
 355
ie++;
 356 
}
 357
std::cout << std::endl;
 358
return 0;
 359 }
 360
 361 int graph::dfs_t_l(vNode * V, std::list<vNode*>& Lv, std::list<eNode*>& Le)
 362 {
 363
std::list<adjListNode *>::iterator i_a;
 364
eNode *p_e;
 365
if (V == NULL)
 366 
{
 367
return -1;
 368 
}
 369
if (V->flag1())
 370 
{
 371 
Le.pop_back();
 372
return 0;
 373 
}
 374
std::cout << V->data() << ' ';
 375
V->T_flag1();
 376 
Lv.push_back(V);
 377
i_a = this->G_adjList.begin();
 378
while (i_a != this->G_adjList.end())
 379 
{
 380
if ((*i_a)->v() == V)
 381 
{
 382
break;
 383 
}
 384
i_a++;
 385 
}
 386
if (i_a == this->G_adjList.end())
 387 
{
 388
return -1;
 389 
}
 390
p_e = (*i_a)->get_first_adj_e();
 391
while (p_e != NULL)
 392 
{
 393
//std::cout << p_e->begin()->data() << ' ' << p_e->end()->data() << std::endl;
 394 
Le.push_back(p_e);
 395
dfs_t_l(p_e->end(), Lv, Le);
 396
p_e = (*i_a)->get_next_adj_e(p_e);
 397 
}
 398
return 0;
 399 }
 400
 401 int graph::bfsTraversal_t_l()
 402 {
 403
int i;
 404
std::list<vNode*> Lv;
 405
std::list<eNode*> Le;
 406
std::list<vNode*>::iterator iv;
 407
std::list<eNode*>::iterator ie;
 408
std::cout << "广度优先遍历序列为:" << std::endl;
 409
this->clear_vFlag();
 410
i = 0;
 411
while (i < this->G_Vnum)
 412 
{
 413
if (!this->G_vList[i]->flag1())
 414 
{
 415
bfs_t_l(this->G_vList[i], Lv, Le);
 416 
}
 417
i++;
 418 
}
 419
std::cout << std::endl;
 420
std::cout << "广度优先遍历生成树(森林)如下:" << std::endl;
 421
std::cout << "点集:" << std::endl;
 422
iv = Lv.begin();
 423
while (iv != Lv.end())
 424 
{
 425
std::cout << (*iv)->data() << ' ';
 426
iv++;
 427 
}
 428
std::cout << std::endl;
 429
std::cout << "边集:" << std::endl;
 430
ie = Le.begin();
 431
while (ie != Le.end())
 432 
{
 433
std::cout << (*ie)->begin()->data();
 434
if (G_U)
 435 
{
 436
std::cout << '-';
 437 
}
 438
else
 439 
{
 440
std::cout << "->";
 441 
}
 442
std::cout << (*ie)->end()->data() << std::endl;
 443
ie++;
 444 
}
 445
std::cout << std::endl;
 446
return 0;
 447 }
 448
 449 int graph::bfsTraversal_t_l(vNode * V)
 450 {
 451
int i;
 452
std::list<vNode*> Lv;
 453
std::list<eNode*> Le;
 454
std::list<vNode*>::iterator iv;
 455
std::list<eNode*>::iterator ie;
 456
if (V == NULL)
 457 
{
 458
std::cout << "结点不存在!" << std::endl;
 459
return -1;
 460 
}
 461
std::cout << "广度优先遍历序列为:" << std::endl;
 462
this->clear_vFlag();
 463 
bfs_t_l(V, Lv, Le);
 464
i = 0;
 465
while (i < this->G_Vnum)
 466 
{
 467
if (!this->G_vList[i]->flag1())
 468 
{
 469
bfs_t_l(this->G_vList[i], Lv, Le);
 470 
}
 471
i++;
 472 
}
 473
std::cout << std::endl;
 474
std::cout << "广度优先遍历生成树(森林)如下:" << std::endl;
 475
std::cout << "点集:" << std::endl;
 476
iv = Lv.begin();
 477
while (iv != Lv.end())
 478 
{
 479
std::cout << (*iv)->data() << ' ';
 480
iv++;
 481 
}
 482
std::cout << std::endl;
 483
std::cout << "边集:" << std::endl;
 484
ie = Le.begin();
 485
while (ie != Le.end())
 486 
{
 487
std::cout << (*ie)->begin()->data();
 488
if (G_U)
 489 
{
 490
std::cout << '-';
 491 
}
 492
else
 493 
{
 494
std::cout << "->";
 495 
}
 496
std::cout << (*ie)->end()->data() << std::endl;
 497
ie++;
 498 
}
 499
std::cout << std::endl;
 500
return 0;
 501 }
 502
 503 int graph::bfs_t_l(vNode * V, std::list<vNode*>& Lv, std::list<eNode*>& Le)
 504 {
 505
vNode *p;
 506
std::queue<vNode *> Q;
 507
std::list<adjListNode *>::iterator i_a;
 508
std::list<eNode *>::iterator i_e;
 509
if (V == NULL || V->flag1())
 510 
{
 511
return -1;
 512 
}
 513 
Q.push(V);
 514
V->T_flag1();
 515
while (!Q.empty())
 516 
{
 517
p = Q.front();
 518 
Q.pop();
 519
std::cout << p->data() << ' ';
 520 
Lv.push_back(p);
 521
i_a = this->G_adjList.begin();
 522
while (i_a != this->G_adjList.end())
 523 
{
 524
if ((*i_a)->v()->data() == p->data())
 525 
{
 526
break;
 527 
}
 528
i_a++;
 529 
}
 530
if (i_a == this->G_adjList.end())
 531 
{
 532
return -1;
 533 
}
 534
i_e = (*i_a)->eList().begin();
 535
while (i_e != (*i_a)->eList().end())
 536 
{
 537
if (!(*i_e)->end()->flag1())
 538 
{
 539
Q.push((*i_e)->end());
 540
(*i_e)->end()->T_flag1();
 541
Le.push_back(*i_e);
 542 
}
 543
i_e++;
 544 
}
 545 
}
 546
return 0;
 547 }
 548
 549 int graph::get_Enum_l()
 550 {
 551
int e_num = 0;
 552
std::list<adjListNode *>::iterator i_a = this->G_adjList.begin();
 553
while (i_a != this->G_adjList.end())
 554 
{
 555
e_num += (*i_a)->eList().size();
 556
i_a++;
 557 
}
 558
if (G_U)
 559 
{
 560
e_num /= 2;
 561 
}
 562
return e_num;
 563 }
 564
 565 int graph::Prim_l(vNode * V)
 566 {
 567
int i = 0;
 568
int num = 1;
 569
vNode *pv = NULL;
 570
eNode *pe = NULL;
 571
std::list<vNode *> V_l;
 572
std::list<vNode *>::iterator iv;
 573
std::list<eNode *> E_l;
 574
std::list<eNode *> E_l2;
 575
std::list<eNode *>::iterator ie;
 576
std::list<adjListNode *>::iterator ia;
 577
if (V == NULL)
 578 
{
 579
return -1;
 580 
}
 581
this->clear_vFlag();
 582 
V_l.push_back(V);
 583
while (E_l.size() < this->G_Vnum - 1)
 584 
{
 585
pv = V_l.back();
 586
pv->T_flag1();
 587
ie = E_l2.begin();
 588
while (ie != E_l2.end())
 589 
{
 590
if ((*ie)->end()->flag1())
 591 
{
 592
ie = E_l2.erase(ie);
 593 
}
 594
else
 595 
{
 596
ie++;
 597 
}
 598 
}
 599
ia = this->G_adjList.begin();
 600
while (ia != this->G_adjList.end())
 601 
{
 602
if ((*ia)->v()->data() == pv->data())
 603 
{
 604
break;
 605 
}
 606
ia++;
 607 
}
 608
if (ia == this->G_adjList.end())
 609 
{
 610
return -1;
 611 
}
 612
ie = (*ia)->eList().begin();
 613
while (ie != (*ia)->eList().end())
 614 
{
 615
if (!(*ie)->end()->flag1())
 616 
{
 617
E_l2.push_back(*ie);
 618 
}
 619
ie++;
 620 
}
 621
if (!E_l2.empty())
 622 
{
 623
ie = E_l2.begin();
 624
pe = (*ie);
 625
while (ie != E_l2.end())
 626 
{
 627
if ((*ie)->len() < pe->len())
 628 
{
 629
pe = (*ie);
 630 
}
 631
ie++;
 632 
}
 633 
}
 634
else
 635 
{
 636
break;
 637 
}
 638 
E_l.push_back(pe);
 639
V_l.push_back(pe->end());
 640 
}
 641
std::cout << "Prim算法:" << std::endl;
 642
std::cout << "起点:" << V->data() << std::endl;
 643
std::cout << "最小生成树如下:" << std::endl;
 644
std::cout << "点集:" << std::endl;
 645
iv = V_l.begin();
 646
while (iv != V_l.end())
 647 
{
 648
std::cout << (*iv)->data() << ' ';
 649
iv++;
 650 
}
 651
std::cout << std::endl;
 652
std::cout << "边集:" << std::endl;
 653
if (E_l.empty())
 654 
{
 655
std::cout << "null!" << std::endl;
 656 
}
 657
else
 658 
{
 659
ie = E_l.begin();
 660
while (ie != E_l.end())
 661 
{
 662
if (!this->G_U)
 663 
{
 664
std::cout << (*ie)->begin()->data() << "->" << (*ie)->end()->data() << ' ';
 665 
}
 666
else
 667 
{
 668
std::cout << (*ie)->begin()->data() << '-' << (*ie)->end()->data() << ' ';
 669 
}
 670
if (this->G_N)
 671 
{
 672
std::cout << "len:" << (*ie)->len();
 673 
}
 674
std::cout << std::endl;
 675
ie++;
 676 
}
 677 
}
 678
return 0;
 679 }
 680
 681 int graph::Kruskal_l(void)
 682 {
 683
int i;
 684
int low_f;
 685
int high_f;
 686
int V_f[MAX_V_NUM];
 687
std::list<eNode *> E_l;
 688
std::list<eNode *> E_l2;
 689
std::list<eNode *>::iterator ie;
 690
std::list<eNode *>::iterator ie2;
 691
std::list<adjListNode *>::iterator ia = this->G_adjList.begin();
 692
i = 0;
 693
while (i < this->G_Vnum)
 694 
{
 695
V_f[this->G_vList[i]->id()] = this->G_vList[i]->id();
 696
i++;
 697 
}
 698
while (ia != this->G_adjList.end())
 699 
{
 700
ie = (*ia)->eList().begin();
 701
while (ie != (*ia)->eList().end())
 702 
{
 703
ie2 = E_l2.begin();
 704
while (ie2 != E_l2.end() && (*ie)->len() > (*ie2)->len())
 705 
{
 706
ie2++;
 707 
}
 708
E_l2.insert(ie2, *ie);
 709
ie++;
 710 
}
 711
ia++;
 712 
}
 713
ie2 = E_l2.begin();
 714
while (ie2 != E_l2.end() && E_l.size() < this->G_Vnum - 1)
 715 
{
 716
if (V_f[(*ie2)->begin()->id()] != V_f[(*ie2)->end()->id()])
 717 
{
 718
E_l.push_back(*ie2);
 719
if ((*ie2)->begin()->id() < (*ie2)->end()->id())
 720 
{
 721
low_f = V_f[(*ie2)->begin()->id()];
 722
high_f = V_f[(*ie2)->end()->id()];
 723 
}
 724
else
 725 
{
 726
low_f = V_f[(*ie2)->end()->id()];
 727
high_f = V_f[(*ie2)->begin()->id()];
 728 
}
 729
i = 0;
 730
while (i < this->G_Vnum)
 731 
{
 732
if (V_f[i] == high_f)
 733 
{
 734
V_f[i] = low_f;
 735 
}
 736
//std::cout << V_f[i] << ' ';
 737
i++;
 738 
}
 739
//std::cout << std::endl;
 740
//std::cout << "low:" << low_f << std::endl;
 741
//std::cout << "high:" << high_f << std::endl;
 742 
}
 743
ie2++;
 744 
}
 745
std::cout << "Kruskal算法:" << std::endl;
 746
std::cout << "最小生成树如下:" << std::endl;
 747
std::cout << "点集:" << std::endl;
 748
i = 0;
 749
while (i < this->G_Vnum)
 750 
{
 751
std::cout << this->G_vList[i]->data() << ' ';
 752
//std::cout << "flag:" << V_f[i] << ' ';
 753
i++;
 754 
}
 755
std::cout << std::endl;
 756
std::cout << "边集:" << std::endl;
 757
if (E_l.empty())
 758 
{
 759
std::cout << "null!" << std::endl;
 760 
}
 761
else
 762 
{
 763
ie = E_l.begin();
 764
while (ie != E_l.end())
 765 
{
 766
if (!this->G_U)
 767 
{
 768
std::cout << (*ie)->begin()->data() << "->" << (*ie)->end()->data() << ' ';
 769 
}
 770
else
 771 
{
 772
std::cout << (*ie)->begin()->data() << '-' << (*ie)->end()->data() << ' ';
 773 
}
 774
if (this->G_N)
 775 
{
 776
std::cout << "len:" << (*ie)->len();
 777 
}
 778
std::cout << std::endl;
 779
ie++;
 780 
}
 781 
}
 782
return 0;
 783 }
 784
 785 int graph::Dijkstra_l(vNode * V)
 786 {
 787
int i;
 788
int j;
 789
int V_pathLen[MAX_V_NUM];
 790
vNode *pv;
 791
eNode *pe;
 792
vNode *V_prior[MAX_V_NUM];
 793
std::list<eNode *>::iterator ie;
 794
std::list<adjListNode *>::iterator ia;
 795
std::stack<char> S_ch;
 796
 797
if (V == NULL)
 798 
{
 799
return -1;
 800 
}
 801
 802
this->clear_vFlag();
 803
 804
i = 0;
 805
while (i < MAX_V_NUM)
 806 
{
 807
V_pathLen[i] = -1;
 808
V_prior[i] = NULL;
 809
i++;
 810 
}
 811
 812
V_pathLen[V->id()] = 0;
 813
V->T_flag1();
 814
pv = V;
 815
do
 816 
{
 817
pe = NULL;
 818
ia = this->G_adjList.begin();
 819
while (ia != this->G_adjList.end())
 820 
{
 821
if ((*ia)->v()->flag1())
 822 
{
 823
ie = (*ia)->eList().begin();
 824
while (ie != (*ia)->eList().end())
 825 
{
 826
if (!(*ie)->end()->flag1())
 827 
{
 828
if (pe == NULL ||
 829
pe->len() + V_pathLen[pe->begin()->id()] >
 830
(*ie)->len() + V_pathLen[(*ie)->begin()->id()])
 831 
{
 832
pe = *ie;
 833 
}
 834 
}
 835
ie++;
 836 
}
 837 
}
 838
ia++;
 839 
}
 840
if (pe != NULL)
 841 
{
 842
pe->end()->T_flag1();
 843
V_pathLen[pe->end()->id()] = V_pathLen[pe->begin()->id()] + pe->len();
 844
V_prior[pe->end()->id()] = pe->begin();
 845 
}
 846
} while (pe != NULL);
 847
std::cout << "Dijkstra算法:" << std::endl;
 848
std::cout << "起点:" << V->data() << std::endl;
 849
std::cout << "从起点至其他各结点的最短路径如下:" << std::endl;
 850
i = 0;
 851
while (i < this->G_Vnum)
 852 
{
 853
std::cout << V->data() << "->" << this->G_vList[i]->data() << ':';
 854
if (V_prior[i] != NULL)
 855 
{
 856
j = i;
 857
while (V_prior[j] != NULL)
 858 
{
 859
S_ch.push(this->getNode_for_ID(j)->data());
 860
j = V_prior[j]->id();
 861 
}
 862
std::cout << V->data();
 863
while (!S_ch.empty())
 864 
{
 865
std::cout << "->" << S_ch.top();
 866 
S_ch.pop();
 867 
}
 868
std::cout << " 路径长度:" << V_pathLen[i];
 869 
}
 870
else if (V_pathLen[i] == 0)
 871 
{
 872
std::cout << this->G_vList[i]->data();
 873
std::cout << " 路径长度:" << V_pathLen[i];
 874 
}
 875
else
 876 
{
 877
std::cout << "路径不存在!";
 878 
}
 879
std::cout << std::endl;
 880
i++;
 881 
}
 882
return 0;
 883 }
 884
 885 int graph::Floyd_l(void)
 886 {
 887
int i;
 888
int j;
 889
int k;
 890
int path_len[MAX_V_NUM][MAX_V_NUM];
 891
vNode *path[MAX_V_NUM][MAX_V_NUM];
 892
std::list<eNode *>::iterator ie;
 893
std::list<adjListNode *>::iterator ia;
 894
std::stack<char> S_ch;
 895
 896
i = 0;
 897
while (i < this->G_Vnum)
 898 
{
 899
j = 0;
 900
while (j < this->G_Vnum)
 901 
{
 902
path[i][j] = NULL;
 903
if (i == j)
 904 
{
 905
path_len[i][j] = 0;
 906 
}
 907
else
 908 
{
 909
path_len[i][j] = -1;
 910 
}
 911
j++;
 912 
}
 913
i++;
 914 
}
 915
 916
ia = this->G_adjList.begin();
 917
while (ia != this->G_adjList.end())
 918 
{
 919
ie = (*ia)->eList().begin();
 920
while (ie != (*ia)->eList().end())
 921 
{
 922
path[(*ie)->begin()->id()][(*ie)->end()->id()] = (*ie)->begin();
 923
path_len[(*ie)->begin()->id()][(*ie)->end()->id()] = (*ie)->len();
 924
ie++;
 925 
}
 926
ia++;
 927 
}
 928
 929
k = 0;
 930
while (k < this->G_Vnum)
 931 
{
 932
i = 0;
 933
while (i < this->G_Vnum)
 934 
{
 935
j = 0;
 936
while (j < this->G_Vnum)
 937 
{
 938
if (path[i][k] != NULL && path[k][j] != NULL && i != j)
 939 
{
 940
if (path[i][j] == NULL ||
 941
path_len[i][k] + path_len[k][j] < path_len[i][j])
 942 
{
 943
path[i][j] = this->G_vList[k];
 944
path_len[i][j] = path_len[i][k] + path_len[k][j];
 945 
}
 946 
}
 947
j++;
 948 
}
 949
i++;
 950 
}
 951
k++;
 952 
}
 953
 954
std::cout << "Floyd算法:" << std::endl;
 955
std::cout << "各对结点之间的最短路径如下:" << std::endl;
 956
i = 0;
 957
while (i < this->G_Vnum)
 958 
{
 959
j = 0;
 960
while (j < this->G_Vnum)
 961 
{
 962
std::cout << this->G_vList[i]->data() << "->" << this->G_vList[j]->data() << ':';
 963
if (path[i][j] != NULL)
 964 
{
 965
k = j;
 966
while (path[i][k] != NULL && k != i)
 967 
{
 968
S_ch.push(this->G_vList[k]->data());
 969
k = path[i][k]->id();
 970 
}
 971
if (k != i)
 972 
{
 973
std::cout << "路径不存在!";
 974 
}
 975
else
 976 
{
 977
std::cout << this->G_vList[i]->data();
 978
while (!S_ch.empty())
 979 
{
 980
std::cout << "->" << S_ch.top();
 981 
S_ch.pop();
 982 
}
 983
std::cout << " 路径长度:" << path_len[i][j];
 984 
}
 985 
}
 986
else
 987 
{
 988
if (i != j)
 989 
{
 990
std::cout << "路径不存在!";
 991 
}
 992
else
 993 
{
 994
std::cout << this->G_vList[i]->data();
 995
std::cout << " 路径长度:" << path_len[i][j];
 996 
}
 997 
}
 998
std::cout << std::endl;
 999
j++;
1000 
}
1001
i++;
1002 
}
1003
1004
1005
return 0;
1006 }
1007
1008 int graph::AOV_l(void)
1009 {
1010
int i;
1011
int deg_i[MAX_V_NUM];
1012
std::list<char> L_ch;
1013
vNode *pv;
1014
std::queue<vNode *> Q;
1015
std::list<adjListNode *>::iterator ia;
1016
std::list<eNode *>::iterator ie;
1017
1018
this->clear_vFlag();
1019
1020
i = 0;
1021
while (i < this->G_Vnum)
1022 
{
1023
deg_i[i] = 0;
1024
i++;
1025 
}
1026
1027
ia = this->G_adjList.begin();
1028
while (ia != this->G_adjList.end())
1029 
{
1030
ie = (*ia)->eList().begin();
1031
while (ie != (*ia)->eList().end())
1032 
{
1033
deg_i[(*ie)->end()->id()] += 1;
1034
ie++;
1035 
}
1036
ia++;
1037 
}
1038
1039
i = 0;
1040
while (i < this->G_Vnum)
1041 
{
1042
if (deg_i[i] == 0)
1043 
{
1044 
Q.push(getNode_for_ID(i));
1045 
}
1046
i++;
1047 
}
1048
1049
while (!Q.empty())
1050 
{
1051
pv = Q.front();
1052 
Q.pop();
1053
1054
pv->T_flag1();
1055
L_ch.push_back(pv->data());
1056
1057
ia = this->G_adjList.begin();
1058
while (ia != this->G_adjList.end())
1059 
{
1060
if ((*ia)->v() == pv)
1061 
{
1062
ie = (*ia)->eList().begin();
1063
while (ie != (*ia)->eList().end())
1064 
{
1065
deg_i[(*ie)->end()->id()] -= 1;
1066
if (deg_i[(*ie)->end()->id()] == 0 && !(*ie)->end()->flag1())
1067 
{
1068
Q.push((*ie)->end());
1069 
}
1070
ie++;
1071 
}
1072 
}
1073
ia++;
1074 
}
1075 
}
1076
1077
if (L_ch.size() < this->G_Vnum)
1078 
{
1079
std::cout << "该图无拓扑序列!" << std::endl;
1080 
}
1081
else
1082 
{
1083
std::cout << "该图的拓扑序列为:";
1084
while (!L_ch.empty())
1085 
{
1086
std::cout << L_ch.front() << ' ';
1087 
L_ch.pop_front();
1088 
}
1089
std::cout << std::endl;
1090 
}
1091
1092
return 0;
1093 }
1094
1095 int graph::AOE_l(void)
1096 {
1097
int i;
1098
int j;
1099
int len = 0;
1100
int deg_i[MAX_V_NUM];
1101
int deg_o[MAX_V_NUM];
1102
int minLs[MAX_V_NUM];
1103
int minLe[MAX_V_NUM];
1104
int maxLs[MAX_V_NUM];
1105
int maxLe[MAX_V_NUM];
1106
vNode *prior[MAX_V_NUM];
1107
vNode *pv;
1108
eNode *pe;
1109
std::list<vNode *> L;
1110
std::list<vNode *> path;
1111
std::list<vNode *>::iterator iv;
1112
std::list<adjListNode *>::iterator ia;
1113
std::list<eNode *>::iterator ie;
1114
1115
this->clear_vFlag();
1116
this->clear_eFlag_l();
1117
1118
i = 0;
1119
while (i < this->G_Vnum)
1120 
{
1121
prior[i] = NULL;
1122
deg_i[i] = 0;
1123
deg_o[i] = 0;
1124
minLs[i] = 0;
1125
minLe[i] = 0;
1126
maxLs[i] = 0;
1127
maxLe[i] = 0;
1128
i++;
1129 
}
1130
1131
ia = this->G_adjList.begin();
1132
while (ia != this->G_adjList.end())
1133 
{
1134
ie = (*ia)->eList().begin();
1135
while (ie != (*ia)->eList().end())
1136 
{
1137
deg_i[(*ie)->end()->id()] += 1;
1138
deg_o[(*ie)->begin()->id()] += 1;
1139
ie++;
1140 
}
1141
ia++;
1142 
}
1143
1144
i = 0;
1145
while (i < this->G_Vnum)
1146 
{
1147
if (deg_i[i] == 0)
1148 
{
1149
minLs[i] = 0;
1150 
L.push_back(getNode_for_ID(i));
1151
getNode_for_ID(i)->T_flag1();
1152 
}
1153
i++;
1154 
}
1155
1156
while (!L.empty())
1157 
{
1158
iv = L.begin();
1159
while (iv != L.end())
1160 
{
1161
maxLe[(*iv)->id()] = len;
1162
iv++;
1163 
}
1164
1165
pe = NULL;
1166
iv = L.begin();
1167
while (iv != L.end())
1168 
{
1169
ia = this->G_adjList.begin();
1170
while (ia != this->G_adjList.end())
1171 
{
1172
if ((*ia)->v() == (*iv))
1173 
{
1174
ie = (*ia)->eList().begin();
1175
while (ie != (*ia)->eList().end())
1176 
{
1177
if (!(*ie)->flag1())
1178 
{
1179
if (pe == NULL ||
1180
pe->len() - (maxLe[pe->begin()->id()] - minLs[pe->begin()->id()]) >
1181
(*ie)->len() - (maxLe[(*ie)->begin()->id()] - minLs[(*ie)->begin()->id()]))
1182 
{
1183
pe = *ie;
1184 
}
1185 
}
1186
ie++;
1187 
}
1188
break;
1189 
}
1190
ia++;
1191 
}
1192
iv++;
1193 
}
1194
1195
if (pe != NULL)
1196 
{
1197
//std::cout << pe->begin()->data() << "->" << pe->end()->data() << std::endl;
1198
1199
len += pe->len() - (maxLe[pe->begin()->id()] - minLs[pe->begin()->id()]);
1200
deg_i[pe->end()->id()] -= 1;
1201
deg_o[pe->begin()->id()] -= 1;
1202
pe->T_flag1();
1203
1204
1205
if (deg_o[pe->begin()->id()] == 0)
1206 
{
1207
iv = L.begin();
1208
while (iv != L.end())
1209 
{
1210
if ((*iv) == pe->begin())
1211 
{
1212
break;
1213 
}
1214
iv++;
1215 
}
1216
(*iv)->T_flag2();
1217
maxLe[(*iv)->id()] = len;
1218
//std::cout << (*iv)->data() << ' ';
1219 
L.erase(iv);
1220 
}
1221
1222
if (deg_i[pe->end()->id()] == 0)
1223 
{
1224
if (!pe->end()->flag1())
1225 
{
1226
minLs[pe->end()->id()] = len;
1227
prior[pe->end()->id()] = pe->begin();
1228
if (deg_o[pe->end()->id()] != 0)
1229 
{
1230
L.push_back(pe->end());
1231 
}
1232
else
1233 
{
1234
if (!pe->end()->flag2())
1235 
{
1236
maxLe[pe->end()->id()] = len + pe->len();
1237
pe->end()->T_flag2();
1238 
}
1239 
}
1240
pe->end()->T_flag1();
1241 
}
1242 
}
1243 
}
1244
else
1245 
{
1246
break;
1247 
}
1248 
}
1249
1250
i = 0;
1251
j = 0;
1252
while (i < this->G_Vnum)
1253 
{
1254
//std::cout << maxLe[i] << std::endl;
1255
if (maxLe[i] > maxLe[j])
1256 
{
1257
j = i;
1258 
}
1259
i++;
1260 
}
1261
1262
i = 0;
1263
while (i < this->G_Vnum)
1264 
{
1265
if (!this->G_vList[i]->flag2())
1266 
{
1267
std::cout << "该图不存在关键路径!" << std::endl;
1268
return 0;
1269 
}
1270
i++;
1271 
}
1272
1273
pv = getNode_for_ID(j);
1274
while (pv != NULL)
1275 
{
1276 
path.push_front(pv);
1277
pv = prior[pv->id()];
1278 
}
1279
std::cout << "该图的关键路径为:" << std::endl;
1280
iv = path.begin();
1281
while (iv != path.end())
1282 
{
1283
std::cout << (*iv)->data();
1284
++iv;
1285
if (iv != path.end())
1286 
{
1287
std::cout << "->";
1288 
}
1289 
}
1290
std::cout << std::endl;
1291
std::cout << "关键路径的长度为:" << maxLe[j] << std::endl;
1292
1293
return 0;
1294 }
1295
1296 bool graph::empty(void)
1297 {
1298
return this->G_empty;
1299 }
1300
1301 bool graph::error(void)
1302 {
1303
return this->G_error;
1304 }
1305
1306 vNode * graph::getNode_for_data(const char n_data)
1307 {
1308
int i = 0;
1309
while (i < this->G_Vnum)
1310 
{
1311
if (this->G_vList[i] != NULL && this->G_vList[i]->data() == n_data)
1312 
{
1313
break;
1314 
}
1315
i++;
1316 
}
1317
if (i >= this->G_Vnum)
1318 
{
1319
return NULL;
1320 
}
1321
return this->G_vList[i];
1322 }
1323
1324 vNode * graph::getNode_for_ID(const int id)
1325 {
1326
if (id >= 0 && id < this->G_Vnum)
1327 
{
1328
return this->G_vList[id];
1329 
}
1330
return NULL;
1331 }
1332
1333 int graph::clear_vFlag()
1334 {
1335
int i = 0;
1336
while (i < this->G_Vnum)
1337 
{
1338
this->G_vList[i]->clear_flag();
1339
i++;
1340 
}
1341
return 0;
1342 }
1343
1344 int graph::clear_eFlag()
1345 {
1346
std::list<eNode *>::iterator ie = this->G_eList.begin();
1347
while (ie != this->G_eList.end())
1348 
{
1349
(*ie)->clear_flag();
1350
ie++;
1351 
}
1352
return 0;
1353 }
1354
1355 int graph::clear_eFlag_l()
1356 {
1357
std::list<adjListNode *>::iterator ia = this->G_adjList.begin();
1358
std::list<eNode *>::iterator ie;
1359
while (ia != this->G_adjList.end())
1360 
{
1361
ie = (*ia)->eList().begin();
1362
while (ie != (*ia)->eList().end())
1363 
{
1364
(*ie)->clear_flag();
1365
ie++;
1366 
}
1367
ia++;
1368 
}
1369
return 0;
1370 }
1371
1372 int graph::coverGraph(const char * fileName)
1373 {
1374
bool error = false;
1375
bool typeLine = false;
1376
bool nodeLine = false;
1377
bool eLine = false;
1378
int elen;
1379
int vID = 0;
1380
int eID = 0;
1381
char ch_a;
1382
char ch_b;
1383
char str[256];
1384
vNode *pv = NULL;
1385
eNode *pe = NULL;
1386 
std::ifstream fra;
1387
int ia;
1388
int ib;
1389
this->delete_G();
1390 
fra.open(fileName);
1391
if (!fra.good())
1392 
{
1393
this->G_error = true;
1394
return -3;
1395 
}
1396
while (fra.good())
1397 
{
1398
fra >> str;
1399
//std::cout << eID << '-';
1400
//std::cout << str << std::endl;
1401
if (strlen(str) == 0)
1402 
{
1403
continue;
1404 
}
1405
if (strncmp(str, "//", 2) == 0)
1406 
{
1407
fra.getline(str, 255);
1408
continue;
1409 
}
1410
if (!typeLine && !nodeLine && !eLine)
1411 
{
1412
if (strcmp(str, "Graph") == 0)
1413 
{
1414
typeLine = true;
1415
continue;
1416 
}
1417 
}
1418
if (typeLine)
1419 
{
1420
if (strcmp(str, "UDG") == 0)
1421 
{
1422
this->G_U = true;
1423
this->G_N = false;
1424 
}
1425
else
1426 
{
1427
if (strcmp(str, "DG") == 0)
1428 
{
1429
this->G_U = false;
1430
this->G_N = false;
1431 
}
1432
else
1433 
{
1434
if (strcmp(str, "UDN") == 0)
1435 
{
1436
this->G_U = true;
1437
this->G_N = true;
1438 
}
1439
else
1440 
{
1441
if (strcmp(str, "DN") == 0)
1442 
{
1443
this->G_U = false;
1444
this->G_N = true;
1445 
}
1446
else
1447 
{
1448
error = true;
1449
break;
1450 
}
1451 
}
1452 
}
1453 
}
1454
typeLine = false;
1455
nodeLine = true;
1456
continue;
1457 
}
1458
if (nodeLine)
1459 
{
1460
ch_a = str[0];
1461
this->G_vList[vID] = new vNode(vID, ch_a);
1462
if (G_vList[vID] == NULL)
1463 
{
1464
error = true;
1465
break;
1466 
}
1467
vID += 1;
1468
if (!fra.good())
1469 
{
1470
error = true;
1471
break;
1472 
}
1473
ch_a = fra.get();
1474
while (ch_a != 'n')
1475 
{
1476
//std::cout << ch_a << ' ';
1477
if (!isspace(ch_a))
1478 
{
1479
this->G_vList[vID] = new vNode(vID, ch_a);
1480
if (G_vList[vID] == NULL)
1481 
{
1482
error = true;
1483
break;
1484 
}
1485
vID += 1;
1486 
}
1487
if (!fra.good())
1488 
{
1489
error = true;
1490
break;
1491 
}
1492
ch_a = fra.get();
1493 
}
1494
//std::cout << std::endl;
1495
if (error)
1496 
{
1497
break;
1498 
}
1499
this->G_Vnum = vID;
1500
nodeLine = false;
1501
eLine = true;
1502
continue;
1503 
}
1504
if (eLine)
1505 
{
1506
ch_a = str[0];
1507
if (!fra.good())
1508 
{
1509
error = true;
1510
break;
1511 
}
1512
fra >> ch_b;
1513
if (this->G_N)
1514 
{
1515
if (!fra.good())
1516 
{
1517
error = true;
1518
break;
1519 
}
1520
fra >> elen;
1521 
}
1522
else
1523 
{
1524
elen = 1;
1525 
}
1526
//std::cout << ch_a << ' ' << ch_b << ' ' << elen << std::endl;
1527
ia = 0;
1528
while (ia < this->G_Vnum)
1529 
{
1530
if (this->G_vList[ia]->data() == ch_a)
1531 
{
1532
break;
1533 
}
1534
ia++;
1535 
}
1536
ib = 0;
1537
while (ib < this->G_Vnum)
1538 
{
1539
if (this->G_vList[ib]->data() == ch_b)
1540 
{
1541
break;
1542 
}
1543
ib++;
1544 
}
1545
if (ia >= G_Vnum || ib >= G_Vnum)
1546 
{
1547
error = true;
1548
break;
1549 
}
1550
//std::cout << eID << std::endl;
1551
pe = new eNode(eID, this->G_vList[ia], this->G_vList[ib], elen);
1552
eID += 1;
1553
if (pe != NULL)
1554 
{
1555
this->G_adjMat[ia][ib] = pe;
1556
this->G_eList.push_back(pe);
1557 
}
1558
else
1559 
{
1560
error = true;
1561
break;
1562 
}
1563 
}
1564
str[0] = '';
1565 
}
1566 
fra.close();
1567
1568
if (error)
1569 
{
1570
this->G_error = true;
1571
return -4;
1572 
}
1573
1574
this->G_Enum = eID;
1575
if (this->G_U)
1576 
{
1577
this->G_Enum /= 2;
1578 
}
1579
1580
if (this->init_list() != 0)
1581 
{
1582
this->G_error = true;
1583
return -5;
1584 
}
1585
1586
this->G_empty = false;
1587
1588
return 0;
1589 }
1590
1591 int graph::delete_G(void)
1592 {
1593
int i;
1594
int j;
1595
1596
i = 0;
1597
while (i < MAX_V_NUM)
1598 
{
1599
if (this->G_vList[i] != NULL)
1600 
{
1601
delete this->G_vList[i];
1602
this->G_vList[i] = NULL;
1603 
}
1604
i++;
1605 
}
1606
1607
while (!this->G_eList.empty())
1608 
{
1609
delete this->G_eList.front();
1610
this->G_eList.pop_front();
1611 
}
1612
1613
while (!this->G_adjList.empty())
1614 
{
1615
delete this->G_adjList.front();
1616
this->G_adjList.pop_front();
1617 
}
1618
1619
while (!this->G_i_adjList.empty())
1620 
{
1621
delete this->G_i_adjList.front();
1622
this->G_i_adjList.pop_front();
1623 
}
1624
1625
i = 0;
1626
while (i < MAX_V_NUM)
1627 
{
1628
j = 0;
1629
while (j < MAX_V_NUM)
1630 
{
1631
this->G_adjMat[i][j] = NULL;
1632
j++;
1633 
}
1634
i++;
1635 
}
1636
1637
this->G_empty = true;
1638
1639
return 0;
1640 }
1641
1642 graph::~graph()
1643 {
1644
this->delete_G();
1645 }
1646
1647 #undef MAX_V_NUM
1648
1649 #endif

View Code

　　测试数据与数据文件对照图可以在这里下载：https://github.com/25thengineer/Data-structure-experiments-of-Hefei-University-of-Technology/tree/master/Exp9_Graph/grpData。

转载于:https://www.cnblogs.com/25th-engineer/p/10225101.html

最后

以上就是糟糕玉米为你收集整理的数据结构实验9：图的相关操作实验9的全部内容，希望文章能够帮你解决数据结构实验9：图的相关操作实验9所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：数据结构与算法
浏览次数：109 次浏览
发布日期：2023-12-09 18:00:35
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_6_f2_14__23__18_2.html

数据结构实验9：图的相关操作实验9

概述

实验9

8.1 实验目的

8.2 实验任务

8.3 实验说明

1. 数据文件格式设计

2. 从数据文件创建邻接矩阵表示的图

3. 从数据文件创建邻接表表示的图

4. 图的销毁

8.4 运行截图

8.5 附源代码

最后

评论列表共有 0 条评论

发表评论取消回复

数据结构实验9：图的相关操作实验9

概述

实验9

8.1 实验目的

8.2 实验任务

8.3 实验说明

1. 数据文件格式设计

2. 从数据文件创建邻接矩阵表示的图

3. 从数据文件创建邻接表表示的图

4. 图的销毁

8.4 运行截图

8.5 附源代码

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

　　8.4 运行截图

发表评论取消回复