数据结构实验-图的遍历和最小生成树

:V

是图的顶点集

,VR

是图中弧的集合

.

操作结果

:

按

V

和

VR

是定义构造图

G

.

Sort(edge* ,MGraph *)

初始条件

:

图

G

存在，各边权值已知；

操作结果

:

对权值进行排序；

Find(int *, int )

初始条件

:

前者为已存在的集合，后者为集合中的元素；

< /p>

操作结果

:

查找函数，确定后者所属子集 ；

MiniSpanTree(MGraph *)

初始条件

:

图

G

存在，各边权值已知；

操作结果

:

生成最小树；

Swapn(edge *, int, int)

初始条件

:

图

G

存在，各边权值已知；

操作结果

:

交换某两个边的权值；

2

图的存储结构

typedef struct

{

int adj;

int weight;

}AdjMatrix[MAX][MAX];

typedef struct

{

AdjMatrix arc;

int vexnum, arcnum;

}MGraph;

typedef struct

{

int begin;

int end;

int weight;

}edge;

3

本程序包含的模块

}

1

）初始化操作，结构体定义；

2

）函数声明模块；

3

）函数定义模块；

4

）主程序模块

Main()

{

调用函数生成图；

判断图是否为空；

（空则从新输入）

调用函数生成最小生成树；

退出；

二、详细设计

#include

#include

using namespace std;

#define int_max 10000

#define inf 9999

#define max 20

//

…………………………………………邻接矩阵定义……………………

typedef struct ArcCell

{

int adj;

char *info;

}ArcCell,AdjMatrix[max][max];

typedef struct

{

char vexs[max];

AdjMatrix arcs;

int vexnum,arcnum;

}MGraph_L;

//^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

int localvex(MGraph_L G

,char v)//

返回

V

的位置

{

int i=0;

while(G

.vexs[i]!=v)

++i;

return i;

}

int creatMGraph_L(MGraph_L &G)//

创建图用邻接矩阵表示

{

char v1,v2;

int i,j,w;

G

.vexnum=7;=12;

for(i=0;i!=;++i)

{

cout<<

输入顶点

V

cin> >G

.vexs[i];

}

for(i=0;i!=;++i)

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

{

G

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

G

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

}

G

.arcs[0][1].adj=24;

G

.arcs[1][0].adj=24;

G

.arcs[0][2].adj=8;

G

.arcs[2][0].adj=8;

G

.arcs[0][3].adj=15;

G

.arcs[3][0].adj=15;

G

.arcs[1][4].adj=6;

G

.arcs[4][1].adj=6;

G

.arcs[1][6].adj=3;

G

.arcs[6][1].adj=3;

G

.arcs[2][4].adj=7;

G

.arcs[4][2].adj=7;

G

.arcs[2][5].adj=3;

G

.arcs[5][2].adj=3;

G

.arcs[3][5].adj=5;

G

.arcs[5][3].adj=5;

G

.arcs[3][6].adj=4;

[6][3].adj=4;

G

.arcs[4][5].adj=2;

G

.arcs[5][4].adj=2;

G

.arcs[4][6].adj=9;

G

.arcs[6][4].adj=9;

G

.arcs[5][6].adj=3;

G

.arcs[6][5].adj=3;

< br>cout<<

图

G

邻接矩阵创建 成功！

return G

.vexnum;

}

void ljjzprint(MGraph_L G) //

邻接矩阵的输出

{

int i,j;

for(i=0;i!=;++i)

{

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

cout<<[i][j].adj<<

cout<

}

}

int visited[max];//

访问标记

int we;

typedef struct arcnode//

弧结点

{

int adjvex;//

该弧指向的顶点的位置

struct arcnode *nextarc;//

弧尾相同的下一条弧

char *info;//

该弧信息

}arcnode;

typedef struct vnode//

邻接链表顶点头接点

{

char data;//

结点信息

arcnode *firstarc;//

指向第一条依附该结点的弧的指针

}vnode,adjlist;

typedef struct//

图的定义

{

adjlist vertices[max];

int vexnum,arcnum;

int kind;

}algraph;

//

…………… ……………………………队列定义……………………

typedef struct qnode

{

int data;

struct qnode *next;

}qnode,*queueptr;

typedef struct

{

queueptr front;

queueptr rear;

}linkqueue;

//

< br>………………………………………………………………………

typedef struct acr

{

int pre;//

弧的一结点

int bak;//

弧另一结点

int weight;//

弧的权

}edg;

int creatadj(algraph &gra,MGraph_L G)//

用邻接表存储图

{

int i=0,j=0;

arcnode *arc,*tem,*p;

for(i=0;i!=;++i)

{

es[i].data=[i];

es[i].firstarc=NULL;

}

for(i=0;i!=;++i)

{

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

{

if(es[i].firstarc==NULL)

{

if( G

.arcs[i][j].adj!=int_max&&j!=G

< br>.vexnum)

{

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

arc->adjvex=j;

es[i].firstarc=arc;

arc->nextarc=NULL;

p=arc;

++j;

whi le([i][j].adj!=int_max&&j!=G

.vexnum)

{

tem=(arcnode *)malloc(sizeof(arcnode));

tem->adjvex=j;

es[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;

}

}

}

}

=;

=;

return 1;

}

int firstadjvex(algraph gra,vnode v)//< /p>

返回依附顶点

V

的第一个点

//

即以

V

为尾的第一个结点

{

if(rc!=NULL)

return rc->adjvex;

}

int nextadjvex(algraph gra,vnode v,int w)//

返回依附顶点

V

的相对于

W