一、实验内容
1．打印出图（网）的两种遍历序。
实验测试数据基本要求：
第一组数据： udg8.grp
第二组数据： udg115.grp
第三组数据： dg6.grp
第四组数据： f14.grp
2．求给定图中的边（或弧）的数目。 实验测试数据基本要求：第一组数据： udg8.grp
第二组数据： udg115.grp
第三组数据： dg6.grp
第四组数据： f14.grp
3．对给定的图G及出发点v0，设计算法从V0出发深度优先遍历图G，并构造出相应的生成树或生成森林。
实验测试数据基本要求：
第一组数据： udg8.grp
第二组数据： dg6.grp
第三组数据： udn8.grp
第四组数据： dn10.grp
4．对给定的图G及出发点v0，设计算法从V0出发广度优先遍历图G，并构造出相应的生成树或生成森林。
第一组数据： udg8.grp
第二组数据： dg6.grp
第三组数据： un8.grp
第四组数据： dn10.grp
5．实现Prim算法，求解下列给定图G的最小生成树。 实验测试数据基本要求：第一组数据： udn6.grp
第二组数据： un8.grp
6．实现Kruskal算法，求解下列给定图G的最小生成树。 实验测试数据基本要求：第一组数据： udn6.grp
第二组数据： un8.grp
7．实现Dijkstra算法，求解下列给定图G指定顶点到其余顶点之间的最短路径。 实验测试数据基本要求：第一组数据： udn6.grp
第二组数据： un8.grp
第三组数据： dn8.grp
第四组数据： dn10.grp
8．实现Floyd算法，求解下列给定图G各顶点之间的最短路径。 实验测试数据基本要求：第一组数据： udn6.grp
第二组数据： un8.grp
第三组数据： dn8.grp
第四组数据： dn10.grp
9．设计算法求解下列给定图G的拓扑序列。 实验测试数据基本要求：
第一组数据： top6dg1.grp
第二组数据： top7dg1.grp
第三组数据： dn8.grp
第四组数据： dn10.grp
10．设计算法求解下列给定AOE网的关键路径。 实验测试数据基本要求：
第一组数据： dn8.grp（测试数据有环）
第二组数据： dn10.grp（测试数据有环）
二、算法设计
（除书上给出的基本运算（这部分不必给出设计思想），其它实验内容要给出算法设计思想）
(1)打印出图（网）的两种遍历序。
深度遍历：
首先将所有顶点都初始化为未访问状态。然后选择一个起始顶点verID，从该顶点开始DFS。此连通分量DFS结束后，再检查是否所有连通分量都已经结束，若没有即visited[vID]==false,从当前顶点开始DFS。直到所有连通分量访问完毕。DFS函数中，首先访问该顶点，然后找到它的第一个邻接点，判断是否访问过，若没有则对他进行DFS。若访问过了找他的另外的邻接点。循环进行上面操作，循环退出条件为所有邻接点都已经访问过。
广度遍历：
首先将所有顶点都初始化为未访问状态。然后选择一个起始顶点verID，从该顶点开始BFS。此连通分量BFS结束后，再检查是否所有连通分量都已经结束，若没有即visited[vID]==false,从当前顶点开始BFS。直到所有连通分量访问完毕。BFS需要利用到队列。BFS函数中，首先访问该顶点，接着将其入队，当队列不空的时候，取队头出队，然后找到它的第一个邻接点，判断是否访问过，若没有则访问它，将他入队。若访问过了找他的另外的邻接点。循环进行上面操作，循环退出条件为所有邻接点都已经访问过。
为了便于操作，队列用数组模拟
(2)求给定图中的边（或弧）的数目。
改编深度遍历算法，每次头结点调用对弧长加一，注意对于有向图和有向网，它的所有邻接点的个数就是它的边数。对于无向图和无向网，它的所有邻接点的个数除以二才是它的边数。
(3) 设计算法从V0出发深度优先遍历图G，并构造出相应的生成树或生成森林。
改编深度遍历，将访问到的路径信息，存储到树的结构中去。
(4) 设计算法从V0出发广度优先遍历图G，并构造出相应的生成树或生成森林。
改编广度遍历算法，将访问到的路径信息，存储到树的结构中去。
(5) 对连通网N=(V,E)，仍设S为已选顶点集，U 为未选顶点集，WE为候选边集，TE为已选 边集，根据上面的讨论，我们得到Prim算 法流程如下： 1、初始化：S为空，U=V，WE为空，TE为空； 2、将起点从U移到S； 3、更新候选边集合WE（一端已选，一端未选）； 4、 如果集合U非空，重复执行下列操作： （a）从候选边集WE中选择一条权值最小的 边，比如(v,u)，加入到已选边集TE中。这 里v为“已选一端”，u为“未选一端”。 如果最小权值的边有几条，任选其中一条； （b）把（a）中所选边的另一端顶点，u，加 入到已选顶点集合S中； （c）更新候选边集合WE； n 循环结束后，整个算法结束，此时有： S=V，U为空，WE为空，TE中为最小生成 树的n-1条边。
(6) 实现Kruskal算法，求解下列给定图G的最小生成树。
先将图的所有边都保存下来，并且都初始化为可用。
还要记录每个连通分量的编号
从所有边中选出最小的可用的边，选完之后将最小边标记为不可用。
将选出的边放到生成树边的数组中去。
将连通编号更新为最小的编号。
直到选出n-1条边，循环结束，最小生成树的边全部找到。
(7) 实现Dijkstra算法，求解下列给定图G指定顶点到其余顶点之间的最短路径。按照最短路径长度不减的次序求解各顶点的解，即按由远及近的次序递推求解各个顶点的解。
vID为选定的起始顶点。
Path[]数组保存全图的最短路径信息，下标对应顶点的编号，数组的值表示当前顶点的直接前驱的编号。
Dist[]数组用来保存全图顶点到指定起点v0的最短距离值。
每次选取dist[]最小的顶点，并且更新其邻接顶点到顶点的最短距离，若dist[i]+这两个顶点间的权值小于原本的dist[]的值，则需要更新，反正则不需要。
全部处理完之后，倒着迭代输出路径和最小路径的距离即可。
(8) 实现Floyd算法，求解下列给定图G各顶点之间的最短路径。
弗洛伊德算法是通过邻接矩阵的递推更新完成的，所以要用到邻接矩阵。
Dist数组表示为i，j之间的最短的距离。
Path数组保存的是i到j的路径上的j的直接前驱顶点。
初始时更具邻接矩阵初始化dist数组。
初始化path数组，若i，j之间存在边，那么j的前驱为i，否则设置为-1。
不断循环尝试以顶点1，2….n为跳点，若距离有所缩短则更新dist数组，并更新j的直接前驱为m。
最终已合适的方法输出path数组和dist数组就可以得到每个顶点间的最短路径。
(9) 设计算法求解下列给定图G的拓扑序列。
拓扑排序需要先求得各个顶点度入度，所以需要编写算法实现求入度，邻接链表对于出度的求解较为方便，入度的求解较为复杂，我这里利用两重循环来实现，从每个边链表上找到所求顶点的入度。
我这里实现的拓扑算法利用的是栈来实现的。
先初始化空栈S，在将AOV网中所有入度为0的顶点入栈。
若栈不为空出栈，输出V，并且将V的每个后继入度减一，若后继为0，则压入栈中。
重复以上操作。
最后若拓扑序列中的顶点数目等于所有顶点数目，则表示无环可以进行拓扑排序返回1，否则则表示有环，不可以拓扑排序返回0。
(10) 设计算法求解下列给定AOE网的关键路径。
关键路径上的顶点需要满足最早发生时间等于最晚发生时间。文章来源地址https://www.toymoban.com/news/detail-478577.html
这题用邻接矩阵实现更为简单。求出每个顶点的最早发生时间和最晚发生时间。最早发生时间的求解要用到拓扑排序的序列来实现。最晚发生时间的求解要用到逆拓扑排序序列来实现。
因此先求出拓扑排序序列。最早发生时间是前面一个顶点的最早发生时间与前一个顶点和当前顶点的活动的持续时间之和的最大值。
最晚发生时间是后一个顶点的最晚发生时间与该顶点和后一个顶点间的活动的持续时间之差的最小值。文章来源：https://www.toymoban.com/news/detail-478577.html
关键路径上的顶点需要满足最早发生时间等于最晚发生时间。
//************************************************************//
//* 图的邻接链表表示的头文件，文件名：GraphAdjLinkList.h *//
//* *//
//************************************************************//
#define INF 65535 //定义无穷大
#define MaxVerNum 100 //定义最大顶点个数
#include<iostream>
#include<string.h>
#include "stdlib.h"
using namespace std;
typedef char elementType; //定义图中顶点的数据类型
typedef int eInfoType; //边链表中关于边的信息的数据类型，比如，带权图中可以表示边的权值
typedef int cellType; //定义邻接矩阵中元素的数据类型
//对无权图，1-相邻（有边），0-不相邻（无边）
//对有权图，为边的权值，特别是无穷大。
typedef enum{UDG, UDN, DG, DN} GraphKind; //枚举图的类型--无向图，无向网，有向图，有向网
typedef struct eNode //边链表结点结构
{
int adjVer; //邻接顶点地址，此处为顶点在顶点表中序号，从1开始
eInfoType eInfo; //边链表中表示边的相关信息，比如表的权值
struct eNode* next; //指向边链表中的下一个结点
}EdgeNode; //边链表结点类型
typedef struct vNode //顶点表中元素结构
{
elementType data; //存放图中顶点的数据
EdgeNode* firstEdge; //指向此顶点关联的第一条边的指针，即边链表的头指针
}VerNode;
typedef struct GraphAdjLinkList
{
VerNode VerList[MaxVerNum+1]; //存放顶点的顺序表，数组0单元不用
int VerNum; //顶点数
int ArcNum; //弧（边）数
GraphKind gKind; //图的类型:0-无向图；1-无向网；2-有向图；3-有向网
}Graph; //图的类型名
typedef struct GraphAdjMatrix
{
elementType Data[MaxVerNum+1]; //顶点数组，存放顶点元素的值，Data[0]单元不用
cellType AdjMatrix[MaxVerNum+1][MaxVerNum+1]; //邻接矩阵，数组下标为0单元不用，从AdjMatrix[1][1]单元开始
int VerNum; //顶点数
int ArcNum; //弧（边）数
GraphKind gKind; //图的类型:0-无向图；1-无向网；2-有向图；3-有向网
} Graph1; //图的类型名
bool visited[MaxVerNum+1]; //全局数组，标记顶点是否已经被访问。0--未访问；1--已访问。数组0单元不用
//******************* 访问图中顶点的函数*********************//
//* 函数功能：打印图中顶点元素，并标记为已经访问 *//
//* 入口参数 Graph G，待访问的图；int verID 目标顶点编号 *//
//* 出口参数：无 *//
//* 返 回 值：空 *//
//* 函 数 名：visit(Graph &G, int verID) *//
//***********************************************************//
void visit(Graph &G, int verID)
{ //顶点编号从1开始，数组0单元不用
cout<<G.VerList[verID].data<<"\t";
visited[verID]=true;
}
//******************* 图中查找目标顶点 *********************//
//* 函数功能：给定顶点元素，在图中查找此顶点元素的编号 *//
//* 入口参数 Graph G，待访问的图；elementType v 目标顶点 *//
//* 出口参数：无 *//
//* 返 回 值：int。如果目标顶点存在，返回顶点编号， *//
//* 顶点编号从1开始；否则返回-1 *//
//* 函 数 名：visit(Graph &G, int verID) *//
//***********************************************************//
int LocateVertex(Graph &G, elementType v)
{
for(int i=1;i<=G.VerNum;i++)
{
if( G.VerList[i].data==v ){
return i;
}
}
return -1;
}
//搜索顶点v的第一个邻接顶点
int firstAdj(Graph &G, int v)
{
EdgeNode *p;
p=G.VerList[v].firstEdge;
if(p)
return p->adjVer;
else
return 0;
}
//搜索顶点v位于邻接点w之后的下一个邻接点
int nextAdj(Graph &G, int v, int w)
{
EdgeNode *p;
p=G.VerList[v].firstEdge; //取顶点v的边链表头指针
while(p->next)
{
if(p->adjVer==w)
return p->next->adjVer; //返回w之后下一个邻接点编号
p=p->next;
}
return 0; //未找到下一个邻接点，返回0
}
//******************** 打印图的相关信息 *********************//
//* 函数功能：打印图的相关信息 *//
//* 入口参数 Graph G，待打印的图 *//
//* 出口参数：无 *//
//* 返 回 值：空 *//
//* 函 数 名：printGraph(Graph &G) *//
//***********************************************************//
void printGraph(Graph &G)
{
int i=0,j=0;
//打印图的类型
switch(G.gKind)
{
case UDG:
cout<<"图类型：无向图"<<endl;
break;
case UDN:
cout<<"图类型：无向网"<<endl;
break;
case DG:
cout<<"图类型：有向图"<<endl;
break;
case DN:
cout<<"图类型：有向网"<<endl;
break;
default:
cout<<"图类型错误。"<<endl;
break;
}
//打印图的顶点数
cout<<"顶点数："<<G.VerNum<<endl;
//打印图的边数
cout<<"边 数："<<G.ArcNum<<endl;
//打印顶点及其编号
cout<<"编号\t顶点\t边链表"<<endl;
EdgeNode* p;
for(i=1;i<=G.VerNum;i++)
{
cout<<i<<"\t"<<G.VerList[i].data<<"\t";
p=G.VerList[i].firstEdge;
while(p!=NULL)
{
cout<<p->adjVer<<"\t";
p=p->next;
}
cout<<endl;
}
cout<<endl;
//打印邻接矩阵
cout<<"邻接矩阵："<<endl;
for(i=1;i<=G.VerNum;i++)
{
cout<<"\t";
p=G.VerList[i].firstEdge;
j=1;
while(p!=NULL || j<=G.VerNum)
{
if((j<=G.VerNum) && (p!=NULL) && j==p->adjVer) //有边
{
cout<<p->eInfo<<"\t";
j++;
p=p->next;
}
else //无边
{
if(G.gKind==UDN || G.gKind==DN)
cout<<"INF"<<"\t"; //网，无边时打印权值为无穷大，用“INF”表示
else
cout<<"0"<<"\t"; //图，无边时用0表示
j++;
}
}
cout<<endl;
}
}
void strLTrim(char* str); //删除字符串左边空格
//***************************2 文件创建图****************************//
//* 函数功能：从文本文件创建邻接矩阵表示的图 *//
//* 入口参数 char fileName[]，文件名 *//
//* 出口参数：Graph &G，即创建的图 *//
//* 返 回 值：bool，true创建成功；false创建失败 *//
//* 函 数 名：CreateGrpFromFile(char fileName[], Graph &G) *//
//* 备 注：本函数使用的数据文件以邻接矩阵为输入数据 *//
//*******************************************************************//
bool CreateGrpFromFile1(char fileName[], Graph1 &G)
{
FILE* pFile; //定义顺序表的文件指针
char str[1000]; //存放读出一行文本的字符串
char strTemp[10]; //判断是否注释行
cellType eWeight; //边的信息，常为边的权值
GraphKind GrpType; //图类型枚举变量
pFile=fopen(fileName,"r");
if(!pFile)
{
printf("错误：文件%s打开失败。\n",fileName);
return false;
}
while(fgets(str,1000,pFile)!=NULL)
{
//删除字符串左边空格
strLTrim(str);
if (str[0]=='\n') //空行，继续读取下一行
continue;
strncpy(strTemp,str,2);
if(strstr(strTemp,"//")!=NULL) //跳过注释行
continue;
else //非注释行、非空行，跳出循环
break;
}
//循环结束，str中应该已经是文件标识，判断文件格式
if(strstr(str,"Graph")==NULL)
{
printf("错误：打开的文件格式错误！\n");
fclose(pFile); //关闭文件
return false;
}
//读取图的类型，跳过空行
while(fgets(str,1000,pFile)!=NULL)
{
//删除字符串左边空格
strLTrim(str);
if (str[0]=='\n') //空行，继续读取下一行
continue;
strncpy(strTemp,str,2);
if(strstr(strTemp,"//")!=NULL) //注释行，跳过，继续读取下一行
continue;
else //非空行，也非注释行，即图的类型标识
break;
}
//设置图的类型
if(strstr(str,"UDG"))
GrpType=UDG; //无向图
else if(strstr(str,"UDN"))
GrpType=UDN; //无向网
else if(strstr(str,"DG"))
GrpType=DG; //有向图
else if(strstr(str,"DN"))
GrpType=DN; //有向网
else
{
printf("错误：读取图的类型标记失败！\n");
fclose(pFile); //关闭文件
return false;
}
//读取顶点元素，到str。跳过空行
while(fgets(str,1000,pFile)!=NULL)
{
//删除字符串左边空格
strLTrim(str);
if (str[0]=='\n') //空行，继续读取下一行
continue;
strncpy(strTemp,str,2);
if(strstr(strTemp,"//")!=NULL) //注释行，跳过，继续读取下一行
continue;
else //非空行，也非注释行，即图的顶点元素行
break;
}
//顶点数据放入图的顶点数组
char* token=strtok(str," ");
int nNum=1;
while(token!=NULL)
{
G.Data[nNum]=*token; // atoi(token); //顶点数据转换为整数，若为字符则不需转换
token = strtok( NULL, " ");
nNum++;
}
nNum--; //顶点数
//图的邻接矩阵初始化
int nRow=1; //矩阵行下标，从1开始
int nCol=1; //矩阵列下标，从1开始
if(GrpType==UDG || GrpType==DG)
{
for(nRow=1;nRow<=nNum;nRow++)
for(nCol=1;nCol<=nNum;nCol++)
G.AdjMatrix[nRow][nCol]=0;
}
else
{
for(nRow=1;nRow<=nNum;nRow++)
for(nCol=1;nCol<=nNum;nCol++)
G.AdjMatrix[nRow][nCol]=INF; //INF表示无穷大
}
//循环读取边的数据到邻接矩阵
int edgeNum=0; //边的数量
elementType Nf,Ns; //边或弧的2个相邻顶点
while(fgets(str,1000,pFile)!=NULL)
{
//删除字符串左边空格
strLTrim(str);
if (str[0]=='\n') //空行，继续读取下一行
continue;
strncpy(strTemp,str,2);
if(strstr(strTemp,"//")!=NULL) //注释行，跳过，继续读取下一行
continue;
char* token=strtok(str," "); //以空格为分隔符，分割一行数据，写入邻接矩阵
if(token==NULL) //分割为空串，失败退出
{
printf("错误：读取图的边数据失败！\n");
fclose(pFile); //关闭文件
return false;
}
Nf=*token; //获取边的第一个顶点
token = strtok( NULL, " "); //读取下一个子串，即第二个顶点
if(token==NULL) //分割为空串，失败退出
{
printf("错误：读取图的边数据失败！\n");
fclose(pFile); //关闭文件
return false;
}
Ns=*token; //获取边的第二个顶点
//从第一个顶点获取行号
for(nRow=1;nRow<=nNum;nRow++)
{
if(G.Data[nRow]==Nf) //从顶点列表找到第一个顶点的编号
break;
}
//从第二个顶点获取列号
for(nCol=1;nCol<=nNum;nCol++)
{
if(G.Data[nCol]==Ns) //从顶点列表找到第二个顶点的编号
break;
}
//如果为网，读取权值
if(GrpType==UDN || GrpType==DN)
{
token = strtok( NULL, " "); //读取下一个子串，即边的附加信息，常为边的权重
if(token==NULL) //分割为空串，失败退出
{
printf("错误：读取图的边数据失败！\n");
fclose(pFile); //关闭文件
return false;
}
eWeight=atoi(token); //取得边的附加信息
}
if(GrpType==UDN || GrpType==DN) //如果为网，邻接矩阵中对应的边设置权值，否则置为1
G.AdjMatrix[nRow][nCol]=eWeight;
else
G.AdjMatrix[nRow][nCol]=1; //atoi(token); //字符串转为整数
edgeNum++; //边数加1
}
G.VerNum=nNum; //图的顶点数
if(GrpType==UDG || GrpType==UDN)
G.ArcNum=edgeNum / 2; //无向图或网的边数等于统计的数字除2
else
G.ArcNum=edgeNum;
G.gKind=GrpType; //图的类型
fclose(pFile); //关闭文件
return true;
}
//***************************3 文件创建图****************************//
//* 函数功能：从文本文件创建邻接矩阵表示的图 *//
//* 入口参数 char fileName[]，文件名 *//
//* 出口参数：Graph &G，即创建的图 *//
//* 返 回 值：bool，true创建成功；false创建失败 *//
//* 函 数 名：CreateGraphUDFromFile(char fileName[], Graph &G) *//
//* 备注：本函数使用的数据文件格式以边（顶点对）为基本数据 *//
//*******************************************************************//
bool CreateGraphFromFile(char fileName[], Graph &G)
{
FILE* pFile; //定义顺序表的文件指针
char str[1000]; //存放读出一行文本的字符串
char strTemp[10]; //判断是否注释行
int i=0,j=0;
int edgeNum=0; //边的数量
eInfoType eWeight; //边的信息，常为边的权值
GraphKind graphType; //图类型枚举变量
pFile=fopen(fileName,"r");
if(!pFile)
{
printf("错误：文件%s打开失败。\n",fileName);
return false;
}
while(fgets(str,1000,pFile)!=NULL) //跳过空行和注释行
{
//删除字符串左边空格
strLTrim(str);
if (str[0]=='\n') //空行，继续读取下一行
continue;
strncpy(strTemp,str,2);
if(strstr(strTemp,"//")!=NULL) //跳过注释行
continue;
else //非注释行、非空行，跳出循环
break;
}
//循环结束，str中应该已经是文件标识，判断文件格式
if(strstr(str,"Graph")==NULL)
{
printf("错误：打开的文件格式错误！\n");
fclose(pFile); //关闭文件
return false;
}
//读取图的类型，跳过空行及注释行
while(fgets(str,1000,pFile)!=NULL)
{
//删除字符串左边空格
strLTrim(str);
if (str[0]=='\n') //空行，继续读取下一行
continue;
strncpy(strTemp,str,2);
if(strstr(strTemp,"//")!=NULL) //注释行，跳过，继续读取下一行
continue;
else //非空行，也非注释行，即图的类型标识
break;
}
//设置图的类型
if(strstr(str,"UDG"))
graphType=UDG; //无向图
else if(strstr(str,"UDN"))
graphType=UDN; //无向网
else if(strstr(str,"DG"))
graphType=DG; //有向图
else if(strstr(str,"DN"))
graphType=DN; //有向网
else
{
printf("错误：读取图的类型标记失败！\n");
fclose(pFile); //关闭文件
return false;
}
//读取顶点元素，到str。跳过空行
while(fgets(str,1000,pFile)!=NULL)
{
//删除字符串左边空格
strLTrim(str);
if (str[0]=='\n') //空行，继续读取下一行
continue;
strncpy(strTemp,str,2);
if(strstr(strTemp,"//")!=NULL) //注释行，跳过，继续读取下一行
continue;
else //非空行，也非注释行，即图的顶点元素行
break;
}
//顶点数据放入图的顶点数组
char* token=strtok(str," ");
int nNum=0;
while(token!=NULL)
{
G.VerList[nNum+1].data=*token;
G.VerList[nNum+1].firstEdge=NULL;
//p=NULL;
//eR=G.VerList[i].firstEdge;
token = strtok( NULL, " ");
nNum++;
}
//循环读取边（顶点对）数据
int nRow=1; //矩阵行下标
int nCol=1; //矩阵列下标
EdgeNode* eR; //边链表尾指针
EdgeNode* p;
elementType Nf,Ns; //边或弧的2个相邻顶点
while(fgets(str,1000,pFile)!=NULL)
{
//删除字符串左边空格
strLTrim(str);
if (str[0]=='\n') //空行，继续读取下一行
continue;
strncpy(strTemp,str,2);
if(strstr(strTemp,"//")!=NULL) //注释行，跳过，继续读取下一行
continue;
//nCol=0; //列号设为0，一行重新开始
char* token=strtok(str," "); //以空格为分隔符，分割一行数据，写入邻接矩阵
if(token==NULL) //分割为空串，失败退出
{
printf("错误：读取图的边数据失败！\n");
fclose(pFile); //关闭文件
return false;
}
Nf=*token; //获取边的第一个顶点
token = strtok( NULL, " "); //读取下一个子串，即第二个顶点
if(token==NULL) //分割为空串，失败退出
{
printf("错误：读取图的边数据失败！\n");
fclose(pFile); //关闭文件
return false;
}
Ns=*token; //获取边的第二个顶点
//从第一个顶点获取行号
for(nRow=1;nRow<=nNum;nRow++)
{
if(G.VerList[nRow].data==Nf) //从顶点列表找到第一个顶点的编号
break;
}
//从第二个顶点获取列号
for(nCol=1;nCol<=nNum;nCol++)
{
if(G.VerList[nCol].data==Ns) //从顶点列表找到第二个顶点的编号
break;
}
//如果为网，读取权值
if(graphType==UDN || graphType==DN)
{
token = strtok( NULL, " "); //读取下一个子串，即边的附加信息，常为边的权重
if(token==NULL) //分割为空串，失败退出
{
printf("错误：读取图的边数据失败！\n");
fclose(pFile); //关闭文件
return false;
}
eWeight=atoi(token ); //取得边的附加信息
}
eR=G.VerList[nRow].firstEdge;
while(eR!=NULL && eR->next!=NULL)
{
eR=eR->next; //后移边链表指针，直至尾节点
}
p=new EdgeNode; //申请一个边链表结点
p->adjVer=nCol; //顶点的编号，从1开始
if(graphType==UDN || graphType==DN) //边的附加信息，对有权图保存权值，无权图为1
p->eInfo=eWeight;
else
p->eInfo=1;
p->next=NULL;
if(G.VerList[nRow].firstEdge==NULL)
{
G.VerList[nRow].firstEdge=p;
eR=p;
}
else
{
eR->next=p;
eR=p; //新的尾指针
}
edgeNum++; //边数加1
}
G.VerNum=nNum; //图的顶点数
if(graphType==UDG || graphType==UDN)
G.ArcNum=edgeNum / 2; //无向图或网的边数等于统计的数字除2
else
G.ArcNum=edgeNum;
G.gKind=graphType; //图的类型
fclose(pFile); //关闭文件
return true;
}
//删除字符串、字符数组左边空格
void strLTrim(char* str)
{
int i,j;
int n=0;
n=strlen(str)+1;
for(i=0;i<n;i++)
{
if(str[i]!=' ') //找到左起第一个非空格位置
break;
}
//以第一个非空格字符为手字符移动字符串
for(j=0;j<n;j++)
{
str[j]=str[i];
i++;
}
}
//销毁图
void DestroyGraph(Graph &G)
{
EdgeNode *p,*u;
int vID;
for(vID=1; vID<=G.VerNum; vID++) //循环删除每个顶点的边链表
{
p=G.VerList[vID].firstEdge;
G.VerList[vID].firstEdge=NULL;
while(p) //循环删除当前顶点所有的关联边
{
u=p->next; //u指向下一个边结点
delete(p); //删除当前边结点
p=u;
}
}
p=NULL;
u=NULL;
G.VerNum=-1; //编辑图已经销毁
}
int firstAdj(Graph1 &G,int v)
{
int w;
for(w=1;w<=G.VerNum;w++)
{
if((G.AdjMatrix[v][w]>=1) &&
(G.AdjMatrix[v][w])<INF)
return w; //返回第一个邻接点编号
}
return -1; //未找到邻接点，返回0
}
//求顶点v的位于邻接点w后的下一个邻接点
int nextAdj(Graph1 &G,int v,int w)
{
int k;
for(k=w+1;k<=G.VerNum;k++)
{
if((G.AdjMatrix[v][k]>=1) &&
(G.AdjMatrix[v][k])<INF)
return k; //返回v的位于w之后的下一个邻接点k
}
return -1; //不存在下一个邻接点，返回0
}
//算法部分
//
///
//
///
///
#include"createGrpAdjLinkedList.h"
//深度遍历
void DFS(Graph &G, int verID){
visit(G, verID);
EdgeNode *p;
p = G.VerList[verID].firstEdge;
while(p){
if(!visited[p->adjVer]){
DFS(G, p->adjVer);
}
p = p->next;
}
}
int DFSTraverse(Graph &G, int verID){
int vID; //顶点编号
int conNum = 0; //记录连通分量数
for(vID = 0; vID <= G.VerNum; vID++){
visited[vID] = false;
}
DFS(G, verID);
conNum++;
for(vID = 1; vID <= G.VerNum; vID++){
if(!visited[vID]){
DFS(G, vID);
conNum++;
}
}
return conNum;
}
//广度遍历
void BFS(Graph &G, int verID){
int u;
EdgeNode *p;
int Q[100]; // 数组模拟队列
int front = 0;
int rear = 0;
visit(G, verID);
Q[++rear] = verID;
while(front != rear){
u = Q[++front];
p = G.VerList[u].firstEdge;
while(p){
if(!visited[p->adjVer]){
visit(G, p->adjVer);
Q[++rear] = p->adjVer;
}
p = p->next;
}
}
}
int BFSTraverse(Graph &G, int verID){
int vID;
int conNum = 0;
for(vID = 0; vID <= G.VerNum; vID++){
visited[vID] = false;
}
BFS(G, verID);
conNum++;
for(vID = 1; vID <= G.VerNum; vID++){
if(!visited[vID]){
BFS(G, vID);
conNum++;
}
} return conNum;
}
//求给定图中的边的数目
void DFS1(Graph &G, int verID, int &E){
visited[verID] = true;
EdgeNode *p;
p = G.VerList[verID].firstEdge;
while(p){
E++;
if(!visited[p->adjVer]){
DFS1(G, p->adjVer, E);
}
p = p->next;
}
}
int Enum(Graph &G, int verID){
int vID; //顶点编号
int E = 0;
for(vID = 0; vID <= G.VerNum; vID++){
visited[vID] = false;
}
for(vID = 1; vID <= G.VerNum; vID++){
if(!visited[vID]){
DFS1(G, vID, E);
}
}
if(G.gKind==UDN || G.gKind==UDG)
return E / 2;
else
return E;
}
//深度优先遍历图G，并构造出相应的生成树或生成森林
typedef struct csNode
{
elementType data;
struct csNode *firstChild, *nextSibling;
}csNode,*csTree;
//先序遍历
void Fist(csNode * T){
if(T){
cout << T->data << " ";
Fist(T->firstChild);
Fist(T->nextSibling);
}
}
void Dfs(Graph G,int i,csNode *&T)
{
visit(G, i);
bool first=true;//表示是否为当前节点第一个孩子
csNode *locat;//同样是定位作用
EdgeNode *p;
p = G.VerList[i].firstEdge;
while(p)//从此节点出发，访问邻接节点。
{
if(!visited[p->adjVer]){
csNode *t=new csNode;//建立一颗小树
t->data=G.VerList[p->adjVer].data;
t->firstChild = NULL;
t->nextSibling = NULL;
if(first){//是当前节点第一个孩子
T->firstChild = t;
first=false;//表示不是传进来的第一个孩子,则是孩子们的兄弟
}else{
locat->nextSibling=t; //建立右孩子
}
locat=t;
Dfs(G,p->adjVer,t);//继续对小树找兄弟
}
p = p->next;
}
}
void DFS_Traverse(Graph G,csNode*&T, int verID)
{
T = NULL;
csNode *locat;//此处定义一个定位指针，用来定位当前树的位置
int vID; //顶点编号
for(int i=1;i<=G.VerNum;i++)
{
visited[i]=false;
}
csNode *t = new csNode;//这代表一个小树
t->data = G.VerList[verID].data;
t->firstChild = NULL;
t->nextSibling = NULL;
T=t;//若树为空，建立头节点
locat=t;//定位至小树
Dfs(G,verID,locat);//建立小树
for(int i=1;i<=G.VerNum;i++)
{
if(!visited[i]){
csNode *t=new csNode;//这代表一个小树
t->data=G.VerList[i].data;
t->firstChild = NULL;
t->nextSibling = NULL;
locat->nextSibling=t;//若树不空，则是森林，插入右兄弟
locat=t;//定位至小树
Dfs(G,i,locat);//建立小树
}
}
}
void Bfs(Graph G,int i,csNode*T){
csNode *q=NULL;
EdgeNode *p;
csNode * Q[100]; // 数组模拟队列
int front = 0;
int rear = 0;
visit(G, i);
//根结点入队
Q[++rear] =T;
//当队列为空时，证明遍历完成
while (front != rear) {
bool first=true;
//队列首个结点出队
q = Q[++front];
//遍历以出队结点为起始点的所有邻接点
int u = LocateVertex(G, q->data);
p = G.VerList[u].firstEdge;
while(p){
if(!visited[i]){
csNode *t=new csNode;//这代表一个小树
t->data=G.VerList[i].data;
t->firstChild = NULL;
t->nextSibling = NULL;
//当前结点入队
Q[++rear] = t;
//更改标志位
visit(G, p->adjVer);
//如果是出队顶点的第一个邻接点，设置p结点为其左孩子
if(first){//是当前节点第一个孩子
T->firstChild = t;
first=false;//表示不是传进来的第一个孩子,则是孩子们的兄弟
}else{
q->nextSibling=t; //建立右孩子
}
q=t;
}
p = p->next;
}
}
}
//广度优先搜索生成森林并转化为二叉树
void BFSForest(Graph G,csNode*&T, int verID){
T = NULL;
csNode *locat;//此处定义一个定位指针，用来定位当前树的位置
for(int i=1;i<=G.VerNum;i++)
{
visited[i]=false;
}
csNode *t = new csNode;//这代表一个小树
t->data = G.VerList[verID].data;
t->firstChild = NULL;
t->nextSibling = NULL;
T=t;//若树为空，建立头节点
locat=t;//定位至小树
Bfs(G,verID,locat);//建立小树
for(int i=1;i<=G.VerNum;i++)
{
if(!visited[i]){
csNode *t=new csNode;//这代表一个小树
t->data=G.VerList[i].data;
t->firstChild = NULL;
t->nextSibling = NULL;
locat->nextSibling=t;//若树不空，则是森林，插入右兄弟
locat=t;//定位至小树
Bfs(G,i,locat);//建立小树
}
}
}
//5．实现Prim算法
//Prim算法基于邻接链表的实现
int inTree[MaxVerNum+1]={0}; //标记顶点已经在Prim生成树中，或已经访问过。1或true--已访问，0或false--未访问
//inTree[0]单元未用
//或者为标记已经在集合U中的顶点
//保存候选边的信息
typedef struct minEdgeType
{
int v; //V-U中当前选中的顶点编号，从1开始。即刚从V-U中选出放到U中的顶点
cellType eWeight; //U中某个顶点到V-U中当前顶点v的最小距离
} MinEdgeType;
????????同时返回此边的权值，用引用或指针返回
//eWeight为当前边的权值
//检查图G中编号为vBegin和vEnd之间是否有边
int HasEdge(Graph &G, int vBegin, int vEnd, eInfoType &eWeight)
{
EdgeNode *p; //边链表结点指针
int f=0; //是否有边的标记
eWeight=INF; //边的权值初始化为无穷大
p=G.VerList[vBegin].firstEdge;
while(p)
{
if( p->adjVer==vEnd )
{
f=1; //vBegin与vEnd之间有边，退出循环，返回1
eWeight=p->eInfo;
break;
}
p=p->next;
}
return f;
}
//初始化候选边数组，和已经选择边数组
void InitMinEdges(Graph &G, MinEdgeType minEdges[],int vID)
{
int i;
eInfoType eWeight;
for(i=1;i<=G.VerNum;i++)
{
//初始化候选边数组
if(HasEdge(G, vID, i, eWeight))
{
minEdges[i].v=vID;
minEdges[i].eWeight=eWeight;
}
else
minEdges[i].eWeight=INF;
}
}
//从候选边集合中选出最小边，返回在V-U中的关联顶点编号
int GetMinEdge(Graph &G, MinEdgeType minEdges[])
{
eInfoType eMin=INF; //保存最小的权值
int i,j;
for(i=1;i<=G.VerNum;i++)
{
if(inTree[i]==0 && minEdges[i].eWeight<eMin)
{
j=i; //如果当前编号为i的顶点在集合V-U中，且权值比eMin小，暂选为最小边
eMin=minEdges[i].eWeight;
}
}
return j; //j即为V-U中，最小边关联顶点的编号
}
//新选出一条最小边后，顶点加入U中，更新其邻接顶点的最小权值
void ChangeMinEdgesWeight(Graph &G, MinEdgeType minEdges[], int vID)
{
//对新选出的编号为vID的顶点（新加入集合U中），调整候选边集合
int i,j;
eInfoType eWeight;
for(i=1;i<=G.VerNum;i++)
{
if(inTree[i]==0) //编号i顶点在V-U中，不在U中
{
//检查vID与i之间是否相邻（有边）
//检查U中顶点vID与i之间的边权值是否更小，若更小则更新(vID,i)权值
if(HasEdge(G,vID,i, eWeight) && eWeight<minEdges[i].eWeight)
{
minEdges[i].v=vID;
minEdges[i].eWeight=eWeight;
}
}
}
}
void Prim(Graph &G, int vID)
{
MinEdgeType minEdges[MaxVerNum]; //minEdges[i]的下标加1，即i+1为选定边的起始点
//minEdges[i].v为选定边的终点
int i;
int curID; //当前选择顶点编号
eInfoType wAll=0; //权值总和
InitMinEdges(G, minEdges, vID); //初始化候选边数组
inTree[vID]=true; //标记vID已在生成树上，即集合U中
for(i=1;i<G.VerNum;i++) //选择n-1条边，形成生成树
{
curID=GetMinEdge(G, minEdges); //选择V-U中最小边关联的顶点
inTree[curID]=true; //标记curID已选进U中
ChangeMinEdgesWeight(G, minEdges, curID); //修改权值
}
cout<<endl; //输出结果
cout<<"Prim生成树起始顶点："<<G.VerList[vID].data<<"，编号："<<vID<<endl;
cout<<"选择的边和权值："<<endl;
for(i=1;i<=G.VerNum;i++)
{
if(i!=vID)
{
cout<<"("<<G.VerList[minEdges[i].v].data<<","<<G.VerList[i].data<<") 权值："<<minEdges[i].eWeight<<endl;
wAll+=minEdges[i].eWeight;
}
}
cout<<"生成树总权值："<<wAll<<endl;
cout<<endl;
}
//Kruskal 算法--基于邻接链表
typedef struct edgetype
{
int vBegin; //边的起始顶点编号，从1开始
int vEnd; //边的另一顶点编号，从1开始
eInfoType eWeight; //边的权值
}EdgeType;
//从图的邻接链表读取所有边的信息，存储到一维数组edges[]中
void GetEdges(Graph &G, EdgeType edges[])
{
int i;
int k=0;
EdgeNode *p;
for(i=1;i<=G.VerNum;i++)
{
p=G.VerList[i].firstEdge;
while(p)
{
edges[k].vBegin=LocateVertex(G, G.VerList[i].data); //由顶点数据获取顶点编号
edges[k].vEnd=p->adjVer;
edges[k].eWeight=p->eInfo;
p=p->next;
k++;
}
}
//for(i=0;i<k;i++)
//{
// cout<<edges[i].vBegin<<"<-->"<<edges[i].vEnd<<"\t"<<edges[i].eWeight<<endl;
//}
}
//获取当前可用最小边--替代方法：对edges[]数组进行递增排序后，就不需要此函数
EdgeType GetMinEdge(Graph &G, EdgeType edges[], int edgeUsed[], int &n) //n为返回的最小边在edges[]数组中的下标
{
EdgeType minEdge;
eInfoType wMin=INF; //保存最小权值
int i,M;
if(G.gKind==UDN || G.gKind==UDG)
M=G.ArcNum*2; //无向图和无向网，由于对称性，edges[]有效数据个数是边数的2倍
else
M=G.ArcNum;
for(i=0;i<M;i++)
{
if(edgeUsed[i]==0 && edges[i].eWeight<wMin)
{
wMin=edges[i].eWeight;
minEdge.eWeight=edges[i].eWeight;
minEdge.vBegin=edges[i].vBegin;
minEdge.vEnd=edges[i].vEnd;
n=i;
}
}
return minEdge; //返回取得的最小边
}
//Kruskal算法
void Kruskal(Graph &G)
{
int conVerID[MaxVerNum]; //存放连通分量（子树）编号
EdgeType edges[MaxVerNum*MaxVerNum]; //存放所有的边信息
EdgeType treeEdges[MaxVerNum-1]; //存放生成树的所有边信息，共n-1条边
int edgeUsed[MaxVerNum*MaxVerNum]; //与edges[]数组对应，标记一条边是否已经使用过。1--已用过，0--未用过
//也可以用排序算法先对图的所有边进行排序来完成这个工作。
EdgeType minEdge; //保存最小边
int i,j;
int n; //返回的最小边的序号
int conID; //获取连通分量编号
int M; //循环次数
if(G.gKind==UDG ||G.gKind==UDN)
M=G.ArcNum*2; //因为无向图、无向网邻接矩阵对称，有效数据是边数的2倍，所以乘2
else
M=G.ArcNum; //有向图或有向网，M=边数
//获取图所有边的信息，存入数组edges[]
GetEdges( G, edges );
for(i=0; i<M; i++)
edgeUsed[i]=0; //标记edges[]中所有边都可用。
//初始化连通分量编号。开始每个顶点作为一个连通分量，每个一个编号，从1开始，与顶点编号相同
for(i=1;i<=M;i++)
{
conVerID[i]=i; //顶点编号与数组下标差1
}
for(i=1; i<G.VerNum; i++) //取出n-1条边，构成生成树
{
minEdge=GetMinEdge(G,edges,edgeUsed,n); //取得本轮循环的最小边
while(conVerID[minEdge.vBegin]==conVerID[minEdge.vEnd]) //当前最小边2个顶点已经属于同一个连通分量，不可用，继续取下一条最小边、
{
edgeUsed[n]=1; //标记边edges[n]（从0开始）不可用
minEdge=GetMinEdge(G,edges,edgeUsed,n); //继续取下一条最小边
}
//取得有效最小边，加入最小生成树中
treeEdges[i]=minEdge;
conID=conVerID[minEdge.vBegin]; //取得此最小边开始顶点的连通编号
for(j=1;j<=G.VerNum;j++)
{
if(conVerID[j]==conID)
conVerID[j]=conVerID[minEdge.vEnd];
}
edgeUsed[i]=1; //当前最小边标记为已使用边
}
//输出结果
eInfoType wAll=0; //总权值
cout<<endl; //输出结果
cout<<"Kruskal最小生成树:"<<endl;
cout<<"选择的边和权值："<<endl;
for(i=1;i<G.VerNum;i++) //n-1条边
{
cout<<"("<<G.VerList[treeEdges[i].vBegin].data<<","<<G.VerList[treeEdges[i].vEnd].data<<") 权值："<<treeEdges[i].eWeight<<endl;
wAll+=treeEdges[i].eWeight;
}
cout<<"生成树总权值："<<wAll<<endl;
cout<<endl;
}
//Dijkstra算法--基于邻接表
//*************** Dijkstra算法--基于邻接表 *****************//
//* 函数功能：给定顶点，求解此点与网中其它顶点的最短路径 *//
//* 入口参数：Graph G，待访问的网（图） *//
//* int vID，指定顶点的编号 *//
//* 出口参数：int path[]，返回最短路径信息 *//
//* int dist[]，返回最短距离值 *//
//* 返 回 值：无 *//
//***********************************************************//
void Dijkstra(Graph &G, int path[], int dist[], int vID)
{
int solved[MaxVerNum]; //标记顶点是否已经求出最短路径（已在集合S中）。1-已求出；0-未求出。
int i,j;
int v; //顶点编号
eInfoType minDist; //保存最短距离值
EdgeNode *p; //指向边链表结点
//初始化集合S，距离数组dist[]，路径数组path[]
for(i=1;i<=G.VerNum;i++)
{
solved[i]=0; //所有顶点均为处理
dist[i]=INF; //所有顶点初始距离置为无穷大（INF）
path[i]=-1; //所有顶点的前驱置为-1，即无前驱
}
//处理顶点vID
solved[vID]=1; //标记vID已经处理
dist[vID]=0;
path[vID]=-1;
//从邻接表初始化dist[]和path[]
p=G.VerList[vID].firstEdge; //顶点vID的边链表指针
while(p)
{
v=p->adjVer; //取得vID邻接顶点编号
dist[v]=p->eInfo; //取得vID与v之间边的权值，赋给dist[v]
path[v]=vID; //顶点v的前驱为vID
p=p->next;
}
//依次找出余下n-1个顶点加入集合S中
for(i=1;i<G.VerNum;i++)
{
minDist=INF;
//寻找集合V-S中距离vID最近的顶点
for(j=1;j<=G.VerNum;j++)
{
if(solved[j]==0 && dist[j]<minDist)
{
v=j; //j为V-S中候选的距离vID最近的顶点
minDist=dist[j];
}
}
if(minDist==INF) //S与V-S没有相邻的顶点，算法退出
return;
cout<<"选择顶点："<<G.VerList[v].data<<"--距离："<<minDist<<endl; //输出本次选择的顶点距离
solved[v]=1; //标记顶点v以找到最短距离，加入集合S中
//对选中的顶点v，更新集合V-S中所有与v邻接的顶点距离vID的距离
p=G.VerList[v].firstEdge; //取得v的边链表指针
while(p)
{
j=p->adjVer; //取得v的邻接顶点编号
if(solved[j]==0 && minDist+p->eInfo<dist[j])
{
dist[j]=minDist+p->eInfo; //更新顶点j的最小距离
path[j]=v; //j的前驱改为顶点v
}
p=p->next;
}
}
}
//打印Dijkstra算法结果
void PrintDijkstra(Graph &G, int path[], int dist[], int vID)
{
int sPath[MaxVerNum]; //按顺序保存从vID到目标顶点最短路径上各个顶点的编号
int vPre; //保存前驱顶点编号
int i,j;
int top=-1; //标记vID当目标顶点经过的顶点个数
for(i=1;i<=G.VerNum;i++)
{
cout<<G.VerList[vID].data<<" to "<<G.VerList[i].data;
if(dist[i]==INF)
cout<<" 无可达路径。"<<endl;
else
{
cout<<" 最短距离："<<dist[i]<<endl;
cout<<" 路径：";
}
top++;
sPath[top]=i; //sPath[0]保存当前目标顶点编号i
vPre=path[i]; //取得顶点i的直接前驱到vPre
while(vPre!=-1) //从第i个顶点，通过前驱顶点往前搜索到根结点，给出最短路径途经的顶点序列
{
top++;
sPath[top]=vPre; //当前顶点vPre存入最短路径途径顶点序列数组
vPre=path[vPre]; //取得当前顶点的前驱顶点编号到vPre
}
//依次打印从vID到i顶点的最短路径顶点序列，如果最短路径存在
if(dist[i]!=INF)
{
for(j=top;j>=0;j--) //sPath[top]为指定的起始顶点vID，sPath[0]为顶点i
{
cout<<G.VerList[sPath[j]].data<<" ";
}
}
top=-1; //初始化top，以取得下一个顶点
cout<<endl;
}
}
//Floyd算法
//typedef cellType dist[MaxVerNum][MaxVerNum];
//typedef int path[MaxVerNum][MaxVerNum];
void Floyd(Graph1 &G, cellType dist[MaxVerNum][MaxVerNum], int path[MaxVerNum][MaxVerNum])
{
int i,j,k;
//初始化距离矩阵和路径矩阵
for(i=1;i<=G.VerNum;i++)
{
for(j=1;j<=G.VerNum;j++)
{
dist[i][j]=G.AdjMatrix[i][j]; //距离矩阵初始化为邻接矩阵
//初始化路径矩阵，路径矩阵元素path[i][j]中保存编号j顶点的前驱的顶点编号
if( i!=j && G.AdjMatrix[i][j]<INF) //如果i,j之间存在边，则j的前驱为i。否则前驱置为-1
path[i][j]=i;
else
path[i][j]=-1;
}
}
//从k=1开始，迭代到k=G.verNum。依次选择一个顶点k，作为顶点i、j之间的中转顶点，优化顶点i、j之间的距离
//下面是Floyd算法的核心--三重for循环
for(k=1; k<=G.VerNum; k++)
{
for(i=1; i<=G.VerNum; i++)
{
for(j=1; j<=G.VerNum;j++)
{
if(i!=j && dist[i][k]+dist[k][j]<dist[i][j]) //k作为中转跳点，i、j之间距离变小，接收k作为中转点，更新i、j之间的距离
{
dist[i][j]=dist[i][k]+dist[k][j]; //更新距离
path[i][j]=path[k][j]; //修改前驱顶点
}
}
}
// //打印k顶点作为中转跳点后优化的距离矩阵
// cout<<"第"<<k<<"轮优化后的距离矩阵："<<endl;
// for(i=1;i<=G.VerNum;i++)
// {
// cout<<"\t";
// for(j=1;j<=G.VerNum;j++)
// {
// if((G.gKind==UDN || G.gKind==DN) && dist[i][j]==INF)
// cout<<"INF"<<"\t"; //网，无穷大时，打印“INF”表示
// else
// cout<<dist[i][j]<<"\t";
// }
// cout<<endl;
// }
// //打印k顶点作为中转跳点后优化的路径矩阵
// cout<<"第"<<k<<"轮优化后的路径矩阵："<<endl;
// for(i=1;i<=G.VerNum;i++)
// {
// cout<<"\t";
// for(j=1;j<=G.VerNum;j++)
// {
// cout<<path[i][j]<<"\t";
// }
// cout<<endl;
// }
}
}
//打印Floyd算法给出的最短路径
void PrintFloyd(Graph1 &G, cellType dist[MaxVerNum][MaxVerNum], int path[MaxVerNum][MaxVerNum])
{
int sPath[MaxVerNum]; //定义一个类似栈操作的数组
int pra; //前驱结点编号
int top=-1; //栈顶
int i;
int j;
int m;
for(i=1; i<=G.VerNum; i++)
{
for(j=1; j<=G.VerNum; j++)
{
cout<<G.Data[i]<<" to "<<G.Data[j];
if(dist[i][j]==INF)
cout<<" 无可达路径。"<<endl;
else
{
cout<<" 最短距离："<<dist[i][j]<<endl;
cout<<" 路径：";
top++;
sPath[top]=j; //sPath[0]为当前顶点i
pra=path[i][j]; //i顶点的前驱顶点
while(pra!=i)
{
top++;
sPath[top]=pra;
pra=path[i][pra];
}
top++;
sPath[top]=i; //加进起始顶点i
if(dist[i][j]!=INF)
{
for(m=top;m>=0;m--) //sPath[top]为指定的起始顶点
{
cout<<G.Data[sPath[m]]<<" ";
}
}
top=-1;
cout<<endl;
}
}
}
}
//拓扑排序算法--基于邻接表
//初始化获取每个顶点的入度，存入入度数组inds[]中
void GetInDegrees(Graph &G, int inds[])
{
EdgeNode *p; //边链表指针
int i;
int k;
for(i=1;i<=G.VerNum;i++)
{
p=G.VerList[i].firstEdge;
while(p)
{
k=p->adjVer;
inds[k]++; //编号为k的顶点入度加1
p=p->next;
}
}
}
//拓扑排序算法--使用栈和队列，使用一个标记数组solved[]
int TopologicalSort(Graph &G, int topoList[])
{
int inds[MaxVerNum]; //存放顶点入度
int solvedlen = 0;
int solved[MaxVerNum]; //标记入度为0的顶点是否已经处理。0--未处理；1--已处理。
int i;
int v=-1; //顶点编号
int vCount=0; //记录入度为0的定点数
EdgeNode *p; //指向边链表结点的指针
//初始化
for(i=1;i<=G.VerNum;i++)
{
inds[i]=0; //所有顶点初始入度置为0
topoList[i]=-1; //拓扑序列初始化为-1
}
//从邻接表获取各顶点初始入度
GetInDegrees(G,inds);
//取得第一个入度为0的顶点（如果存在），保存到v
for(i=1;i<=G.VerNum;i++)
{
if(inds[i]==0)
{
solved[solvedlen++] = i;
}
}
while(solvedlen > 0)
{
v = solved[--solvedlen];
topoList[vCount+1]=v;
vCount++;
//以顶点v相邻的顶点入度减1
p=G.VerList[v].firstEdge;
while(p)
{
v=p->adjVer;
inds[v]--; //邻接点入度减1
if(inds[v] == 0){
solved[solvedlen++] = v;
}
p=p->next;
}
}
if(vCount==G.VerNum)
return 1; //拓扑排序成功
else
return 0; //存在回路，拓扑排序失败
}
void PrintKeyPath(Graph1& G, int topoList[], int vet[MaxVerNum], int vlt[MaxVerNum]) {
int v, w;
cout << "其中一条关键路径为：\t";
v = topoList[1];
cout << G.Data[v] << "\t";
while (v != -1) {
w = firstAdj(G, v);
while (w != -1) {
if (vet[w] == vlt[w]) {
cout << G.Data[w] << "\t";
break;
}
else {
w = nextAdj(G, v, w);
}
}
v = w;
}
}
void KeyPath(Graph1& G, int topoList[]) {
int i, j;
int vPre;//保存顶点的前驱顶点编号
int vSuc;//保存顶点的后继顶点编号
int vet[MaxVerNum + 1];
int vlt[MaxVerNum + 1];
for (i = 1; i <= G.VerNum; i++) {//初始化最早发生时间为0
vet[i] = 0;
}
for (i = 1; i <= G.VerNum; i++) {
vPre = topoList[i];
for (j = 1; j <= G.VerNum; j++) {
if (G.AdjMatrix[vPre][j] >= 1 && G.AdjMatrix[vPre][j] < INF) {
if (vet[j] < vet[vPre] + G.AdjMatrix[vPre][j]) {
vet[j] = vet[vPre] + G.AdjMatrix[vPre][j];
}
}
}
}
for (i = 1; i <= G.VerNum; i++) {//初始化vlt值为vet[G.VerNum]
vlt[i] = vet[G.VerNum];
}
for (i = G.VerNum; i >= 1; i--) {//按照逆拓扑次序求解最迟发生时间
vSuc = topoList[i];
for (j = G.VerNum; j >= 1; j--) {
if(G.AdjMatrix[j][vSuc]>=1&&G.AdjMatrix[j][vSuc]<INF){
if (vlt[j] > vlt[vSuc] - G.AdjMatrix[j][vSuc]) {
vlt[j] = vlt[vSuc] - G.AdjMatrix[j][vSuc];
}
}
}
}
PrintKeyPath(G, topoList, vet, vlt);
}
//
//
//
//主函数部分
//
//
#include<iostream>
//#include"createGrpAdjLinkedList.h"
#include"LianTu.h"
//#include"createGrpAdjMatrix.h"
using namespace std;
int main(void){
char strLine[100][3];
char fileName_1[100] = {"udg8.grp"};
char fileName_2[100] = {"udg115.grp"};
char fileName_3[100] = {"dg6.grp"}; //无
char fileName_4[100] = {"f14.grp"};
char fileName_5[100] = {"udn6.grp"}; //无
char fileName_6[100] = {"dn10.grp"};
char fileName_7[100] = {"un8.grp"}; //无
char fileName_8[100] = {"dn8.grp"};//无
char fileName_9[100] = {"Top6dg1.grp"};
char fileName_10[100] = {"Top7dg1.grp"};
Graph G;
Graph1 G1;
csNode *T;
int v0;
int vID;
char v;
int choice;
while(1){
cout << "***************************必做***************************" << endl;
cout << "1.打印出图（网）的两种遍历序。 "<< endl;
cout << "2.求给定图中的边（或弧）的数目。" << endl;
cout << "3.对给定的图G及出发点v0，设计算法从V0出发深" << endl;
cout << " 度优先遍历图G，并构造出相应的生成树或生成森林。 " << endl;
cout << "4.对给定的图G及出发点v0，设计算法从V0出发广" << endl;
cout << " 度优先遍历图G，并构造出相应的生成树或生成森林。 " << endl;
cout << "5.实现Prim算法，求解下列给定图G的最小生成树。" << endl;
cout << "6.实现Kruskal算法，求解下列给定图G的最小生成树。" << endl;
cout << "7.实现Dijkstra算法，求解下列给定图G指定顶点" << endl;
cout << " 到其余顶点之间的最短路径。" << endl;
cout << "8.实现Floyd算法，求解下列给定图G各顶点之间的最短路径。" << endl;
cout << "9.设计算法求解下列给定图G的拓扑序列。" << endl;
cout << "10.设计算法求解下列给定AOE网的关键路径。" << endl;
cout << "11.退出" << endl;
cout << "***************************结束***************************" << endl;
cout << "输入你所需要验证的题号：" << endl;
cin >> choice;
switch(choice){
case 1:
cout << "测试数据为：" << endl;
cout << "第一组数据：udg8.grp" << endl;
if(CreateGraphFromFile(fileName_1, G)){
cout << "图创建成功" << endl;
cout << "深度优先搜索遍历" << endl;
DFSTraverse(G, 1);
cout << "\n广度优先搜索遍历" << endl;
BFSTraverse(G, 1);
//printGraph(G);
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第二组数据：udg115.grp" << endl;
if(CreateGraphFromFile(fileName_2, G)){
cout << "图创建成功" << endl;
cout << "深度优先搜索遍历" << endl;
DFSTraverse(G, 1);
cout << "\n广度优先搜索遍历" << endl;
BFSTraverse(G, 1);
//printGraph(G);
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第三组数据：dg6.grp" << endl;
if(CreateGraphFromFile(fileName_3, G)){
cout << "图创建成功" << endl;
cout << "深度优先搜索遍历" << endl;
DFSTraverse(G, 1);
cout << "\n广度优先搜索遍历" << endl;
BFSTraverse(G, 1);
//printGraph(G);
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第四组数据：f14.grp" << endl;
if(CreateGraphFromFile(fileName_4, G)){
cout << "图创建成功" << endl;
cout << "深度优先搜索遍历" << endl;
DFSTraverse(G, 1);
cout << "\n广度优先搜索遍历" << endl;
BFSTraverse(G, 1);
//printGraph(G);
DestroyGraph(G);
}
cout << endl;
system("pause");
system("cls");
break;
case 2:
cout << "测试数据为：" << endl;
cout << "第一组数据：udg8.grp" << endl;
if(CreateGraphFromFile(fileName_1, G)){
cout << "图创建成功" << endl;
cout << "给定图的边的数目为：" << endl;
cout << G.ArcNum << endl;
cout << Enum(G, 1);
//printGraph(G);
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第二组数据：udg115.grp" << endl;
if(CreateGraphFromFile(fileName_2, G)){
cout << "图创建成功" << endl;
cout << "给定图的边的数目为：" << endl;
cout << G.ArcNum << endl;
cout << Enum(G, 1);
//printGraph(G);
DestroyGraph(G);
}cout << "\n*************************************************************" << endl;
cout << "第三组数据：dg6.grp" << endl;
if(CreateGraphFromFile(fileName_3, G)){
cout << "图创建成功" << endl;
cout << "给定图的边的数目为：" << endl;
cout << G.ArcNum << endl;
cout << Enum(G, 1);
//printGraph(G);
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第四组数据：f14.grp" << endl;
if(CreateGraphFromFile(fileName_4, G)){
cout << "图创建成功" << endl;
cout << "给定图的边的数目为：" << endl;
cout << G.ArcNum << endl;
cout << Enum(G, 1);
//printGraph(G);
DestroyGraph(G);
}
cout << endl;
system("pause");
system("cls");
break;
case 3:
cout << "测试数据为：" << endl;
cout << "第一组数据：udg8.grp" << endl;
if(CreateGraphFromFile(fileName_1, G)){
cout << "图创建成功" << endl;
cout << "深度优先搜索遍历" << endl;
cout << "请输入出发点v0(1 <= v0 <= " << G.VerNum << ")\n";
cin >> v0;
DFS_Traverse(G, T, v0);
cout << "\n森林的先序遍历为：" << endl;
Fist(T);
//printGraph(G);
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第二组数据：dg6.grp" << endl;
if(CreateGraphFromFile(fileName_3, G)){
cout << "图创建成功" << endl;
cout << "深度优先搜索遍历" << endl;
cout << "请输入出发点v0(1 <= v0 <= " << G.VerNum << ")\n";
cin >> v0;
DFS_Traverse(G, T, v0);
cout << "\n森林的先序遍历为：" << endl;
Fist(T);
//printGraph(G);
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第三组数据：un8.grp" << endl;
if(CreateGraphFromFile(fileName_7, G)){
cout << "图创建成功" << endl;
cout << "深度优先搜索遍历" << endl;
cout << "请输入出发点v0(1 <= v0 <= " << G.VerNum << ")\n";
cin >> v0;
DFS_Traverse(G, T, v0);
cout << "\n森林的先序遍历为：" << endl;
Fist(T);
//printGraph(G);
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第四组数据：dn10.grp" << endl;
if(CreateGraphFromFile(fileName_6, G)){
cout << "图创建成功" << endl;
cout << "深度优先搜索遍历" << endl;
cout << "请输入出发点v0(1 <= v0 <= " << G.VerNum << ")\n";
cin >> v0;
DFS_Traverse(G, T, v0);
cout << "\n森林的先序遍历为：" << endl;
Fist(T);
//printGraph(G);
DestroyGraph(G);
}
cout << endl;
system("pause");
system("cls");
break;
case 4:
cout << "测试数据为：" << endl;
cout << "第一组数据：udg8.grp" << endl;
if(CreateGraphFromFile(fileName_1, G)){
cout << "图创建成功" << endl;
cout << "广度优先搜索遍历" << endl;
cout << "请输入出发点v0(1 <= v0 <= " << G.VerNum << ")\n";
cin >> v0;
BFSForest(G, T, v0);
cout << "\n森林的先序遍历为：" << endl;
Fist(T);
//printGraph(G);
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第二组数据：dg6.grp" << endl;
if(CreateGraphFromFile(fileName_3, G)){
cout << "图创建成功" << endl;
cout << "广度优先搜索遍历" << endl;
cout << "请输入出发点v0(1 <= v0 <= " << G.VerNum << ")\n";
cin >> v0;
BFSForest(G, T, v0);
cout << "\n森林的先序遍历为：" << endl;
Fist(T);
//printGraph(G);
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第三组数据：un8.grp" << endl;
if(CreateGraphFromFile(fileName_7, G)){
cout << "图创建成功" << endl;
cout << "广度优先搜索遍历" << endl;
cout << "请输入出发点v0(1 <= v0 <= " << G.VerNum << ")\n";
cin >> v0;
BFSForest(G, T, v0);
cout << "\n森林的先序遍历为：" << endl;
Fist(T);
//printGraph(G);
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第四组数据：dn10.grp" << endl;
if(CreateGraphFromFile(fileName_6, G)){
cout << "图创建成功" << endl;
cout << "广度优先搜索遍历" << endl;
cout << "请输入出发点v0(1 <= v0 <= " << G.VerNum << ")\n";
cin >> v0;
BFSForest(G, T, v0);
cout << "\n森林的先序遍历为：" << endl;
Fist(T);
//printGraph(G);
DestroyGraph(G);
}
cout << endl;
system("pause");
system("cls");
break;
case 5:
cout << "测试数据为：" << endl;
cout << "第一组数据：udn6.grp" << endl;
if(CreateGraphFromFile(fileName_5, G)){
cout << "图创建成功" << endl;
cout<<"请输入Prim算法的起始顶点：\n";
cin >> v;
vID=LocateVertex(G, v);
if(vID==-1){
cout<<endl<<"错误：选择遍历的起始顶点不在图上，算法失败。"<<endl<<endl;
}else{
//初始化已经选定顶点数组
for(int i=1;i<=G.VerNum;i++)
inTree[i]=0; //表示全部没有选定
Prim(G,vID); //执行Prim算法，产生minEdges[]数组
}
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第二组数据：un8.grp" << endl;
if(CreateGraphFromFile(fileName_7, G)){
cout << "图创建成功" << endl;
cout<<"请输入Prim算法的起始顶点：\n";
cin >> v;
vID=LocateVertex(G, v);
if(vID==-1){
cout<<endl<<"错误：选择遍历的起始顶点不在图上，算法失败。"<<endl<<endl;
}else{
//初始化已经选定顶点数组
for(int i=1;i<=G.VerNum;i++)
inTree[i]=0; //表示全部没有选定
Prim(G,vID); //执行Prim算法，产生minEdges[]数组
}
DestroyGraph(G);
}
cout << endl;
system("pause");
system("cls");
break;
case 6:
cout << "测试数据为：" << endl;
cout << "第一组数据：udn6.grp" << endl;
if(CreateGraphFromFile(fileName_5, G)){
cout << "图创建成功" << endl;
Kruskal(G);
DestroyGraph(G);
}
cout << "*************************************************************" << endl;
cout << "第二组数据：un8.grp" << endl;
if(CreateGraphFromFile(fileName_7, G)){
cout << "图创建成功" << endl;
Kruskal(G);
DestroyGraph(G);
}
system("pause");
system("cls");
break;
case 7:
cout << "测试数据为：" << endl;
cout << "第一组数据：udn6.grp" << endl;
if(CreateGraphFromFile(fileName_5, G)){
cout << "图创建成功" << endl;
cout<<"请输入 Dijkstra 算法的起始顶点：";
cin>>v;
vID=LocateVertex(G, v);
if(vID==-1)
{
cout<<endl<<"错误：选择的起始顶点不在图上，搜索失败。"<<endl<<endl;
}else{
int path[MaxVerNum+1];
int dist[MaxVerNum+1];
Dijkstra(G, path, dist, vID);
PrintDijkstra(G, path, dist, vID); //打印最短路径
}
DestroyGraph(G);
}
cout << "*************************************************************" << endl;
cout << "第二组数据：un8.grp" << endl;
if(CreateGraphFromFile(fileName_7, G)){
cout << "图创建成功" << endl;
cout<<"请输入 Dijkstra 算法的起始顶点：";
cin>>v;
vID=LocateVertex(G,v);
if(vID==-1)
{
cout<<endl<<"错误：选择的起始顶点不在图上，搜索失败。"<<endl<<endl;
}else{
int path[MaxVerNum+1];
int dist[MaxVerNum+1];
Dijkstra(G, path, dist, vID);
PrintDijkstra(G, path, dist, vID); //打印最短路径
}
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第三组数据：dn8.grp" << endl;
if(CreateGraphFromFile(fileName_6, G)){
cout << "图创建成功" << endl;
cout<<"请输入 Dijkstra 算法的起始顶点：";
cin>>v;
vID=LocateVertex(G,v);
if(vID==-1)
{
cout<<endl<<"错误：选择的起始顶点不在图上，搜索失败。"<<endl<<endl;
}else{
int path[MaxVerNum+1];
int dist[MaxVerNum+1];
Dijkstra(G, path, dist, vID);
PrintDijkstra(G, path, dist, vID); //打印最短路径
}
DestroyGraph(G);
}
cout << endl;
system("pause");
system("cls");
break;
case 8:
cout << "测试数据为：" << endl;
cout << "第一组数据：udn6.grp" << endl;
if(CreateGrpFromFile1(fileName_5, G1)){
cout << "图创建成功" << endl;
cellType dist1[MaxVerNum][MaxVerNum]; //二维距离矩阵
int path1[MaxVerNum][MaxVerNum]; //二维路径矩阵
Floyd(G1, dist1, path1); //执行Floyd算法
PrintFloyd(G1, dist1, path1);
}
cout << "*************************************************************" << endl;
cout << "第二组数据：un8.grp" << endl;
if(CreateGrpFromFile1(fileName_7, G1)){
cout << "图创建成功" << endl;
cellType dist1[MaxVerNum][MaxVerNum]; //二维距离矩阵
int path1[MaxVerNum][MaxVerNum]; //二维路径矩阵
cout << "图创建成功" << endl;
Floyd(G1, dist1, path1); //执行Floyd算法
PrintFloyd(G1, dist1, path1);
}
cout << "\n*************************************************************" << endl;
cout << "第三组数据：dn8.grp" << endl;
if(CreateGrpFromFile1(fileName_6, G1)){
cout << "图创建成功" << endl;
cellType dist1[MaxVerNum][MaxVerNum]; //二维距离矩阵
int path1[MaxVerNum][MaxVerNum]; //二维路径矩阵
cout << "图创建成功" << endl;
Floyd(G1, dist1, path1); //执行Floyd算法
PrintFloyd(G1, dist1, path1);
}
cout << endl;
system("pause");
system("cls");
break;
case 9:
cout << "测试数据为：" << endl;
cout << "第一组数据：top6dg1.grp" << endl;
if(CreateGraphFromFile(fileName_9, G)){
cout << "图创建成功" << endl;
int topoList[MaxVerNum+1]; //保存拓扑序列的数组
if(TopologicalSort(G, topoList)) //调用拓扑排序算法--使用栈
{
cout<<endl;
cout<<"本图拓扑排序成功。拓扑序列："<<endl;
for(int i=1;i<=G.VerNum;i++) //以顶点元素输出拓扑序列
cout<<G.VerList[topoList[i]].data<<"\t";
cout<<endl<<endl;
}
else
{
cout<<endl<<"本图具有回路，拓扑排序失败。"<<endl<<endl;
}
DestroyGraph(G);
}
cout << "*************************************************************" << endl;
cout << "第二组数据：top7dg1.grp" << endl;
if(CreateGraphFromFile(fileName_10, G)){
cout << "图创建成功" << endl;
int topoList[MaxVerNum+1]; //保存拓扑序列的数组
if(TopologicalSort(G, topoList)) //调用拓扑排序算法--使用栈
{
cout<<endl;
cout<<"本图拓扑排序成功。拓扑序列："<<endl;
for(int i=1;i<=G.VerNum;i++) //以顶点元素输出拓扑序列
cout<<G.VerList[topoList[i]].data<<"\t";
cout<<endl<<endl;
}
else
{
cout<<endl<<"本图具有回路，拓扑排序失败。"<<endl<<endl;
}
DestroyGraph(G);
}
cout << "\n*************************************************************" << endl;
cout << "第三组数据：dn8.grp" << endl;
if(CreateGraphFromFile(fileName_6, G)){
cout << "图创建成功" << endl;
int topoList[MaxVerNum+1]; //保存拓扑序列的数组
if(TopologicalSort(G, topoList)) //调用拓扑排序算法--使用栈
{
cout<<endl;
cout<<"本图拓扑排序成功。拓扑序列："<<endl;
for(int i=1;i<=G.VerNum;i++) //以顶点元素输出拓扑序列
cout<<G.VerList[topoList[i]].data<<"\t";
cout<<endl<<endl;
}
else
{
cout<<endl<<"本图具有回路，拓扑排序失败。"<<endl<<endl;
}
DestroyGraph(G);
}
cout << endl;
system("pause");
system("cls");
break;
case 10:
cout << "测试数据为：" << endl;
cout << "第一组数据：top6dg1.grp" << endl;
if(CreateGraphFromFile(fileName_9, G)){
cout << "图创建成功" << endl;
CreateGrpFromFile1(fileName_9, G1);
int topoList[MaxVerNum + 1]; //保存拓扑序列的数组
TopologicalSort(G, topoList);
cout<<endl;
cout<<"本图拓扑排序成功。拓扑序列："<<endl;
for(int i=1;i<=G.VerNum;i++) //以顶点元素输出拓扑序列
cout<<G.VerList[topoList[i]].data<<"\t";
cout<<endl;
KeyPath(G1,topoList);//调用拓扑排序算法--使用栈
}
cout << endl;
system("pause");
system("cls");
break;
case 11:
cout << "再见！" << endl;
return 0;
}
}
return 0;
}到了这里，关于数据结构实验———图实验的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
