数据结构课程设计——图的建立和遍历(邻接矩阵+邻接表)和最短路径dijkstra路径记录
#include<iostream>
#include<>
#include <>
#include<string>
#include<>
#include<queue>
#include<>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAX_VERTEX_NUM 105
#define INFINITY 0X3f3f3f3f
typedef char InfoType;
typedef int Status;
typedef int Boolean;
typedef string VertexType;
typedef enum {DG,DN,UDG,UDN} GraphKind;
Boolean visited[MAX_VERTEX_NUM];
typedef struct ArcCell///弧(邻接矩阵)
{
int adj;
InfoType *info;
} ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct///图(邻接矩阵)
{
string vexs[MAX_VERTEX_NUM];///结点名
AdjMatrix arcs; ///邻接矩阵
int vexnum,arcnum; ///结点数，弧数
GraphKind kind;
} MGraph;
Status (*VisitFunc)(MGraph G,int v);
Status LocateVex(MGraph G,string name)///获取结点标号
{
for(int i=0; i<; i++)
if(name==[i])return i;
return -1;
}
Status CreateDG(MGraph &G)///邻接矩阵(建立无权有向图)
{
int IncInfo;
printf("建立无权有向图，请依次输入总结点数、总边数、是否包含信息(0不包含、1包含):\n");
scanf("%d%d%d",&,&,&IncInfo);
while(>*(-1)/2||<-1)
{
if(>*(-1)/2)printf("边数输入错误,边数过多,超过完全图最大边数，请重新输入:\n");
if(<-1)printf("边数输入错误,边数不足以形成连通图,请重新输入:\n");
scanf("%d%d%d",&,&,&IncInfo);
}
printf("请为从1至%d个结点命名:\n",);
for(int i=0; i<; i++)cin>>[i];
for(int i=0; i<; i++)
for(int j=0; j<; j++)[i][j].adj=INFINITY,[i][j].info=NULL;
string v1,v2;
printf("请输入%d组由左指向右的有向边(x--->y):\n",);
for(int k=0; k<; k++)
{
cout<<"第"<<k+1<<"条边:";
cin>>v1>>v2;
int i=LocateVex(G,v1);
int j=LocateVex(G,v2);
if(i==-1||j==-1)
{
if(i==-1||j==-1)printf("输入的结点名不存在，请重新输入\n");
k--;
continue;
}
[i][j].adj=TRUE;///无权
if(IncInfo)scanf("%s",[i][j].info);
}
return OK;
}
Status CreateDN(MGraph &G)///邻接矩阵(建立带权有向网)
{
int IncInfo;
printf("建立带权有向网，请依次输入总结点数、总边数、是否包含信息(0不包含、1包含):\n");
scanf("%d%d%d",&,&,&IncInfo);
while(>*(-1)/2||<-1)
{
if(>*(-1)/2)printf("边数输入错误,边数过多,超过完全图最大边数，请重新输入:\n");
if(<-1)printf("边数输入错误,边数不足以形成连通图,请重新输入:\n");
scanf("%d%d%d",&,&,&IncInfo);
}
printf("请为从1至%d个结点命名:\n",);
for(int i=0; i<; i++)cin>>[i];
for(int i=0; i<; i++)
for(int j=0; j<; j++)[i][j].adj=INFINITY,[i][j].info=NULL;
string v1,v2;
int w;
printf("请输入%d组由左指向右的有向边与边权(x--->y 边权:z):\n",);
for(int k=0; k<; k++)
{
cout<<"第"<<k+1<<"条边:";
cin>>v1>>v2>>w;
int i=LocateVex(G,v1);
int j=LocateVex(G,v2);
if(i==-1||j==-1||w<=0||w>1000000000)
{
if(i==-1||j==-1)printf("输入的结点名不存在，请重新输入\n");
if(w<=0||w>1000000000)printf("输入的边权错误,请重新输入\n");
k--;
continue;
}
[i][j].adj=w;///带权
if(IncInfo)scanf("%s",[i][j].info);
}
return OK;
}
Status CreateUDG(MGraph &G)///邻接矩阵(建立无权无向图)
{
int IncInfo;
printf("建立无权无向图，请依次输入总结点数、总边数、是否包含信息(0不包含、1包含):\n");
scanf("%d%d%d",&,&,&IncInfo);
while(>*(-1)/2||<-1)
{
if(>*(-1)/2)printf("边数输入错误,边数过多,超过完全图最大边数，请重新输入:\n");
if(<-1)printf("边数输入错误,边数不足以形成连通图,请重新输入:\n");
scanf("%d%d%d",&,&,&IncInfo);
}
printf("请为从1至%d个结点命名:\n",);
for(int i=0; i<; i++)cin>>[i];
for(int i=0; i<; i++)
for(int j=0; j<; j++)[i][j].adj=INFINITY,[i][j].info=NULL;
string v1,v2;
printf("请输入%d组相互依附的两结点:\n",);
for(int k=0; k<; k++)
{
cout<<"第"<<k+1<<"条边:";
cin>>v1>>v2;
int i=LocateVex(G,v1);
int j=LocateVex(G,v2);
if(i==-1||j==-1)
{
if(i==-1||j==-1)printf("输入的结点名不存在，请重新输入\n");
k--;
continue;
}
[i][j].adj=TRUE;///无权
if(IncInfo)scanf("%s",[i][j].info);
[j][i]=[i][j];///无向图,结构体赋值
}
return OK;
}
Status CreateUDN(MGraph &G)///邻接矩阵(建立带权无向网)
{
int IncInfo;
printf("建立带权无向网，请依次输入总结点数、总边数、是否包含信息(0不包含、1包含):\n");
scanf("%d%d%d",&,&,&IncInfo);
while(>*(-1)/2||<-1)
{
if(>*(-1)/2)printf("边数输入错误,边数过多,超过完全图最大边数，请重新输入:\n");
if(<-1)printf("边数输入错误,边数不足以形成连通图,请重新输入:\n");
scanf("%d%d%d",&,&,&IncInfo);
}
printf("请为从1至%d个结点命名:\n",);
for(int i=0; i<; i++)cin>>[i];
for(int i=0; i<; i++)
for(int j=0; j<; j++)
[i][j].adj=INFINITY,[i][j].info=NULL;
string v1,v2;
printf("请输入%d组相互依附的两结点与边权(x<--->y 边权:z):\n",);
int w;///边权
for(int k=0; k<; k++)
{
cout<<"第"<<k+1<<"条边:";
cin>>v1>>v2>>w;
int i=LocateVex(G,v1);
int j=LocateVex(G,v2);
if(i==-1||j==-1||w<=0||w>1000000000)
{
if(i==-1||j==-1)printf("输入的结点名不存在，请重新输入\n");
if(w<=0||w>1000000000)printf("输入的边权错误,请重新输入\n");
k--;
continue;
}
[i][j].adj=w;///带权
if(IncInfo)scanf("%s",[i][j].info);
[j][i]=[i][j];///无向图,结构体赋值
}
return OK;
}
void DFS(MGraph G,int v)///邻接矩阵DFS
{
visited[v]=TRUE;
VisitFunc(G,v);
for(int w=0; w<; w++)
if([v][w].adj!=INFINITY&&!visited[w])DFS(G,w);
}
void DFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v))
{
VisitFunc=Visit;
printf("请输入深度优先搜索起始结点:\n");
string st;
while(cin>>st)
{
if(st=="END")break;
int tmp=LocateVex(G,st);
if(tmp==-1)
{
printf("输入的起点不存在，请重新输入\n");
continue;
}
for(int v=0; v<; v++)visited[v]=FALSE;
printf("深度优先搜索遍历序列:\n");
DFS(G,tmp);
for(int v=0; v<; v++)if(!visited[v])DFS(G,v);
printf("\n");
printf("*********输入新起点搜索起点重新遍历*********\n");
printf(" **********输入END结束深度优先搜索*********\n");
printf("请输入操作:");
}
printf("==============================================================\n");
printf("|| 1.深度优先搜索遍历 ||\n");
printf("|| 2.广度优先搜索遍历 ||\n");
printf("|| 3.最短路径计算(仅带权图) ||\n");
printf("|| 4.结束程序 ||\n");
printf("|| 5.重新建图 ||\n");
printf("==============================================================\n");
printf("请输入对图的操作:\n");
}
void BFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v))///邻接矩阵BFS
{
queue<int>Q;
printf("请输入广度优先搜索起始结点:\n");
string st;
while(cin>>st)
{
if(st=="END")break;
int temp=LocateVex(G,st);
if(temp==-1)
{
printf("输入的起点不存在，请重新输入\n");
continue;
}
for(int v=0; v<; v++)visited[v]=FALSE;
while(!())();
printf("广度优先搜索遍历序列:\n");
Visit(G,temp);
(temp);
visited[temp]=TRUE;
while(!())
{
int tmp=();
();
for(int w=0; w<; w++)
{
if(!visited[w]&&[tmp][w].adj!=INFINITY)
{
visited[w]=TRUE;
Visit(G,w);
(w);
}
}
}
for(int v=0; v<; v++)///剩余连通分量
{
if(!visited[v])
{
visited[v]=TRUE;
Visit(G,v);
(v);
while(!())
{
int tmp=();
();
for(int w=0; w<; w++)
{
if(!visited[w]&&[tmp][w].adj!=INFINITY)
{
visited[w]=TRUE;
Visit(G,w);
(w);
}
}
}
}
}
printf("\n");
printf("*********输入新起点搜索起点重新遍历*********\n");
printf("*********输入END结束广度优先搜索*********\n");
printf("请输入操作:");
}
printf("==============================================================\n");
printf("|| 1.深度优先搜索遍历 ||\n");
printf("|| 2.广度优先搜索遍历 ||\n");
printf("|| 3.最短路径计算(仅带权图) ||\n");
printf("|| 4.结束程序 ||\n");
printf("|| 5.重新建图 ||\n");
printf("==============================================================\n");
printf("请输入对图的操作:\n");
}
Status CreateGraph(MGraph &G)///邻接矩阵
{
printf("**********************************************\n");
printf("* *\n");
printf("* 1:无权有向图 *\n");
printf("* 2:带权有向网 *\n");
printf("* 3:无权无向图 *\n");
printf("* 4:带权无向网 *\n");
printf("* *\n");
printf("**********************************************\n");
printf("请输入建图类型:");
scanf("%d",&);///输入图的种类
system("cls");
switch(-1)
{
case DG:
return CreateDG(G);
case DN:
return CreateDN(G);
case UDG:
return CreateUDG(G);
case UDN:
return CreateUDN(G);
default:
return ERROR;
}
}
Status visit(MGraph G,int v)///邻接矩阵遍历
{
cout<<[v]<<' ';
}
///===========================================================================
typedef struct ArcNode///弧(邻接表)
{
int adjvex; ///当前弧指向的顶点
int info; ///权值
struct ArcNode *nextarc;///下一条当前顶点为出度的弧
} ArcNode;
typedef struct VNode///点(邻接表)
{
VertexType data;///结点名
ArcNode *firstarc;///该点的第一条出边
} VNode,AdjList[MAX_VERTEX_NUM];
typedef struct///图(邻接表)
{
AdjList vertices;///点的邻接表(数组)
int vexnum,arcnum;
int kind;
} ALGraph;
Status (*VisitFunc_2)(ALGraph G,int v);
void ArcAdd_sort(ALGraph &G,int v1,int v2,int w)///从大到小顺序建立邻接表
{
ArcNode *p,*h,*q;
p=new ArcNode;
p->adjvex=v2;
p->info=w;
p->nextarc=NULL;
h=q=[v1].firstarc;
if(q==NULL)[v2].firstarc=p;
else
{
if(p->adjvex > q->adjvex)///邻接表按结点序号从大到小排列
{
p->nextarc=q;
[v2].firstarc=p;
}
else
{
while([v2].firstarc!=NULL&&q->nextarc!=NULL&&p->adjvex < q->adjvex)
{
h=q;
q=q->nextarc;
}
if(q->nextarc==NULL&&p->adjvex < q->adjvex) q->nextarc=p;
else
{
p->nextarc=q;
h->nextarc=p;
}
}
}
}
void ArcAdd(ALGraph &G,int v1,int v2,int w)///加边
{
ArcNode *p,*q;
p=new ArcNode;
p->adjvex=v2;
p->info=w;
p->nextarc=NULL;
q=[v1].firstarc;
if(q==NULL) [v1].firstarc=p;///若第一条依附v2顶点的弧还未存在，新加入的边作为第一条依附弧
else///否则顺着链表向后查找
{
while(q->nextarc!=NULL) q=q->nextarc;
q->nextarc=p;
}
}
int LocateVex_2(ALGraph G,string name)///获取结点标号
{
for(int i=0; i<; i++)
if(name==[i].data)return i;
return -1;
}
Status CreateDG_2(ALGraph &G)///邻接表(建立无权有向图)
{
printf("建立无权有向图，请依次输入总结点数、总边数:\n");
scanf("%d%d",&,&);
printf("请为从1至n个结点命名:\n");
for(int i=0; i<; i++)cin>>[i].data,[i].firstarc=NULL;
string v1,v2;
printf("请输入%d组由左指向右的有向边:\n",);
for(int k=0; k<; k++)
{
cin>>v1>>v2;
int i=LocateVex_2(G,v1);///获取标号
int j=LocateVex_2(G,v2);
ArcAdd(G,i,j,1);
}
return OK;
}
Status CreateDN_2(ALGraph &G)///邻接表(建立带权有向网)
{
printf("建立带权有向网，请依次输入总结点数、总边数:\n");
scanf("%d%d",&,&);
printf("请为从1至n个结点命名:\n");
for(int i=0; i<; i++)cin>>[i].data,[i].firstarc=NULL;
string v1,v2;
int w;
printf("请输入%d组由左指向右的有向边与边权:\n",);
for(int k=0; k<; k++)
{
cin>>v1>>v2>>w;
int i=LocateVex_2(G,v1);///获取标号
int j=LocateVex_2(G,v2);
ArcAdd(G,i,j,w);
}
return OK;
}
Status CreateUDG_2(ALGraph &G)///邻接表(建立无权无向图)
{
printf("建立无权无向图，请依次输入总结点数、总边数:\n");
scanf("%d%d",&,&);
printf("请为从1至n个结点命名:\n");
for(int i=0; i<; i++)cin>>[i].data,[i].firstarc=NULL;
string v1,v2;
printf("请输入%d组相互依附的两结点:\n",);
for(int k=0; k<; k++)
{
cin>>v1>>v2;
int i=LocateVex_2(G,v1);///获取标号
int j=LocateVex_2(G,v2);
ArcAdd(G,i,j,1);///无向边
ArcAdd(G,j,i,1);
}
return OK;
}
Status CreateUDN_2(ALGraph &G)///邻接表(建立带权无向网)
{
printf("建立带权无向网，请依次输入总结点数、总边数:\n");
scanf("%d%d",&,&);
printf("请为从1至%d个结点命名:\n",);
for(int i=0; i<; i++)cin>>[i].data,[i].firstarc=NULL;
string v1,v2;
int w;
printf("请输入%d组相互依附的两结点与边权:\n",);
for(int k=0; k<; k++)
{
cin>>v1>>v2>>w;
int i=LocateVex_2(G,v1);///获取标号
int j=LocateVex_2(G,v2);
ArcAdd(G,i,j,w);///无向边
ArcAdd(G,j,i,w);
}
return OK;
}
int FirstAdjVex(ALGraph G,int v)
{
if([v].firstarc) return [v].firstarc->adjvex;
return -1;
}
int NextAdjVex(ALGraph G,int v,int w)
{
ArcNode *p=[v].firstarc;
while(p->adjvex!=w&&p->nextarc!=NULL)p=p->nextarc;
if(p->nextarc==NULL)return -1;
return p->nextarc->adjvex;
}
void DFS_2(ALGraph G,int v)///邻接表DFS
{
visited[v]=TRUE;
VisitFunc_2(G,v);
for(int w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
if(!visited[w])DFS_2(G,w);
}
void DFSTraverse_2(ALGraph G,Status (*Visit)(ALGraph G,int v))
{
VisitFunc_2=Visit;
printf("请输入深度优先搜索起始结点:\n");
for(int v=0; v<; v++)visited[v]=FALSE;
string st;
cin>>st;
int tmp=LocateVex_2(G,st);
printf("深度优先搜索遍历序列:\n");
DFS_2(G,tmp);
for(int v=0; v<; v++)if(!visited[v])DFS_2(G,v);
printf("\n");
}
void BFSTraverse_2(ALGraph G,Status (*Visit)(ALGraph G,int v))///邻接表BFS
{
for(int v=0; v<; v++)visited[v]=FALSE;
queue<int>Q;
printf("请输入广度优先搜索起始结点:\n");
string st;
cin>>st;
printf("广度优先搜索遍历序列:\n");
int temp=LocateVex_2(G,st);
Visit(G,temp);
(temp);
visited[temp]=TRUE;
while(!())
{
int tmp=();
();
for(int w=FirstAdjVex(G,tmp); w>=0; w=NextAdjVex(G,tmp,w))
{
if(!visited[w])
{
visited[w]=TRUE;
Visit(G,w);
(w);
}
}
}
for(int v=0; v<; v++)///剩余连通分量
{
if(!visited[v])
{
visited[v]=TRUE;
Visit(G,v);
(v);
while(!())
{
int tmp=();
();
for(int w=FirstAdjVex(G,tmp); w>=0; w=NextAdjVex(G,tmp,w))
{
if(!visited[w])
{
visited[w]=TRUE;
Visit(G,w);
(w);
}
}
}
}
}
printf("\n");
}
void PrintGraph(ALGraph G)///输出邻接表
{
cout<<"图的创建完成,该图的邻接表表示为:"<<endl;
ArcNode *p;
for(int i=0; i<; i++)
{
if([i].firstarc == NULL)
cout<<i<<":"<<[i].data<<"-->NULL"<<endl;
else
{
p = [i].firstarc;
cout<<i<<":"<<[i].data<<"-->";
while(p->nextarc!=NULL)
{
cout<<p->adjvex<<"-->";
p = p->nextarc;
}
cout<<p->adjvex<<"-->NULL"<<endl;
}
}
}
Status CreateGraph_2(ALGraph &G)///邻接表
{
printf("**********************************************\n");
printf("* *\n");
printf("* 1:无权有向图 *\n");
printf("* 2:带权有向网 *\n");
printf("* 3:无权无向图 *\n");
printf("* 4:带权无向网 *\n");
printf("* *\n");
printf("**********************************************\n");
printf("请输入建图类型:");
scanf("%d",&);///输入图的种类
system("cls");
switch(-1)
{
case DG:
return CreateDG_2(G);
case DN:
return CreateDN_2(G);
case UDG:
return CreateUDG_2(G);
case UDN:
return CreateUDN_2(G);
default:
return ERROR;
}
}
Status visit_2(ALGraph G,int v)///邻接表遍历
{
cout<<[v].data<<' ';
}
///===============================================================================
void dijkstra(MGraph G)
{
string tmp;
int pre[108];
int dist[MAX_VERTEX_NUM],s;///最短路数组
bool vis[MAX_VERTEX_NUM];
printf("请输入该图起点:");
while(cin>>tmp)///最短路源点
{
if(tmp=="END")break;
s=LocateVex(G,tmp);
if(s==-1)
{
printf("输入的起点不存在，请重新输入\n");
continue;
}
for(int i=0; i<; i++)pre[i]=s;///路径父亲初始化
memset(vis,false,sizeof(vis));
memset(dist,0x3f,sizeof(dist));
for(int i=0; i<; i++)///所有点到达起点的距离
dist[i]=[s][i].adj;
dist[s]=0;///标记起点长度为0
vis[s]=true;///标记走过
for(int i=1; i<; i++)///遍历n-1次
{
int minn=0x7fffffff,mini;
for(int j=0; j<; j++)///这里是要遍历所有的点，因为不一定是第0个点作为起点
{
if(!vis[j]&& dist[j] < minn)
{
minn=dist[j];
mini=j;
}
}
vis[mini]=true;
for(int j=0; j<; j++)
{
if(dist[j]>dist[mini]+[mini][j].adj)
{
dist[j]=dist[mini]+[mini][j].adj;
pre[j]=mini;
}
// dist[j]=dist[j]<(dist[mini]+[mini][j].adj)?dist[j]:(dist[mini]+[mini][j].adj);
// printf("**%d %d\n",dist[j],dist[mini]+[mini][j].adj);
}
}
cout<<"从源点"<<[s]<<"到达所有位置的最短路径:\n";
for(int i=0; i<; i++)
{
if(i!=s)
{
cout<<"到达"<<[i]<<"的最短路径距离:"<<dist[i]<<endl;
int step=0,road[108],tmp=i;
while(pre[tmp]!=tmp)
{
road[step++]=pre[tmp];
tmp=pre[tmp];
}
printf("最短路径为：");
for(int j=step-1; j>=0; j--) cout<<[road[j]]<<" ";
cout<<[i]<<endl;
}
}
printf("*********输入新起点搜索起点重新遍历*********\n");
printf("*********输入END结束最短路径计算*********\n");
printf("请输入操作:");
}
printf("==============================================================\n");
printf("|| 1.深度优先搜索遍历 ||\n");
printf("|| 2.广度优先搜索遍历 ||\n");
printf("|| 3.最短路径计算(仅带权图) ||\n");
printf("|| 4.结束程序 ||\n");
printf("|| 5.重新建图 ||\n");
printf("==============================================================\n");
printf("请输入对图的操作:\n");
}
int main()
{
while(true)
{
MGraph G1;
while(!CreateGraph(G1))///邻接矩阵
printf("输入错误\n");
// for(int i=0; i<; i++)
// for(int j=0; j<; j++)
// printf("%15d%c",[i][j].adj,j==-1?'\n':' ');
int con;
printf("==============================================================\n");
printf("|| 1.深度优先搜索遍历 ||\n");
printf("|| 2.广度优先搜索遍历 ||\n");
printf("|| 3.最短路径计算(仅带权图) ||\n");
printf("|| 4.结束程序 ||\n");
printf("|| 5.重新建图 ||\n");
printf("==============================================================\n");
printf("请输入对图的操作:\n");
while(scanf("%d",&con)!=EOF)
{
system("cls");
if(con==1)
DFSTraverse(G1,visit);///深搜邻接矩阵
else if(con==2)
BFSTraverse(G1,visit);///广搜邻接矩阵
else if(con==3&&(==2||==4))
dijkstra(G1);
else if(con==4)
return 0;
else if(con==5)
break;
else
printf("输入错误，可能输入错误的指令或对无权图求最短路\n");
}
printf("请重新建图！\n");
ALGraph G2;///邻接表
// CreateGraph_2(G2);
// PrintGraph(G2);///输出邻接表
// DFSTraverse_2(G2,visit_2);///邻接表深搜
// BFSTraverse_2(G2,visit_2);///邻接表广搜
}
}
/*
3
8 9
V1 V2 V3 V4 V5 V6 V7 V8
V1 V2
V2 V4
V4 V8
V8 V5
V2 V5
V1 V3
V3 V6
V3 V7
V6 V7
V1 V2 1
V1 V3 12
V2 V3 9
V2 V4 3
V3 V5 5
V4 V3 4
V4 V5 13
V4 V6 15
V5 V6 4
*/