实验7图.docx

实验7图.docx

《实验7图.docx》由会员分享，可在线阅读，更多相关《实验7图.docx（14页珍藏版）》请在冰点文库上搜索。

实验7图

实验七：

图的应用

一、实验预备知识

1复习C中的全局变量的概念。

2复习图的邻接矩阵和邻接表两种存储方式。

3复习图的两种遍历方法和求图的最小生成树的方法。

二、实验目的

1掌握图的邻接矩阵和邻接表两种存储方法。

2掌握有关图的操作算法并用高级语言实现。

3熟悉图的构造算法，了解实际问题的求解效率与采用何种存储结构与算法有着密切联系。

4掌握图的两种搜索路径的遍历算法。

5掌握求图的最小生成树的普里姆算法和克鲁斯卡尔算法。

三、实验内容

1．创建给定的图，用邻接表或邻接矩阵进行存储。

2．对所创建的图进行深度和广度优先搜索遍历，给出遍历过程中的顶点序列。

3．求图的最小生成树，按构造顺序输出边的序列。

3．编写一个主函数，将上面函数连在一起，构成一个完整程序。

4．将实验源程序调试并运行。

四、实验要求

创建图，如图G1所示。

图1G1

●用邻接表存储结构时，可以自定义链表中结点的顺序，如单链表以结点的从小到大排列。

按自定义的结点顺序将图1的存储邻接表画出。

●注意标志数组visited[n+1]的定义和赋值。

●将顶点1作为起点。

五、存储结构图

图2G1存储结构图

六、程序代码

#include

#include

usingnamespacestd;

#defineint_max10000

#defineinf9999

#definemax20

//邻接矩阵定义

typedefstructArcCell

{intadj;char*info;}ArcCell,AdjMatrix[20][20];

typedefstruct

{charvexs[20];AdjMatrixarcs;

intvexnum,arcnum;}MGraph_L;

intlocalvex（MGraph_LG,charv）//返回V的位置

{

inti=0;

while（G.vexs[i]!

=v）{++i;}returni;

}

intcreatMGraph_L（MGraph_L&G）//创建图用邻接矩阵表示

{

charv1,v2;inti,j,w;

cout<<"…………创建无向图…………"<

（46）不包括“（）”"<

cin>>G.vexnum>>G.arcnum;

for（i=0;i!

=G.vexnum;++i）

{cout<<"输入顶点"<>G.vexs[i];}

for（i=0;i!

=G.vexnum;++i）

for（j=0;j!

=G.vexnum;++j）

{G.arcs[i][j].adj=int_max;G.arcs[i][j].info=NULL;}

for（intk=0;k!

=G.arcnum;++k）

{

cout<<"输入一条边依附的顶点和权:

（ab3）不包括“（）”"<

cin>>v1>>v2>>w;i=localvex（G,v1）;j=localvex（G,v2）;

G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;

}

cout<<"图G邻接矩阵创建成功！

"<

}

voidljjzprint（MGraph_LG）

{inti,j;

for（i=0;i!

=G.vexnum;++i）

{

for（j=0;j!

=G.vexnum;++j）cout<

cout<

}

}

intvisited[max];intwe;

typedefstructarcnode//弧结点

{

intadjvex;structarcnode*nextarc;char*info;

}arcnode;

typedefstructvnode//邻接链表顶点头接点

{chardata;arcnode*firstarc;}vnode,adjlist;

typedefstruct//图的定义

{

adjlistvertices[max];intvexnum,arcnum;intkind;

}algraph;

//队列定义

typedefstructqnode

{intdata;structqnode*next;}qnode,*queueptr;

typedefstruct

{queueptrfront;queueptrrear;}linkqueue;

typedefstructacr

{intpre,bak,weight;}edg;

intcreatadj（algraph&gra,MGraph_LG）//用邻接表存储图

{inti=0,j=0;arcnode*arc,*tem,*p;

for（i=0;i!

=G.vexnum;++i）

{

gra.vertices[i].data=G.vexs[i];gra.vertices[i].firstarc=NULL;

}

for（i=0;i!

=G.vexnum;++i）

{

for（j=0;j!

=G.vexnum;++j）

{

if（gra.vertices[i].firstarc==NULL）

{

if（G.arcs[i][j].adj!

=int_max&&j!

=G.vexnum）

{

arc=（arcnode*）malloc（sizeof（arcnode））;arc->adjvex=j;

gra.vertices[i].firstarc=arc;arc->nextarc=NULL;p=arc;++j;

while（G.arcs[i][j].adj!

=int_max&&j!

=G.vexnum）

{

tem=（arcnode*）malloc（sizeof（arcnode））;tem->adjvex=j;

gra.vertices[i].firstarc=tem;tem->nextarc=arc;arc=tem;++j;

}--j;

}

}

else

{

if（G.arcs[i][j].adj!

=int_max&&j!

=G.vexnum）

{

arc=（arcnode*）malloc（sizeof（arcnode））;arc->adjvex=j;

p->nextarc=arc;arc->nextarc=NULL;p=arc;

}

}

}

}

gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;

cout<<"图G邻接表创建成功！

"<

}

voidadjprint（algraphgra）

{inti;

for（i=0;i!

=gra.vexnum;++i）

{

arcnode*p;cout<

while（p!

=NULL）

{cout<adjvex;p=p->nextarc;

}cout<

}

}

intfirstadjvex（algraphgra,vnodev）//返回依附顶点V的第一个点

{if（v.firstarc!

=NULL）returnv.firstarc->adjvex;}

intnextadjvex（algraphgra,vnodev,intw）//返回依附顶点V的相对于W的下一个顶点

{

arcnode*p;p=v.firstarc;

while（p!

=NULL&&p->adjvex!

=w）

{p=p->nextarc;}

if（p->adjvex==w&&p->nextarc!

=NULL）

{p=p->nextarc;returnp->adjvex;}

if（p->adjvex==w&&p->nextarc==NULL）return-10;

}

intinitqueue（linkqueue&q）//初始化队列

{

q.rear=（queueptr）malloc（sizeof（qnode））;q.front=q.rear;

if（!

q.front）return0;q.front->next=NULL;return1;

}

intenqueue（linkqueue&q,inte）//入队

{

queueptrp;p=（queueptr）malloc（sizeof（qnode））;

if（!

p）return0;

p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;return1;

}

intdequeue（linkqueue&q,int&e）//出队

{

queueptrp;if（q.front==q.rear）return0;

p=q.front->next;e=p->data;q.front->next=p->next;

if（q.rear==p）q.rear=q.front;free（p）;return1;

}

intqueueempty（linkqueueq）//判断队为空

{if（q.front==q.rear）return1;return0;}

voidbfstra（algraphgra）//广度优先遍历

{inti,e;linkqueueq;

for（i=0;i!

=gra.vexnum;++i）visited[i]=0;initqueue（q）;

for（i=0;i!

=gra.vexnum;++i）

if（!

visited[i]）

{visited[i]=1;cout<

while（!

queueempty（q））

{dequeue（q,e）;

for（we=firstadjvex（gra,gra.vertices[e]）;we>=0;we=nextadjvex（gra,gra.vertices[e],we））

{

if（!

visited[we]）{visited[we]=1;cout<

}

}

}

}

intdfs（algraphgra,inti）;//声明DFS

intdfstra（algraphgra）

{

inti,j;for（i=0;i!

=gra.vexnum;++i）{visited[i]=0;}

for（j=0;j!

=gra.vexnum;++j）

{

if（visited[j]==0）dfs（gra,j）;

}return0;

}

intdfs（algraphgra,inti）

{

visited[i]=1;intwe1;cout<

for（we=firstadjvex（gra,gra.vertices[i]）;we>=0;we=nextadjvex（gra,gra.vertices[i],we））

{we1=we;

if（visited[we]==0）dfs（gra,we）;

we=we1;}return12;

}

typedefstruct

{intadjvex,lowcost;}closedge;

intprim（intg[][max],intn）//最小生成树PRIM算法

{

intlowcost[max],prevex[max];inti,j,k,min;

for（i=2;i<=n;i++）{lowcost[i]=g[1][i];prevex[i]=1;}

lowcost[1]=0;//标志顶点1加入U集合

for（i=2;i<=n;i++）//形成n-1条边的生成树

{

min=inf;k=0;

for（j=2;j<=n;j++）

if（（lowcost[j]

=0））{min=lowcost[j];k=j;}

printf（"（%d,%d）%d\t",prevex[k]-1,k-1,min）;lowcost[k]=0;

for（j=2;j<=n;j++）//修改由顶点k到其他顶点边的权值

if（g[k][j]

printf（"\n"）;

}return0;

}intacrvisited[100];//kruscal弧标记数组

intfind（intacrvisited[],intf）

{

while（acrvisited[f]>0）f=acrvisited[f];

returnf;

}

voidkruscal_arc（MGraph_LG,algraphgra）

{

edgedgs[20];inti,j,k=0;

for（i=0;i!

=G.vexnum;++i）

for（j=i;j!

=G.vexnum;++j）

{

if（G.arcs[i][j].adj!

=10000）

{

edgs[k].pre=i;edgs[k].bak=j;edgs[k].weight=G.arcs[i][j].adj;

++k;

}

}

intx,y,m,n;intbuf,edf;

for（i=0;i!

=gra.arcnum;++i）acrvisited[i]=0;

for（j=0;j!

=G.arcnum;++j）

{m=10000;

for（i=0;i!

=G.arcnum;++i）

{

if（edgs[i].weight

{

m=edgs[i].weight;x=edgs[i].pre;y=edgs[i].bak;n=i;

}

}

buf=find（acrvisited,x）;edf=find（acrvisited,y）;edgs[n].weight=10000;

if（buf!

=edf）{acrvisited[buf]=edf;cout<<"（"<

}

}

voidmain（）

{

algraphgra;MGraph_LG;inti,d,g[20][20];chara='a';

d=creatMGraph_L（G）;creatadj（gra,G）;vnodev;

cout<

若该图为非强连通图（含有多个连通分量）时"<

<<"最小生成树不存在,则显示为非法值。

"<

cout<<"…………………菜单……………………"<

cout<<"0、显示该图的邻接矩阵……………………"<

cout<<"1、显示该图的邻接表……………………"<

cout<<"2、深度优先遍历…………………………"<

cout<<"3、广度优先遍历…………………………"<

cout<<"4、最小生成树PRIM算法…………………"<

cout<<"5、最小生成树KRUSCAL算法………………"<

ints;chary='y';

while（y='y'）

{

cout<<"请选择菜单：

"<>s;

switch（s）

{case0:

cout<<"邻接矩阵显示如下：

"<

case1:

cout<<"邻接表显示如下：

"<

case2:

cout<<"广度优先遍历：

";bfstra（gra）;cout<

case3:

for（i=0;i!

=gra.vexnum;++i）visited[i]=0;

cout<<"深度优先遍历：

";dfstra（gra）;cout<

case4:

for（i=0;i!

=G.vexnum;++i）

for（intj=0;j!

=G.vexnum;++j）g[i+1][j+1]=G.arcs[i][j].adj;

cout<<"prim:

"<

case5:

cout<<"kruscal:

"<

}

cout<

y/n:

";cin>>y;

if（y=='n'）break;

}

}

七、运行结果

八、实验总结