数据结构课程设计之图的遍历和生成树求解

##大学

数据结构课程设计报告

题目：图的遍历和生成树求解

院（系）：计算机工程学院

学生姓名:_____________________

班级：学号:

起迄日期：2011

指导教师：______________________

指导教师评语：成绩:

签名:

年月日

2010—2011年度第2学期

一、需求分析

1.问题描述：

图的遍历和生成树求解实现

图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅

有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，

数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多

个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；

而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都

可能相关。

生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图

才有生成树。

2.基本功能

1）先任意创建一个图；

2）图的DFS,BFS的递归和非递归算法的实现

3)最小生成树(两个算法)的实现，求连通分量的实现

4)要求用邻接矩阵、邻接表等多种结构存储实现

3.输入输出

输入数据类型为整型和字符型，输出为整型和字符

二、概要设计

1.设计思路：

a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中

元素全是无穷大(intjnax),再将边的信息存到数组中。其中无权图的边用1

表示，无边用0表示；有全图的边为权值表示，无边用8表示。

b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的

每一行都转成链表的形式将有边的结点进行存储。

c.图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次

访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，

并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直

至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，

则另选未被访问的重复以上步骤，是一个非递归过程。

d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点,

然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，

这是个递归的过程。

e.图的连通分量:这是对一个非强连通图的遍历，从多个结点出发进行搜索,

而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连

通分量的顶点集。本程序利用的图的深度优先遍历算法。

2.数据结构设计：

ADTQueue{

数据对象:D={aJa(GElemSet,i=l,2,3...,n,n20}

数据关系：Rl={<ai-bai>|alba.ED,i=l,2,3,....,n}

基本操作：

InitQueue(&Q)

操作结果：构造一个空队列Q。

QueueEmpty(Q)

初始条件：Q为非空队列。

操作结果：若Q为空队列，则返回真，否则为假。

EnQueue(&Q,e)

初始条件：Q为非空队列。

操作结果：插入元素e为Q的新的队尾元素。

DeQueue(&Q,e)

初始条件：Q为非空队列。

操作结果：删除Q的队头元素，并用e返回其值。

}ADTQueue

ADTGraph{

数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：

R={VR}

VR={〈v,W＞IV,wev且P(v,w),〈V,W〉表示从V到w的弧，

谓词P(v.w)定义了弧＜v,w＞的意义或信息}

基本操作P:

CreatGraph(&G,V,VR);

初始条件：V是图的顶点集，VR是图中弧的集合。

操作结果：按V和VR的定义构造图G。

BFSTraverse(G,visit());

初始条件：图G存在，Visit是定点的应用函数。

操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点

调用函数Visit一次且仅一次。一旦visit()失

败，则操作失败。

DFSTraverse(G,visit());

初始条件：图G存在，Visit是定点的应用函数。

操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点

调用函数Visit一次且仅一次。一旦visit()失

败，则操作失败。

DFStra_fen(G)

初始条件：图G存在，存在图的深度优先遍历算法。

操作结果：从多个顶点对图进行深度优先遍历，得到连通分量。

}ADTGraph;

3.软件结构设计:

creatMGraph_L(G)int

creatadj(gra,G)int

Ijjzprint(G)void

adjprint(gra,G)void

BFSTraverse(gra)void

DFStra(gra)int

DFSTraverse_fen(gra)int

MiniSpanTree_PRIM(g,G.vexnum)int

MiniSpanTREE_KRUSCAL(G,gra)void

三、详细设计

1.定义程序中所有用到的数据及其数据结构，及其基本操作的实现；

邻接矩阵定义：

typedefstructArcCell

(

VRTypeadj;〃VRType是顶点关系类型。对无权图，用1或0表示相邻否;

对带权图，则为权值类型

InfoType*info;〃该弧相关信息的指针

}ArcCell,AdjMatrix[max][max];

typedefstruct

(

VertexTypevexs[max];〃顶点向量

AdjMatrixarcs;〃邻接矩阵

intvexnum,arcnum;〃图的当前顶点数和弧数

}MGraph_L;

邻接表的定义：

typedefstructArcNode〃弧结点

{

intadjvex;〃该弧指向的顶点的位置

structArcNode*nextarc;〃指向下一条弧的指针

InfoType*info;〃该弧相关信息的指针

}ArcNode;

typedefstructVNode〃邻接链表顶点头接点

(

VertexTypedata;〃顶点信息

ArcNode*firstarc;〃指向第一条依附该顶点的弧的指针

}VNode,AdjList;

typedefstruct〃图的定义

AdjListvertices[max];

intvexnum,arcnum;〃图的当前顶点数和弧数

}ALGraph;

队列定义：

typedefstructQNode

(

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;

typedefstruct

(

QueuePtrfront;〃队头指针

QueuePtrrear;〃队尾指针

}LinkQueue;

2.主函数和其他函数的伪码算法；

主函数：

intmain()

ints;

chary=，y，;

cout<<〃|innQQQQnQQnQQQQnQQ菜单QQQQQQnQQ

QQQQQQaaal|z，«endl;

cout<<z，||------------------------【0、创建一个无向图

-----------------------------||〃<<endl;

cout<m------------------------11、显示该图的邻接矩阵

,,

-------------------------1|«endi；

cout<r||-------------------------【2、显示该图的邻接表

---------------------------1]〃<<endl;

cout«，zH------------------------13、广度优先遍历

-------------------------------1|〃<<endl;

cout«"||-------------------------【4、深度优先遍历

-------------------------------||〃<<endl;

cout<</z||------------------------[5、最小生成树MiniSpanTree_PRIM

算法------------1|z，«endl;

cout«/，||------------------------【6、最小生成树

MiniSpanTree_KRUSCAL算法---------1|"Gendl;

cou^CH------------------------17、连通分量

-----------------------------------||“<<endl;

COUKCIlanaQaaaaanoaaaananaQaaaaQaaa

□□□□□□naali〃«endi；

while(y==，y')

(

cout<<”请选择菜单："<<endl;

cin»s;

if(s==0)

(

++o;

if(o==2)

(

n=0;

1=0;

o=0;

1

}

switch(s)

(

case0:cout<X〃创建一个无向图：〃<Xendl;

MGraph_LG;

creatMGraph_L(G);

ALGraphgra;

creatadj(gra,G);

break;

case1:cout<〈〃邻接矩阵显示如下：〃《endl;

1jjzprint(G);

break;

case2:

cout<〈〃邻接表显示如下：〃<<endl;

adjprint(gra,G);

break;

case3:

cout«〃广度优先遍历：〃；

BFSTraverse(gra);

cout<<endl;

break;

case4:

cout<<〃深度优先遍历：〃；

DFStra(gra);

cout<<endl;

break;

case5:

if(n=0){cout<〈〃无权图没有最小生成树〃;break;}

elseif(l〉O){cout<〈〃若该图为非强连通图(含有多个连通分量)时,

最小生成树不存在〃<<endl;break;}

else

(

inti,g[max][max];

for(i=0;i!=G.vexnum;++i)

for(intj=0;j!=G.vexnum;++j)

g[i+l]Lj+1]=G.arcsEi][j].adj;

cout<<〃普利姆算法:，，<<endl;

MiniSpanTree_PRIM(g,G.vexnum);

break;

)

case6:if(n=0){cout<〈〃无权图没有最小生成树〃；break;}

elseif(l>0){cout«〃该图为非强连通图(含有多个连通分量)，最

小生成树不存在〃<<endl;break;}

else

(

cout<<〃克鲁斯卡尔算法：〃〈Vendl;

MiniSpanTREE_KRUSCAL(G,gra);

break;

)

case7:cout<<〃连通分量：〃<<endl;

DFSTraverse_fen(gra);

break;

cout«endl<<〃是否继续?y/n:〃；

cin»y;

if(y==，n)

break;

}

return0;

)

邻接矩阵存储：

intcreatMGraph_L(MGraph_L&G)〃创建图用邻接矩阵表示

(

charvl,v2;

inti,j,w;

cout。〃请输入顶点和弧的个数〃<<endl;

cin>>G.vexnum»G.arcnum;

cout<X〃输入各个顶点〃<Xendl;

for(i=0;i<G.vexnum;++i)

(

cin>>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<〈〃输入一条边依附的顶点和权〃〈〈endl;

cin>>vl>>v2>>w;〃输入一条边依附的两点及权值

i=localvex(G,vl);〃确定顶点VI和V2在图中的位置

j=localvex(G,v2);

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

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

)

for(i=0;i!=G.vexnum;++i)

for(j=0;j!=G.vexnum;++j)

if(G.arcs[i][j].adj!=1&&G.arcs[i][j].adj<int_max)n+=l;

)

if(n>=l)cout<〈〃这是一个有权图〃<<endl;

elsecout<<〃这是一个无权图〃<Xendl;

cout*〃图G邻接矩阵创建成功！〃<<endl;

returnG.vexnum;

)

邻接矩阵的输出：

void1jjzprint(MGraph_LG)〃邻接矩阵的输出

(

inti,j;

if(n==0)

(

for(i=0;i!=G.vexnum;++i)

(

for(j=0;j!=G.vexnum;++j)

(

if(G.arcs[i][j].adj==int_max){cout<<〃0〃<<〃〃;}

else{cout<<G.arcs[i][j].adj<<z，〃;}

}

cout<<endl;

)

}

else

(

for(i=0;i!=G.vexnum;++i)

(

for(j=0;j!=G.vexnum;++j)

(

if(G.arcs[i][j].adj==int_max){cout<<〃8〃<<〃〃；}

else{cout<<G.arcs[i][j].adj<<〃〃;}

)

cout«endl;

用邻接表存储图：

intcreatadj(ALGraph&gra,MGraphLG)〃用邻接表存储图

(

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].firstare=NULL;

)

for(i=0;i!=G.vexnum;++i)

for(j=0;j!=G.vexnum;++j)

(

if(G.arcs[i][j].adj!=int_max)

(

arc=(ArcNode*)malloc(sizeof(ArcNode));

arc->adjvex=j;

arc->nextarc=gra.vertices[i]・firstarc;

gra.vertices[i].firstarc=arc;

)

}

gra.vexnum=G.vexnum;

gra.arcnum=G.arcnum;

cout«〃图G邻接表创建成功！〃<<endl;

return1;

)

邻接表输出：

voidadjprint(ALGraphgra,MGraph_LG)//邻接表输出

(

inti;

for(i=0;i!=gra.vexnum;++i)

(

ArcNode*p;

cout«，，r«i«，，/，«G.vexs[i]«，，]，z;

p=gra.vertices[i]・firstarc;

while(p!=NULL)

cout«〃->〃<<〃[〃<<p->adjvex<<〃]〃;

p=p->nextarc;

}

cout«//->，，«，，End，z;

cout<<endl;

)

)

初始化队列：

StatusInitQueue(LinkQueue&Q)〃初始化队列

(

Q・front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)return0;〃存储分配失败

Q.front->next=NULL;

return1;

)

入队：

StatusEnQueue(LinkQueue&Q,QElemTypee)〃入队，插入元素e为Q的新的队

尾元素

(

QueuePtrp;

p=(QueuePtr)malloc(sizeof(QNode));

if(!p)return0;〃存储分配失败

p->data=e;p->next=NULL;

Q.rear->next=p;Q.rear=p;

return1;

)

出队：

StatusDeQueue(LinkQueue&Q,QElemType&e)〃出队，若队列不空，则删除Q

的队头元素，用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;

)

判断队为空：

StatusQueueEmpty(LinkQueueQ)〃判断队为空

(

if(Q.front==Q.rear)return1;

return0;

)

广度优先遍历：

voidBFSTraverse(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]=l;

cout<<gra.vertices[i]・data;

EnQueue(q,i);

while(!QueueEmpty(q))

(

DeQueue(q,e);

for(we=firstadjvex(gra,gra.vertices®);we>=0;we=nextadjvex(gra,g

ra.vertices[e],we))

(

if(!visited[we])

(

visited[we]=l;

cout<<gra.vertices[we],data;

EnQueue(q,we);

)

深度优先遍历：

intDFS(ALGraphgra,inti)

(

visited[i]=l;

intwel;

cout<<gra.vertices[i]・data;

for(we=firstadjvex(gra,gra.vertices"]);we>=0;we=nextadjvex(gra,g

ra.vertices[i],we))

(

wel=we;

if(visited[we]-O)

DFS(gra,we);

we=wel;

)

return1;

)

intDFStra(ALGraphgra)

(

inti,j;

for(i=0;i!=gra.vexnum;++i)

(

visited[i]=O;

}

for(j=0;j!=gra.vexnum;++j)

(

if(visited[j]==0)DFS(gra,j);

)

return0;

)

连通分量：

intDFSTraverse_fen(ALGraphgra)

inti,j;

for(i=0;i!=gra.vexnum;++i)

visited[i]=O;

for(j=0;j!=gra.vexnum;++j)

(

if(visited[j]==O)

(

DFS(gra,j);

cout«endl;

1++；

}

)

return0;

)

3.主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图

的形式表示。

图的邻接矩阵存储图的邻接表存储图的广度优先遍历

<■

开始

Intlowcost[max]

Prevex[max]

IntI,j,k,min

结束

图的普利姆算法求最小生成树

四、调试分析

1.实际完成的情况说明；

a.先任意创建一个图；

b.图的DFS,BFS的递归和非递归算法的实现

c.最小生成树（两个算法）的实现，求连通分量的实现

d.要求用邻接矩阵、邻接表等多种结构存储实现

支持的数据类型：整型和字符型

2.程序的性能分析，包括时空分析；

本程序的图的遍历是以邻接表做图的存储结构，其时间复杂度为0（n+e）。

3.上机过程中出现的问题及其解决方案；

a.程序开始对无权图和有权图的邻接矩阵的输出时，无边都用的10000（无

穷大int_max）表示的，这种表示和我们习惯上的0与8的表示有差异。所以在

程序中定义了全局变量n（初值为0）,来判断创建的无向图是有权图还是无权图,

n>0为有权图，此时输出的时候用8代替10000；n=0为无权图，此时输出的时

候用0代替10000.

b.程序中有的功能对某些图是不适用的，比如无权图没有最小生成树，非强

连通图没有最小生成树等。所以在程序中又新增了全局变量L1>0时表示为非强

连通图，则在求最小生成树时报错。

C.当程序先创建一个有权图后，n的值会大于1,第二次创无权图时也会被

程序认为有权图，所以在程序中在定义全局变量。（初值为0）,来判断创建了几

次图，当第二次创建图，即。=2时，所有全局变量在开始全归零。

4.程序中可以改进的地方说明；

当建立一个图时先得求其连通分量，从而确定全局变量1的值，从而才能判断该

图是否有最小生成树。

五、测试结果

创建一个无权图:

c:"E:\VC6\lyProjects\^^c4\Debug\test.exe

-------------------------日：显示该由的穗廨---------------------------

-------------------------【2、显示该图的邻接表-----------------------------

---------------------------------------------13、广度优先遍历---------------------------------

---------------------------------------------14、深度机先遍历---------------------------------

---------------------------------------------15、桂箍分量-------------------------------------

---------------------------------------------16、曩个生成忡iniSpanTreeJPRIM算法--------------

-------------------------【7、最小生成树MiniSpanTree_KRUSCAL算法-----------

在求最小生成树前请先求连通分量?

请选择菜单：

创建一个无向图：

请输入顶点和弧的个数

全i入各个顶点

abcdefg

输入一条边依附的顶点和权

ab1

输入一条边依附的顶点和权

ac1

输入一条边依附的顶点和权

bd1

输入一条边依附的顶点和权

be1

输入一条边依附的顶点和权

de1

输入一条边依附的顶点和权

fa1

逡是一个无权图

图G邻黄矩阵创建成功！

图G邻鬟表创建成功！

是否继续？i1/n：

03否继续？y/n：y

青选择菜单:

，ji谶续？y/n：y

邮接矩阵显示如下:邻接表显示如下请选择菜单：

[0,aJ->[2J->Cl]->End

31100003

[l,b]->[4]->[3J->[0]->End

L00100L度优先遍历：acbedfg

[2,c]->[0]->End

L000000

[3,d]->E4]->riJ->End

3100100是否继续？y/n：y

[4,e]->[3]->Ll]->End

3101000请选择菜单：

L5,f]->[6]->End

3000001

彳000010[6,g]->[5]->End深度优先遍历：acbedfg

是否继续？“n：

创建一个费强连通的有权图:

歆,E:\VC6\IyProjects\^4\：

习"E:\VC6\・yPrejects'课设

请输入顶点和弧的个数

55

输入各个顶点

abede

输入一条边依附的顶点和权

ab2

输入一条边依附的顶点和权

ac3

输入一条边依附的顶点和权

bd1

输入一条边依附的顶点和权

he3

输入一条边依附的顶点和权

de4

这是一个有权图

图G邻楼矩阵创建成功！

图G邻馨表创建成功！

是否继续？y/n：y

F选择菜单：

连通分量：

acbed

是否继续？y/n：y

通选择菜单：

署利拇算法：

<0,1>2

<0,2>3

<1,4>3

是否继续？y/n：y

事选择菜单：

■鲁斯卡尔算法:

<0,1>2

<0,2>3

<1,4〉3

是否继续？y/n：

六、用户手册

c'"E:\¥C6\・yProjects\课设4\Debug\test.exe"BISE

I

!-------------------------加、创建一无向图-------------------------------

1---------------------------------------------------0显示该图的邻言矩阵---------------------------：i

1---------------------------------------------------12、显示该图的邻馨表-----------------------------1

!-------------------------【3、匚哪先瀛历---------------------------------!

•14、深度优先遍历•

；西、他通分里：!

1---------------------------------------------------【6、蜃小生成科MiniSpanTreeJPRIM算法--------------1

最小生,成树算法-----------

1i-u----a---n----n----u----u----u----n----Q-----Q------u----u----u[7u,nunuunMninaiSQpannTrneeu_KQRUnSCnAuLuunuriuni1

在求最小生成树前请先求连通分量，

哥选择菜单：

a.先选0创建一个图。b.选择y继续操作。c.按照菜单编码选择操作。

七、体会与自我评价

在做这个程序的时候你首先必须知道图的一些概念，图是一种较线性表和树

更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素

只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层

次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相

关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间

的关系可以是任意的，图中任意两个数据元素之间都可能相关。

当我们拿到一个图时，我们对该图的遍历就要有一些方法，所以有了深度优

先遍历和广度优先遍历，我们要明白这两种遍历是怎么实现的，然后根据我们人

脑中的方法把它写成电脑算法。

对一个图我们还定义了连通分量，所以将图存到电脑中时，我们对连通分量

得有个算法。

求图的最小生成树有两种算法，普利姆是从结点出发寻找权最小的边，知道

所有结点都练通了；而克鲁斯卡尔算法则是从边出发，寻找使图连通的权值最小

边的方法。

算法的实现从人脑到电脑的转变是比较复杂的一件事，要求做到具体到实现

该方法的每一个步骤，然后再将每一个步骤通过代码实现。

这要求我们要明确各个数据元素和个元素之间的关系，然后才能明确使用算

法去调用这些数据。

通过本次的课程设计，我对数据结构有了一定的认识，明白了数据结构中数

据，数据关系，及对其操作的方法。但同时也发现在自己有很多的不足，在使用

语言和如何精炼语言需要进行更多的训练。

源代码:

#include<iostream>

#include<malloc.h>

usingnamespacestd;

#defineint_max10000〃最大值

staticintn=0;〃全局变量，判断有权图和无权图

staticinto=0;〃全局变量，清除BUG

staticini1=0;〃全局变量，清除BUG

#defineinf9999〃最小值的最大值

#definemax20〃最大顶点个数

typedefintVRType,QElemType,Status;

typedefcharInfoType,VertexType;

//miiiiiiiiiiiwiiiii邻接矩阵iiiiiuiiiiiiiuiiiiiiiiiiw

//------------------邻接矩阵定义------------------

typedefstructArcCell

(

VRTypeadj;//VRType是顶点关系类型。对无权图，用1或0表示相邻否；对带权图,

则为权值类型

InfoType求info;〃该弧相关信息的指针

}ArcCell,AdjMatrix[max][max];

typedefstruct

(

VertexTypevexs|max];〃顶点向量

AdjMatrixarcs;〃邻接矩阵

intvexnum,arcnum;〃图的当前顶点数和弧数

}MGraph_L;

//--------------------------------------------------------------------

intlocalvex(MGraph_LG,charv)〃返回V的位置

(

inti=0;

while(G.vexs[i]!=v)++i;

returni;

)

intcreatMGraph_L(MGraph_L&G)//创建图用邻接矩阵表示

(

charvl,v2;

inti,j,w;

coutvv"请输入顶点和弧的个数"v<endl;

cin»G.vexnum»G.arcnum;

coutvv"输入各个顶点"vvendl;

for(i=0;i<Gvexnum;++i)

(

cin»G.vexs[i];

fbr(i=0;i<Gvexnum;4-+i)

for(j=0;j<Gvexnum;++j)

(

Garcs[i][j].adj=int_max;

Garcs[i][j].info=NULL;

)

for(intk=O;k<G.arcnum;++k)

(

cout«"输入一条边依附的顶点和权"vvendl;

cin»v1»v2»w;〃输入一条边依附的两点及权值

i二k)calvex(G,vl);〃确定顶点VI和V2在图中的位置

j=localvex(G,v2);

Garcs[i][j].adj=w;

Garcs[j][i].adj=w;

)

for(i=0;i!=Gvexnum;+4-i)

for(j=0;j!=Gvexnum;++j)

(

if(G.arcs[i][j].adj!=l&&G.arcs[i][j].adj<int_max)n+=l;

)

if(n>=l)cout«”这是一个有权图”《endl;

elsecout<<"这是一个无权图"<<endl;

cout<<”图G邻接矩阵创建成功！"《endl;

returnGvexnum;

)

voidljjzprint(MGraph_LG)//邻接矩阵的输出

(

inti,j;

if(n==0)

(

fbr(i=O;i!=Gvexnum;++i)

(

for(j=0;j!=Gvexnum;++j)

(

if(G.arcs[i][j].adj==int_max){cout«nO"«nn;}

else{cout«G.arcs[i]fj].adj«,'

}

cout«endl;

)

)

else

{

fbr(i=O;i!=Gvexnum;++i)

for(j=0;j!=Gvexnum;++j)

if(Garcs[i][j].adj-int_max)(cout«"°°"«"";}

else{cout«Garcs[i][j].adj«"";}

)

cout«endl;

)

)

I

//llllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

//-----------------邻接表的定义----------------

lypedefstructArcNode//弧结点

(

intadjvex;〃该弧指向的顶点的位置

structArcNode*nextarc;〃指向下一条弧的指针

InfoType*info;〃该弧相关信息的指针

}ArcNode;

typedefstructVNode〃邻接链表顶点头接点

(

VertexTypedata;//顶点信息

ArcNode*firstarc;〃指向第一条依附该顶点的弧的指针

(VNode,AdjList;

typedefstruct//图的定义

(

AdjListvertices!max];

intvexnum,arcnum;〃图的当前顶点数和弧数

}ALGraph;

intcreatadj(ALGraph&gra,MGraph_LG)〃用邻接表存储图

(

inti=0,j=0;

ArcNode*arc;

for(i=0;i!=G.vexnum;++i)

{

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

gra.vertices[i].firstarc=NULL;

)

fdr(i=O;i!=Gvexnum;++i)

for(j=0;j!=G.vexnum;+4j)

(

if(Garcs[i][j].adj!=int_max)

(

arc=(ArcNode*)malloc(sizeof(ArcNode));

arc->adjvex=j;

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

gra.vertices[i].firstarc=arc;

)

gra.vexnum=G.vexnum;

gra.arcnum=G.arcnum;

cout«nSG邻接表创建成功!n«endl;

return1;

)

voidadjprint(ALGraphgra,MGraph_LG)〃邻接表输出

(

inti;

fbr(i=O;i!=gra.vexnum;++i)

(

ArcNode*p;

coutv<”["vvivv",”<vGvexs[i]<v"「；

p=gra.vertices[i].firstarc;

while(p!=NULL)

(

coutvv”->“v<"[“<vp->adjvex<<”『；

p=p->nextarc;

)

cout«',->',«uEnd,';

cout«endl;

)

)

//IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIN

//----------------队列定义-----------------

typedefstructQNode

(

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;

typedefstruct

(

QueuePtrfront;〃队头指针

QueuePtrrear;//队尾指针

(LinkQueue;

//------------------------------------------------------------

StatusInitQueue(LinkQueue&Q)〃初始化队列

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)retum0;〃存储分配失败

Q.front->next=NULL;

return1;

)

StatusEnQueue(LinkQueue&Q,QElemTypee)〃入队，插入元素e为Q的新的队尾元素

(

QueuePtrp;

p=(QueuePtr)malloc(sizeof(QNode));

if(!p)return0;//存储分配失败

p->data=e;p->next=NULL;

Q.rear->next=p;Q.rear=p;

return1;

}

StatusDeQueue(LinkQueue&Q,QElemType&e)〃出队，若队列不空，则删除Q的队头元素,

用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;

)

StatusQueueEmpty(LinkQueueQ)〃判断队为空

(

if(Q.front==Q.rear)return1;

return0;

)

//-------------------图的遍历-------------------

intvisited|max];〃访问标记

intwe;

intfirstadjvex(ALGraphgra,VNodev)〃返回依附顶点V的第一个点

〃即以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;

)

//-------------------广度优先遍历-------------------

voidBFSTraverse(ALGr叩hgra)

(

inti,e;

LinkQueueq;

fbr(i=O;i!=gra.vexnum;++i)visited[i]=0;

InitQueue(q);

for(i=O;i!=gra.vexnum;++i)

if(!visitedfi])

(

visited[i]=l;

cout«gra.vertices[i].data;

EnQueue(q,i)；

while(!QueueEmpty(q))

(

DeQueue(q,e);

fbr(we=firstadjvex(gra,gra.vertices[e]);we>=O;we=nextadjvex(gra,gra.vertices[e],we))

(

if(!visited[we])

(

visited[we]=l;

cout«gra.vertices[we].data;

EnQueue(q,we);

)

)

)

)

)

//----------------------深度优先遍历----------------------

intDFS(ALGraphgra,inti)

visited[i]=l;

intwel;

cout«gra.vertices[i].data;

for(we=firstadjvex(gra,gra.vertices[i]);we>=O;we=nextadjvex(gra,gra.vertices[i],we))

(

wel=we;

if(visited[we]==O)

DFS(gra,we);

we=wel;

)

return1;

)

intDFStra(ALGraphgra)

(

inti,j;

fbr(i=O;i!=gra.vexnum;++i)

(

visited[i]=O;

)

fbr(j=O;j!=gra.vexnum;++j)

(

if(visited|j]==O)DFS(gra,j);

)

return0;

)

//-------------------求连通分量...............——

intDFSTraverse_fen(ALGraphgra)

(

inti,j;

for(i=0;i!=gra.vexnum;++i)

visited[i]=0;

for(j=0;j!=gra.vexnum;++j)

(

if(visited[jl==0)

{

DFS(gra,j);

coul«endl;

1++；

)

)

return0;

)

//--------------------最小生成树的普利姆算法--------------------

typedefstruct

intadjvex;

intlowcost;

Jclosedge;

intMiniSpanTree_PRIM(intg[][max],intn)

(

intlowcost[max],prevex[max];//lowcost口存储当前集合分别到剩余结点的最小权值

//prevex口存储最短路径的前一个结点

inti,j,k,min;

for(i=2;i<=n;i++)//n个顶点，n・l条边

(

k)wcost[i]=g[l][i];//初始化

prevex[i]=l;//顶点未加入到最小生成树中

)

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

for(i=2;iv=n;i++)〃形成n-1条边的生成树

(

min=inf;

k=0;

for(j=2;j<=n;j++)//寻找满足边的一个顶点在U,另一个顶点在V的最小边

if((lowcost[j]<min)&&(lowcost[j]!=0))

(

min=lowcost|j];

k=j；

)

cout«,'(',«prevex[k]-1«",M«k-1«,,),'«min;

lowcosl[k]=0;//顶点k加入U

for(j=2;jv=n;j++)〃修改由顶点k到其他顶点边的权值

if(g[k][j]<lowcost[j])

(

lowcost[j]=g[k][j];

prevex|j]=k;

)

cout«endl;

}

return0;

}

//-----------------最小生成树的克鲁斯卡尔算法-------------------

intacrvisitedfmax];〃克鲁斯卡尔弧标记数组

intfind(intacrvisited[],intf)

(

while(acrvisited[f]>O)f=acrvisited[f];

returnf;

typedefstructacr

intpre;〃弧的一结点

intbak;〃弧另一结点

intweight;〃弧的权

}edg;

voidMiniSpanTREE_KRUSCAL(MGraph_LQALGraphgra)

(

edgedgs[max];

inti,j,k=O;

for(i=O;i!=Gvexnum;++i)

for(j=i;j!=G.vexnum;++j)

(