数据结构课程设计图的实现.docx
《数据结构课程设计图的实现.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计图的实现.docx（25页珍藏版）》请在冰点文库上搜索。
数据结构课程设计图的实现
数据结构课程设计
图的基本操作与实现
#include
usingnamespacestd;
typedefcharVertexType;
#include"Graph.h"
#include"UDGraph.h"
#include"UNGraph.h"
#include"DGraph.h"
#include"DNGraph.h"
voidShowMainMenu（）
{
cout<<"\n";
cout<<" ***************图的基本操作及应用******************\n";
cout<<" * 1无向图的基本操作及应用 *\n";
cout<<" * 2无向网的基本操作及应用 *\n";
cout<<" * 3有向图的基本操作及应用 *\n";
cout<<" * 4有向网的基本操作及应用 *\n";
cout<<" * 5退出 *\n";
cout<<" ***************************************************\n";
}
voidUDG（）
{
MGraphMG;
ALGraphALG;
intn;
do
{
cout<<"\n";
cout<<" ***************无向图的基本操作及应用***************\n";
cout<<" * 1创建无向图的邻接矩阵 *\n";
cout<<" * 2创建无向图的邻接表 *\n";
cout<<" * 3无向图的深度优先遍历 *\n";
cout<<" * 4无向图的广度优先遍历 *\n";
cout<<" * 5退出 *\n";
cout<<" *************************************************\n";
cin>>n;
switch（n）{
case1:
CreatUDG_M（MG）;
break;
case2:
CreatUDG_ALG（ALG）;
dispgraph（ALG）;
break;
case3:
CreatUDG_ALG（ALG）;
dfstraverse（ALG）;
break;
case4:
CreatUDG_M（MG）;
BFSTraver（MG）;
break;
default:
if（n!
=5）
cout<<"错误，重新输入\n";
}
}while（n!
=5）;
}
voidUDN（）
{
MGraphMG;
ALGraphALG;
intn;
do{
cout<<"\n";
cout<<" ***************无向网的基本操作及应用***************\n";
cout<<" * 1创建无向网的邻接矩阵 *\n";
cout<<" * 2创建无向网的邻接表 *\n";
cout<<" * 3prim算法求最小生成树 *\n";
cout<<" * 4kraskal算法求最小生成树 *\n";
cout<<" * 5退出 *\n";
cout<<" ****************************************************\n";
cin>>n;
switch（n）{
case1:
CreateUDN_M（MG）;
break;
case2:
CreateUDN（ALG）;
dispUDN（&ALG）;
break;
case3:
CreateUDN_M（MG）;
prim（MG）;
break;
case4:
CreateUDN_M（MG）;
Kruskal（MG）;
break;
default:
if（n!
=5）
cout<<"错误，重新输入\n";
}
}while（n!
=5）;
}
voidDG（）
{
MGraphMG;
ALGraphALG;
intn;
do
{
cout<<"\n";
cout<<" ***************有向图的基本操作及应用***************\n";
cout<<" * 1创建有向图的邻接矩阵 *\n";
cout<<" * 2创建有向图的邻接表 *\n";
cout<<" * 3拓扑排序 *\n";
cout<<" * 4退出 *\n";
cout<<" ****************************************************\n";
cin>>n;
switch（n）{
case1:
CreatDG_M（MG）;
break;
case2:
CreatDG_ALG（ALG）;
dispgraph（ALG）;
break;
case3:
CreatDG_ALG（ALG）;
TopologicalSort（ALG）;
break;
default:
if（n!
=4）
cout<<"错误，重新输入\n";
}
}while（n!
=4）;
}
voidDN（）
{
MGraphMG;
ALGraphALG;
intn;
PathMatrixp1;
ShortPathTabled1;
dist2d;
path2p;
do{
cout<<"\n";
cout<<" ***************有向网的基本操作及应用***************\n";
cout<<" * 1创建有向网的邻接矩阵 *\n";
cout<<" * 2创建有向网的邻接表 *\n";
cout<<" * 3关键路径 *\n";
cout<<" * 4单源顶点最短路径问题 *\n";
cout<<" * 5每对顶点最短路径问题 *\n";
cout<<" * 6退出 *\n";
cout<<" ****************************************************\n";
cin>>n;
switch（n）{
case1:
CreateDNG_M（MG）;
break;
case2:
CreateDN（ALG）;
dispDN（&ALG）;
break;
case3:
CreateDN（ALG）;
CriticalPath（ALG）;
break;
case4:
CreateDNG_M（MG）;
ShortestPath（MG,1,p1,d1）;
break;
case5:
CreateDNG_M（MG）;
Floyd（MG,p,d）;
break;
default:
if（n!
=6）
cout<<"错误，重新输入\n";
}
}while（n!
=6）;
}
voidmain（）
{
intn;
do{
ShowMainMenu（）;
cin>>n;
switch（n）{
case1:
UDG（）;
break;
case2:
UDN（）;
break;
case3:
DG（）;
break;
case4:
DN（）;
break;
default:
if（n!
=5）
cout<<"错误，重新输入\n";
}
}while（n!
=5）;
}
//Graph.h（图的定义）
#defineMAXVEX30
#defineMAXCOST1000
typedefintInfoType;
typedefstruct{
VertexTypevexs[MAXVEX];
intarcs[MAXVEX][MAXVEX];
intvexnum,arcnum;
}MGraph;
typedefstructarcnode{
intadjvex;//邻接点序号
intw;//边或狐上的权
InfoType*info;
structarcnode*next;
}ArcNode;
typedefstructvnode{
VertexTypedata; //顶点信息
intindegree;
ArcNode*firstarc; //指向下一个边结点
}Vnode,AdjList[MAXVEX];
typedefstruct{
AdjListvertices;
intvexnum,arcnum;
}ALGraph;
//UDGraph.h（无向图的基本操作及应用）
voidCreatUDG_M（MGraph&G）
{
inti,j,c;
cout<<"请输入顶点数,边数:
";
cin>>G.vexnum;
cin>>G.arcnum;
cout<<"请输入结点信息，如“123..."< for（i=1;i<=G.vexnum;i++）
{
cin>>G.vexs[i];
}
for（i=1;i<=G.vexnum;i++）
for（j=1;j<=G.vexnum;j++）
G.arcs[i][j]=0;
for（c=1;c<=G.arcnum;c++）
{printf（"第%d条边=>起点序号,终点序号:
",c）;
cin>>i>>j;
G.arcs[i][j]=1;
G.arcs[j][i]=1;
}
cout<<"创建的邻接矩阵为：
"< for（inti=1;i<=G.vexnum;i++）
{for（intj=1;j<=G.vexnum;j++）
cout< cout< }
cout<<"邻接矩阵创建完毕"<}
/////////////////////////////////////////////////////////////////////////
voidCreatUDG_ALG（ALGraph&G）
{
inti,s,d;
ArcNode*p,*q;
cout<<"请输入顶点数,边数：
";
cin>>G.vexnum;
cin>>G.arcnum;
cout<<"请输入结点信息，如“123..."< for（i=1;i<=G.vexnum;i++）
{
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL;
}
for（i=1;i<=G.arcnum;i++）
{
printf（"第%d条边=>起点序号,终点序号:
",i）;
cin>>s>>d;
p=（ArcNode*）malloc（sizeof（ArcNode））;
q=（ArcNode*）malloc（sizeof（ArcNode））;
p->adjvex=d;
q->adjvex=s;
p->next=G.vertices[s].firstarc; //p插入顶点s的邻接表中
G.vertices[s].firstarc=p;
q->next=G.vertices[d].firstarc; //q插入顶点d的邻接表中
G.vertices[d].firstarc=q;
}
}
voiddispgraph（ALGraphG）
{
inti;
ArcNode*p;
printf（"图的邻接表表示如下:
\n"）;
for（i=1;i<=G.vexnum;i++）
{
printf（" [%d,%c]=>",i,G.vertices[i].data）;
p=G.vertices[i].firstarc;
while（p!
=NULL）
{
printf（"[%d→]",p->adjvex）;
p=p->next;
}
printf（"∧\n"）;
}
}
////////////////////////////////////////////////////////////////////////
intvisit[20];
voiddfs（ALGraphG,intv）//从顶点v出发深度优先搜索
{visit[v]=1;
cout<ArcNode*p;
p=G.vertices[v].firstarc;
while（p）{
if（visit[p->adjvex]!
=1）
dfs（G,p->adjvex）;
p=p->next;
}//while
}
voiddfstraverse（ALGraphG）//对一个图进行深度优先搜索
{ intv;
for（v=1;v<=G.vexnum;v++）
if（!
visit[v]）
dfs（G,1）;
}
///////////////////////////////////////////////////////////////////////
#include"CirQueue.h"
intFirstAdjVex（MGraphG,intvex）
{
intw,i;
for（i=1;i<=G.vexnum;i++）
{
if（G.arcs[vex][i]==1&&visit[i]==0）
{w=i;break;
}
elsew=0;
}
returnw;
}
//获取下一个未被访问的邻接节点
intNextAdjVex（MGraphG,intvex,intw）
{
inti;
for（i=w;i<=G.vexnum;i++）//从w开始
{
if（G.arcs[vex][i]==1&&visit[i]==0）
{w=i;
break;
}
elsew=0;
}
returnw;
}
voidBFSTraver（MGraphG）
{
Queueq;
InitQueue（&q）;
inti,w,u;
for（i=1;i<=G.vexnum;i++）
visit[i]=0;
for（i=1;i<=G.vexnum;i++）//确保所有的节点被访问到的一个循环
{
if（visit[i]==0）
{
visit[i]=1;
cout<EnQueue（&q,i）;
while（!
QueueEmpty（&q））//当队列非空时一直做
{
DeQueue（&q,u）;//取出队列头元素并置为u
w=FirstAdjVex（G,u）;
while（w>0）
{
if（visit[w]==0）
{
visit[w]=1;
cout<EnQueue（&q,w）;
w=NextAdjVex（G,u,w）;
}
}
}
}
}
}
//UNGraph.h（无向网的基本操作及应用）
voidCreateUDN_M（MGraph&G）
{inti,j,k,n;
cout<<"请输入顶点数和边数"<cin>>G.vexnum;
cin>>G.arcnum;
cout<<"输入顶点"<for（i=1;i<=G.vexnum;i++）
cin>>G.vexs[i];
for（i=1;i<=G.vexnum;i++）
for（j=1;j<=G.vexnum;j++）
G.arcs[i][j]=999;
cout<<"输入边的起点到终点的序号及权值"<for（k=1;k<=G.arcnum;k++）
{
cin>>i>>j>>n;
G.arcs[i][j]=n;
G.arcs[j][i]=G.arcs[i][j];
}
cout<<"创建的邻接矩阵为：
"< for（inti=1;i<=G.vexnum;i++）
{for（intj=1;j<=G.vexnum;j++）
cout< cout< }
cout<<"邻接矩阵创建完毕"<}
//建立无向网的邻接矩阵存储结构
///////////////////////////////////////////////////////
voidCreateUDN（ALGraph&G） //邻接表建立无向网
{
int i,s,d,w1;
ArcNode*p,*q;
cout<<"输入节点数和边数"< cin>>G.vexnum>>G.arcnum;
cout<<"输入顶点，如“123...”"< for（i=1;i<=G.vexnum;i++） //输入顶点
{
cin>>G.vertices[i].data; //输入顶点
G.vertices[i].firstarc=NULL; //首先初始化为NULL
}
cout<<"输入边的起点到终点的序号及权值"< for（i=1;i<=G.arcnum;i++）
{
cin>>s>>d>>w1; //输入一条边依附的起点序号和终点序号
p=（ArcNode*）malloc（sizeof（ArcNode））;
q=（ArcNode*）malloc（sizeof（ArcNode））;
p->info=（InfoType*）malloc（sizeof（InfoType））;
q->info=（InfoType*）malloc（sizeof（InfoType））;
p->adjvex=d; //保存该弧所指向的顶点位置
q->adjvex=s; //保存该弧所指向的顶点位置
*（p->info）=w1; //保存权值到一个结点里
*（q->info）=w1; //保存权值到一个结点里
p->next=G.vertices[s].firstarc;
G.vertices[s].firstarc=p;
q->next=G.vertices[d].firstarc;
G.vertices[d].firstarc=q;
}
}
voiddispUDN（ALGraph*G） /*打印无向网每个结点的单链表*/
{
inti,j;
cout<<"[起点权值终点]"< for（i=1;i<=G->vexnum;i++）
{
while（G->vertices[i].firstarc->next）
{
cout<<"["<vertices[i].data<<"";
j=G->vertices[i].firstarc->adjvex;
cout<<*（G->vertices[i].firstarc->info）<<""<vertices[j].data<<"]";
G->vertices[i].firstarc=G->vertices[i].firstarc->next;
}
cout<<"["<vertices[i].data<<"";
j=G->vertic
升级会员 