北邮数据结构实验第二次实验图

数据结构实验报告

1． 实验要求

（ 1）实验目的

通过选择下面 5 个题目之一进行实现，掌握如下内容：

掌握图基本操作的实现方法

了解最小生成树的思想和相关概念

了解最短路径的思想和相关概念

学习使用图解决实际问题的能力

(2) 实验内容

根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。

图的基本功能：

1、图的建立

2、图的销毁

3、深度优先遍历图

4、广度优先遍历图

5 、使用普里姆算法生成最小生成树

6、使用克鲁斯卡尔算法生成最小生成树

7、求指定顶点到其他各顶点的最短路径

8、其他：比如连通性判断等自定义操作

编写测试 main() 函数测试图的正确性

2. 程序分析

2.1 存储结构

图：

(1) 带权值的无向图

V0

9

6 V1

(2) 带权值的有向图

V0

2

V2

6

3 9 V1

2

4

V2

2.2 关键算法分析 （1）深度优先遍历

int visited[MAXSIZE]={false}; template

void MGraph::DFS(int v) {

cout<

for(int j=0;j

if(arc[v][j]==1&&!visited[j])

DFS(j);

}

时间复杂度： O(n2) （2）广度优先遍历 int queue[MAXSIZE];

int f=0,r=0;

cout<

v=queue[++f];

for(int j=0;j

if(arc[v][j]==1&&!visit[j]) {

cout<

queue[++r]=j; }

时间复杂度： O（ n2） （3）普利姆算法 int adjvex[MAXSIZE]; int lowcost[MAXSIZE]; int MAX=10000; template

int mininum(MGraph G,int a[]) {

int min=MAX; int k=0;

for(int i=0;i

if(a[i]!=0&&a[i]

min=a[i]; k=i;

}

}

return k;

}

template

void MGraph:: Prim(MGraph G) {

for(int i=0;i

adjvex[i]=0;

lowcost[i]=G.arcs[0][i];

}

lowcost[0]=0;// {

int k=mininum(G,lowcost);// lowcost[k]=0;

for(int j=0;j

if(lowcost[j]!=0&&G.arcs[k][j]

lowcost[j]=G.arcs[k][j]; adjvex[j]=k;

}

}

} }

时间复杂度： O(n2) （4）克鲁斯卡尔算法 template

void GenSortEdge(MGraph G,VEdge E[])//

获取 EdgeList

求下一个边权值最小的邻接点

寻找 U-{V-U} 中边权值最小的顶点

初始化 U={vo}

for(int i=1;i

cout<<'V'<

{

int k=0,i,j;

for(i=0;i

边赋值

for(j=i;j

if(G.arcs[i][j]!=MAX) {

E[k].fromV=i; E[k].endV=j;

E[k].weight=G.arcs[i][j]; k++;

}

for(i=0;i

{

for(j=i+1;jE[j].weight)

{

VEdge t=E[i]; E[i]=E[j]; E[j]=t;

}

}

}

const int MAX_VERTEXT=20; template

void MGraph:: Kruskal(VEdge E[],int n,int e) {

int vset[MAX_VERTEXT]; for(int i=0;i

int k=0,j=0; while(k

int m=E[j].fromV,n=E[j].endV;

int sn1=vset[m];//m

int sn2=vset[n];//n

所属的集合 所属的集合

if(sn1!=sn2) {

cout<<'V'<

for(int i=0;i

if(vset[i]==sn2)//

集合编号为 sn2 的全部改为vset[i]=sn1;

sn1