#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define NULL 0
typedef int Status;
#include
#include
#include
/*-------------------*/
/***以下是"图"相关定义***/
typedef char VertexType;
//本程序选用ASCII字符区分各顶点#define IOTYPE "%c"
//VertexType的输入输出格式
#define MAX_VER_NUM 19
//最大支持的顶点数,说明见下#define NOTFOUND MAX_VER_NUM+1
//找不到顶点位置时的返回值
#define INFINITY 1000
//"无穷大" ∞
typedef unsigned VRType,AdjMatrix[MAX_VER_NUM][MAX_VER_NUM]; //带权的弧(Arc),以及邻接矩阵类型定义
//以unsigned类型存放权值,但DOS字符界面下横排仅有80个字符宽
//为了完整的显示邻接矩阵,权值不能超过三位数,顶点数不能超过19 typedef enum{DG,DN,UDG,UDN} GraphKind; //标明"图"种类的枚举型变量
typedef struct
{VertexType vexs[MAX_VER_NUM]; //顶点信息数组
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //当前的顶点数和弧数
GraphKind kind;} //图的种类
MGraph; //邻接矩阵表示的"图"之结构体
typedef Status PathMatrix[MAX_VER_NUM][MAX_VER_NUM];
//用于存放"最短路径上的顶点标记"的矩阵类型定义
typedef unsigned ShortPathTable[MAX_VER_NUM];
//用于存放"各顶点的最短路径长度"的数组类型定义
/*
C++/C 中的数组下标从零开始,而数据结构中经常不用零号位!
例如本程序中的MGraph.vexs[ ]数组(存放顶点信息)用零号位,
但visited[ ](存放顶点的访问标记)数组不用.
为了方便起见,也为了区分清楚,特以i/j 表示数组下标(从0开始);
以u/v/w/n 表示顶点编号(从1开始)--在visited[ ]数组中
同时也是数组下标,因为不使用零号位.
另外如head等指针在进行加减或比较运算时的标准同"下标".
*/
unsigned LocateVex(MGraph G,VertexType v); //在图G中查找值为v的顶点,并返回其位置
unsigned FirstAdjVex(MGraph G,unsigned n); //返回编号为n顶点的第一个邻接顶点unsigned NextAdjVex(MGraph G,unsigned n,unsigned adj);
//返回编号为n顶点的,相对其邻接顶点adj的下一个邻接顶点
void CreateGraph(MGraph &G,GraphKind kind); //采用邻接矩阵表示法,构造kind类型的图G
void ShowGraph(MGraph G); //显示图G的所有信息
void DFS(MGraph G,unsigned v); //从第v个顶点出发,深度优先遍历图G。
void DFSTraverse(MGraph G,Status (* Visit)(MGraph G,unsigned v)); //对图G用Visit"深度优先遍历"
void BFSTraverse(MGraph G,Status (* Visit)(MGraph G,unsigned v));
//对图G用Visit"广度优先遍历",使用队列Q存放访问优先次序
Status ShowVertex(MGraph G,unsigned v); //显示顶点v之值的接口函数,用以展示遍历序列
void ShortestPath_DIJ(MGraph G,unsigned v0,PathMatrix &P,ShortPathTable &D); //Dijkstra算法: 求从有向网G的'(v0)+1'号顶点到其余各顶点之
//最短路径P[v] 及路径的带权长度D[v]. 并列表显示之
/***以下是"队列"相关定义***/
#define MAXQSIZE MAX_VER_NUM+1
//循环队列将多用一个元素空间以区分"满"与"空"
typedef unsigned QElemType;
//unsigned型,用以存放顶点编号(从一开始)
typedef struct
{QElemType *base; //队列起始位
int front,rear;} //首/尾下标,front标示列首元素
//rear标示列尾元素后一位置
SqQueue; //用数组存储的"循环队列"数据结构
Status InitQueue(SqQueue &Q); //初始化一个空队列Q
int QueueLength(SqQueue Q); //返回队列Q的长度
inline Status QueueEmpty(SqQueue Q); //判断队列Q是否为空inline Status QueueFull(SqQueue Q); //判断队列Q是否为满
Status EnQueue(SqQueue &Q,QElemType e); //元素e进入队列Q
Status DeQueue(SqQueue &Q,QElemType &e); //队列Q的队首元素出列,并将其值赋给
e
/***以下是"队列"子程序***/
Status InitQueue(SqQueue &Q)
//初始化一个空队列Q
{Q.base=new QElemType[MAXQSIZE];
if(!Q.base) exit(OVERFLOW); //开辟空间失败
Q.front=Q.rear=0;
return OK;} //InitQueue
int QueueLength(SqQueue Q)
//返回队列Q的长度
{return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;} //QueueLength // ~~~~~~~~~~~~~~ 可能<0,故"+MAXQSIZE"
inline Status QueueEmpty(SqQueue Q)
//判断队列Q是否为空
{if(Q.front==Q.rear) return TRUE;
else return FALSE;} //QueueEmpty inline Status QueueFull(SqQueue Q)
//判断队列Q是否为满
{if(Q.front== (Q.rear+1)%MAXQSIZE) return TRUE;
else return FALSE;} //QueueFull
Status EnQueue(SqQueue &Q,QElemType e)
//元素e进入队列Q
{if(QueueFull(Q)) return ERROR; //队列满
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE; //以"%"实现可能的回卷return OK;} //EnQueue
Status DeQueue(SqQueue &Q,QElemType &e)
//队列Q的队首元素出列,并将其值赋给e
{if(QueueEmpty(Q)) return ERROR; //队列空
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE; //以"%"实现可能的回卷return OK;} //DeQueue
/***以下是"图"子程序***/
unsigned LocateVex(MGraph G,VertexType v)
//在图G中查找值为v的顶点,并返回其位置
{int i;
for(i=0;i if(G.vexs[i]==v) return i; //返回数组下标 return NOTFOUND;} //LocateVex unsigned FirstAdjVex(MGraph G,unsigned n) //返回编号为n顶点的第一个邻接顶点 {VRType *head,dflt; //default VR value int ano=G.vexnum; //剩余最多可搜索弧数 if(G.kind==DG||G.kind==UDG) dflt=0; //图 else if(G.kind==DN||G.kind==UDN) dflt=INFINITY; //网else exit(ERROR); for(head=G.arcs[n-1]; *head==dflt && ano; head++,ano--); if(!ano) head--; //防止head越界 if(*head!=dflt) return head-G.arcs[n-1]+1; //返回顶点编号//Creat时约定VertexNumber>=2,可防止head不动else return NOTFOUND; } //FirstAdjVex unsigned NextAdjVex(MGraph G,unsigned n,unsigned adj) //返回编号为n顶点的,相对其邻接顶点adj的下一个邻接顶点 {VRType *head,dflt; //default VR value int ano=G.vexnum-adj; //剩余最多可搜索弧数 if(G.kind==DG||G.kind==UDG) dflt=0; //图 else if(G.kind==DN||G.kind==UDN) dflt=INFINITY; //网 else exit(ERROR); for(head=G.arcs[n-1]+adj; *head==dflt && ano; head++,ano--); //从adj后一条边/弧开始搜索 if(!ano) head--; //防止head越界,但可能造成head不动 if(*head!=dflt && head!=G.arcs[n-1]+adj-1) return head-G.arcs[n-1]+1; //防止head不动~~ \\返回顶点编号 // "-1"是因为head指针按"下标"标准运算, // 而adj是顶点编号(从1开始) else return NOTFOUND; } //NextAdjVex void CreateGraph(MGraph &G,GraphKind kind) //采用邻接矩阵表示法,构造kind类型的图G {int vno,ano,i,j,k; back1: cout<<"\nThe Vertex_Number="; cin>>vno; //输入顶点数 if(vno<2 || vno>=MAX_VER_NUM) {cout<<"非法的顶点数,请重新输入!"; goto back1; } //if back2: cout<<"The Arc_Number="; cin>>ano; //输入弧数 if(kind==DG||kind==DN) {if(ano<0 || ano>(vno-1.0)*vno) {cout<<"非法的弧数,请重新输入!\n"; goto back2; } //if } //if else if(kind==UDG||kind==UDN) {if(ano<0 || ano>(vno-1.0)*vno/2) {cout<<"非法的边数,请重新输入!\n"; goto back2; } //if } //if G.vexnum=vno,G.arcnum=ano; G.kind=kind; cout<<"\n请依次输入各顶点的信息(字符型),不得重复:\n"; for(i=0;i {cout<<"V"<<(i+1)<<" = "; cin>>G.vexs[i]; //输入顶点信息 for(j=0;j if(G.vexs[j]==G.vexs[i]) //输入的信息与先前信息重复 {i--; //重新输入 cout<<"\n请勿输入重复的信息,详见V"<<(j+1)< continue; } //if for j } //for i 构建顶点信息数组 VertexType vt,vh; //弧尾(tail) / 弧头(head) 顶点值 VRType w; //权重 cout<<"\n请务必按格式输入所有弧或边的信息:\n"; if(kind==DG||kind==UDG) //构建"图"的相关操作 {for(i=0;i for(j=0;j //初始化邻接矩阵,"图"以0表示非邻接 cout<<"输入格式: tail,head if(kind==DG) //有向图 for(k=0;k {cout<<"A"<<(k+1)<<" : "; cin>>vt>>','>>vh; if(vt==vh) //两点是同一者 {k--; cout<<"不能和自身相连,请重新输入\n"; continue; } //if vt==vh i=LocateVex(G,vt); //vt定位 j=LocateVex(G,vh); //vh定位 if(i==NOTFOUND||j==NOTFOUND) //找不到 {k--; cout<<"找不到相应的顶点,请重新输入\n"; continue; } //if NOTFOUND if(G.arcs[i][j]) //已赋值 {k--; cout<<"重复赋值错误,请重新输入\n"; continue; } //if G.arcs[i][j]!=0 G.arcs[i][j]=1; //建立一段弧 } //for if DG else //无向图 for(k=0;k {cout<<"E"<<(k+1)<<" : "; cin>>vt>>','>>vh; if(vt==vh) //两点是同一者 {k--; cout<<"不能和自身相连,请重新输入\n"; continue; } //if vt==vh i=LocateVex(G,vt); j=LocateVex(G,vh); if(i==NOTFOUND||j==NOTFOUND) //找不到 {k--; cout<<"找不到相应的顶点,请重新输入\n"; continue; } //if INFINITY if(G.arcs[i][j]) //已赋值 {k--; cout<<"重复赋值错误,请重新输入\n"; continue; } //if G.arcs[i][j]!=0 G.arcs[i][j]=G.arcs[j][i]=1; //建立一对对称弧 } //for if UDG } //if DG||UDG else //构建"网"的相关操作 {for(i=0;i for(j=0;j //初始化邻接矩阵,"网"以INFINITY表示非邻接 cout<<"输入格式: tail,head,weight if(kind==DN) //有向网 for(k=0;k {cout<<"A"<<(k+1)<<" : "; cin>>vt>>','>>vh>>','>>w; if(vt==vh) //两点是同一者 {k--; cout<<"不能和自身相连,请重新输入\n"; continue; } //if vt==vh i=LocateVex(G,vt); //vt定位 j=LocateVex(G,vh); //vh定位 if(i==NOTFOUND||j==NOTFOUND) //找不到 {k--; cout<<"找不到相应的顶点,请重新输入\n"; continue; } //if INFINITY if(w>=INFINITY) //权值过大 {k--; cout<<"权值不得超过三位数,请重新输入\n"; continue; } //if INFINITY if(G.arcs[i][j]!=INFINITY) //已赋值 {k--; cout<<"重复赋值错误,请重新输入\n"; continue; } //if G.arcs[i][j]!=INFINITY G.arcs[i][j]=w; //建立一段弧 } //for if DN else //无向网 for(k=0;k {cout<<"E"<<(k+1)<<" : "; cin>>vt>>','>>vh>>','>>w; if(vt==vh) //两点是同一者 {k--; cout<<"不能和自身相连,请重新输入\n"; continue; } //if vt==vh i=LocateVex(G,vt); j=LocateVex(G,vh); if(i==NOTFOUND||j==NOTFOUND) //找不到 {k--; cout<<"找不到相应的顶点,请重新输入\n"; continue; } //if INFINITY if(w>=INFINITY) //权值过大 {k--; cout<<"权值不得超过三位数,请重新输入\n"; continue; } //if INFINITY if(G.arcs[i][j]!=INFINITY) //已赋值 {k--; cout<<"重复赋值错误,请重新输入\n"; continue; } //if G.arcs[i][j]!=INFINITY G.arcs[i][j]=G.arcs[j][i]=w; //建立一对对称弧 } //for else UDN } //if DN||UDN cout<<"\n-----------------------------"; cout<<"\n\tInputing End!\n\n"; } //CreateGraph void ShowGraph(MGraph G) //显示图G的所有信息 {int vno,ano,i,j; vno=G.vexnum,ano=G.arcnum; cout<<"The Vertex_Number ="< switch(G.kind) {case DG: cout<<"有向图"; break; case DN: cout<<"有向网"; break; case UDG:cout<<"无向图"; break; case UDN:cout<<"无向网"; break; default: cout<<"类型错误"; } //switch cout< cout<<"\n顶点信息:"; cout<<"\nVertex: "; for(i=0;i printf("V%-2d ",i+1); cout<<"\n Value: "; for(i=0;i printf(" " IOTYPE " ",G.vexs[i]); cout<<"\n\nPress 'Enter' to continue!\n"; getchar(); cout<<"\n邻接矩阵:"; printf("\n |"); for(i=1;i<=vno;i++) printf(" %3d",i); printf("\n"); for(i=0;i<3+4*vno;i++) printf("-"); printf("\n"); for(i=0;i {for(j=0;j {if(!j) printf("%2d|",i+1); if(G.arcs[i][j]>=INFINITY) {cout<<" ∞"; continue; } //if >= printf(" %3d",G.arcs[i][j]); } //for j printf("\n"); } //for i cout<<"\n\n------------------------"; cout<<"\n\tShowing Ended!\n\n"; } //ShowGraph Status visited[MAX_VER_NUM+1]; //存放是否访问过的标记,0号位闲置Status (* VisitFunc)(MGraph G,unsigned v); //全局函数变量(首地址) void DFS(MGraph G,unsigned v) //从第v个顶点出发,深度优先遍历图G。 {unsigned w; visited[v]=TRUE; //标记为"已访问" VisitFunc(G,v); //Visit图G的第v个顶点 for(w=FirstAdjVex(G,v); w!=NOTFOUND; w=NextAdjVex(G,v,w)) if(!visited[w]) DFS(G,w); //对v的"未访问"邻接点w调用DFS } //DFS void DFSTraverse(MGraph G,Status (* Visit)(MGraph G,unsigned v)) //对图G用Visit"深度优先遍历" {unsigned v; VisitFunc=Visit; //使用全局变量,则DFS不必传函数指针 for(v=1;v<=G.vexnum;v++) visited[v]=FALSE; //初始化访问标记数组 for(v=1;v<=G.vexnum;v++) if(!visited[v]) DFS(G,v); //若顶点v"未访问"则调用DFS } //DFSTraverse void BFSTraverse(MGraph G,Status (* Visit)(MGraph G,unsigned v)) //对图G用Visit"广度优先遍历",使用队列Q存放访问优先次序{unsigned u,v,w; SqQueue Q; for(v=1;v<=G.vexnum;v++) visited[v]=FALSE; //初始化访问标记数组InitQueue(Q); //初始化辅助队列Q for(v=1;v<=G.vexnum;v++) if(!visited[v]) //v尚未访问 {visited[v]=TRUE; //标记为"已访问" Visit(G,v); //Visit图G的第v个顶点 EnQueue(Q,v); //v入队列 while(!QueueEmpty(Q)) {DeQueue(Q,u); //队首元素出队并置为u for(w=FirstAdjVex(G,u); w!=NOTFOUND; w=NextAdjVex(G,u,w)) if(!visited[w]) {visited[w]=TRUE; //标记为"已访问" Visit(G,w); //Visit图G的第w个顶点 EnQueue(Q,w); //w入队列 } //if for w //访问u的"未访问"邻接点w,并将w入队列Q } //while } //if for v } //BFSTraverse Status ShowVertex(MGraph G,unsigned v) //显示顶点v之值的接口函数,用以展示遍历序列 {printf(IOTYPE " -> ",G.vexs[v-1]);} //ShowVertex void ShortestPath_DIJ(MGraph G,unsigned v0,PathMatrix &P,ShortPathTable &D) //Dijkstra算法: 求从有向网G的'(v0)+1'号顶点到其余各顶点之 //最短路径P[v] 及路径的带权长度D[v]. 并列表显示之 //若P[v][w]==TRUE,则w是从源点到v+1最短路径上的顶点, //若S[v]!=0,表示v∈集合S,已求得从源点到v+1的最短路径.(详见下) {unsigned i,j,v,w,min,vno=G.vexnum; //min临时存放"当前最短路径长度" //为了和课本保持一致,此处的i,j,v,w均表示"下标" (从0开始) // ~~~~~~~~~~~~~~~ ☆☆☆☆☆//称呼顶点时一概用"x+1点", x=i,j,v,w,v0 unsigned S[MAX_VER_NUM]; //集合S的标记数组,0表示'不在'集合S内; //非0表示'在',且数字越大进入的时间越晚 for(v=0;v {S[v]=NULL; //置集合S为空集 D[v]=G.arcs[v0][v]; //默认路径长度为"直接相连"的长度 for(w=0;w if(D[v] {P[v][v0]=TRUE; P[v][v]=TRUE; //v+1 AND v0+1 均在路径上 } //if } //for v D[v0]=0; //v0->v0 长度为0 S[v0]=1; //v0顶点加入S集 /*以上完成了初始化 再简要提示一遍: P:路径顶点矩阵 D:路径长度数组 S:集合标记数组 */ //下面开始主循环,每次求得源点到某个顶点v+1的最短路径,并加入S集 Status change_v; //标记v是否已改变,防止重复写S[v] for(i=1;i {min=INFINITY; //考虑到可能有"无路可通"的点,默认的最近距离为∞ change_v=FALSE; for(w=0;w if(!S[w] && D[w] {v=w; //更改"下一最近顶点" min=D[w]; //更改"下一最短路径长度" change_v=TRUE; //v已改变 } //if && //for w if(change_v) S[v]=i+1; //下一最近顶点加入S集 for(w=0;w if(!S[w] && (min+G.arcs[v][w] //min对应的是"新加入的" 顶点v的"最短路径" {D[w]=min+G.arcs[v][w]; //更新最短路径长度数组D[w] for(j=0;j //更新最短路径顶点矩阵的P[w][ ] 分量为P[v][ ] P[w][w]=TRUE; //将自身加入路径 //w的路径P[w][ ] = P[v][ ] + P[w][w] } //if && //for w } //for i //下面显示刚刚求得的最短路径及其长度 unsigned Sequence[MAX_VER_NUM]; //按"进入集合S的顺序"存放各顶点下标位置的数组 unsigned SqLen; //Sequence数组的有效长度 for(i=1,SqLen=0;i<=vno;i++,SqLen++) //搜索"进入集合S的次序"为i的顶点{for(j=0;j if(S[j]==i) break; //找到"进入次序"为i的顶点(j+1) //该break跳出for j 内循环 if(j==vno) break; //if 找不到次序为i的顶点,则次序>i者亦不存在,停止搜索 //该break跳出for i 外循环,则本轮SqLen不++ Sequence[i-1]=j; //"第i个进入S"的顶点(j+1),其下标为j } //for i 该循环建立了集合S按照"进入顺序"排列的索引 printf("\n\n\n\n 路径的源点: V%u (",v0+1); printf( IOTYPE ")\n\n",G.vexs[v0]); printf("==================================\n"); printf("终点(值) 长度最短路径的顶点序列\n"); printf("----------------------------------\n"); for(i=0;i {if(i==v0) continue; //跳过源点自身 printf(" V%u (" IOTYPE ") ",i+1,G.vexs[i]); //终点编号 if(!S[i]) printf(" ∞无,不可通\n"); //此路不通 else {printf("%6u ",D[i]); //路径长度 for(j=0;j if(P[i][Sequence[j]]) printf(IOTYPE "→",G.vexs[Sequence[j]]); //if for j 依照路径顺序打印各顶点编号 printf("\b\b \n"); //抹去最后多余的"→"两个字符,并换行 } //if-else } //for i printf("==================================\n\n"); printf("Dijkstra算法求V%u (" IOTYPE,v0+1,G.vexs[v0]); printf(")的'单源最短路径'演示完毕!\n\n"); } //ShortestPath_DIJ /***以下是"图"主控程序***/ main() {MGraph G; GraphKind kind; int choice; cout<<"Copyright(c) Marine.Marion马瑞,All Rights Reserved!\n"; cout<<"Email : marion@https://www.doczj.com/doc/d618791791.html, / m_marion@https://www.doczj.com/doc/d618791791.html,\n"; cout<<"Mobile: 131********\n"; cout<<"\n\t******************************************\n"; cout<<"\tFunctions of DataStructure 'Graph' Release\n"; cout<<"\t******************************************\n\n"; cout<<"本程序选用ASCII字符区分各顶点,顶点的值互不相同.\n"; cout<<"最大支持"< cout<<"支持的'图'类型有:DG,DN,UDG,UDN.\n"; cout<<"分别表示: 有向图,有向网,无向图,无向网.\n"; cout<<"\n"; cout<<"Press 'Enter' to continue!\n"; getchar(); again1: cout<<"\n请用数字选择你将要建立的图的类型\n"; cout<<"1)DG, 2)DN, 3)UDG, 4)UDN :\n"; cin>>choice; switch(choice) {case 1:kind=DG; break; case 2:kind=DN; break; case 3:kind=UDG; break; case 4:kind=UDN; break; default:cout<<"\nWrong Choice!\n"; goto again1; } //switch CreateGraph(G,kind); cout<<"Press 'Enter' to continue!\n"; getchar(); cout<<"\n已建立的图是:\n"; ShowGraph(G); cout<<"Press 'Enter' to continue!\n\n"; getchar(); cout<<"\n对该图进行深度优先遍历(DFS)得到的顶点访问序列为:\n"; DFSTraverse(G,ShowVertex); cout<<"结束\n"; cout<<"\n对该图进行广度优先遍历(BFS)得到的顶点访问序列为:\n"; BFSTraverse(G,ShowVertex); cout<<"结束\n"; cout<<"\n Create a new Graph again?(y/n)"; //重新建立一幅图进行演示 if(getchar()=='y') {getchar(); //清回车 goto again1; } //if cout<<"\n\n\t--------------------------------------\n"; cout<<"\t下面演示Dijkstra 算法求'单源最短路径'\n"; cout<<"\t--------------------------------------\n"; again2: cout<<"\n请重新输入一个有向网(DN):\n"; CreateGraph(G,DN); cout<<"Press 'Enter' to continue!\n"; getchar(); cout<<"\n已建立的有向网是:\n"; ShowGraph(G); cout<<"Press 'Enter' to continue!\n"; getchar(); VertexType value; unsigned position; PathMatrix PM; //存放"顶点是否在路径上"标记的矩阵ShortPathTable SPT; //存放"从源点到各顶点最短路径"的数组 back: cout<<"\n选择一个顶点做源点,请输入它的值: "; cin>>value; position=LocateVex(G,value); //value定位 //注意position是数组下标if(position==NOTFOUND) //找不到 {cout<<"找不到相应的顶点,请重新输入!\n\n"; goto back; } //if NOTFOUND ShortestPath_DIJ(G,position,PM,SPT); cout<<"是否另选择一个顶点做源点?(y/n)"; if(getchar()=='y') {getchar(); //清回车 goto back; } //if getchar(); //清回车 cout<<"\n Try 'Dijkstra' in another Graph?(y/n)"; //换一幅图演示Dijkstra算法 if(getchar()=='y') {getchar(); //清回车 cout< goto again2; } //if cout<<"\n\n--------------------------------\n"; cout<<"Thank you for use this Software!\n"; cout<<"\tPowered by 马瑞"; } //main 请重新输入一个有向网(DN): The Vertex_Number=6 The Arc_Number=8 请依次输入各顶点的信息(字符型),不得重复: V1 = 0 V2 = 1 V3 = 2 V4 = 3 V5 = 4 V6 = 5 请务必按格式输入所有弧或边的信息: 输入格式: tail,head,weight A1 : 0,5,100 A2 : 0,4,30 A3 : 4,5,60 A4 : 4,3,20 A5 : 3,5,10 A6 : 0,2,10 A7 : 1,2,5 A8 : 2,3,50 ----------------------------- Inputing End! Press 'Enter' to continue! 已建立的有向网是: The Vertex_Number =6 The Arc/Edge_Number =8 The GraphKind: 有向网 顶点信息: Vertex: V1 V2 V3 V4 V5 V6 Value: 0 1 2 3 4 5 Press 'Enter' to continue! 邻接矩阵: | 1 2 3 4 5 6 --------------------------- 1| ∞∞ 10 ∞ 30 100 2| ∞∞ 5 ∞∞∞ 3| ∞∞∞ 50 ∞∞ 4| ∞∞∞∞∞ 10 5| ∞∞∞ 20 ∞ 60 6| ∞∞∞∞∞∞ ------------------------ Showing Ended! Press 'Enter' to continue! 选择一个顶点做源点,请输入它的值: 0 路径的源点: V1 (0) ================================== 终点(值) 长度最短路径的顶点序列 ---------------------------------- V2 (1) ∞无,不可通 V3 (2) 10 0→2 V4 (3) 50 0→4→3 V5 (4) 30 0→4 V6 (5) 60 0→4→3→5 ================================== Dijkstra算法求V1 (0)的'单源最短路径'演示完毕! 是否另选择一个顶点做源点?(y/n)n Try 'Dijkstra' in another Graph?(y/n)y 请重新输入一个有向网(DN): The Vertex_Number=3 The Arc_Number=2 请依次输入各顶点的信息(字符型),不得重复: V1 = a V2 = b V3 = c 请务必按格式输入所有弧或边的信息: 输入格式: tail,head,weight A1 : a,b,55 A2 : b,c,66 ----------------------------- Inputing End! Press 'Enter' to continue! 已建立的有向网是: The Vertex_Number =3 The Arc/Edge_Number =2 The GraphKind: 有向网 顶点信息: Vertex: V1 V2 V3 Value: a b c Press 'Enter' to continue! 邻接矩阵: | 1 2 3 --------------- 1| ∞ 55 ∞ 2| ∞∞ 66 3| ∞∞∞ ------------------------ Showing Ended! Press 'Enter' to continue! 选择一个顶点做源点,请输入它的值: b 路径的源点: V2 (b) ================================== 终点(值) 长度最短路径的顶点序列 ---------------------------------- V1 (a) ∞无,不可通 V3 (c) 66 b→c ================================== Dijkstra算法求V2 (b)的'单源最短路径'演示完毕! 是否另选择一个顶点做源点?(y/n)y 选择一个顶点做源点,请输入它的值: a 路径的源点: V1 (a) ================================== 终点(值) 长度最短路径的顶点序列 ---------------------------------- V2 (b) 55 a→b V3 (c) 121 a→b→c ================================== Dijkstra算法求V1 (a)的'单源最短路径'演示完毕!
相关主题
文本预览