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

数据结构实验报告

1． 实验要求

（1）实验目的

通过选择下面5个题目之一进行实现，掌握如下内容： ? 掌握图基本操作的实现方法 ? 了解最小生成树的思想和相关概念 ? 了解最短路径的思想和相关概念 ? 学习使用图解决实际问题的能力 (2)实验内容

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

1、图的建立 2、图的销毁 3、深度优先遍历图 4、广度优先遍历图

5、使用普里姆算法生成最小生成树 6、使用克鲁斯卡尔算法生成最小生成树 7、求指定顶点到其他各顶点的最短路径 8、其他：比如连通性判断等自定义操作 编写测试main()函数测试图的正确性

2. 程序分析

2.1 存储结构

图：

(1) 带权值的无向图

V0

9 6

V1 2 V2

(2) 带权值的有向图

V0 6 3 9 4

V1 2 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<

时间复杂度：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;//初始化U={vo} for(int i=1;i

int k=mininum(G,lowcost);//求下一个边权值最小的邻接点 cout<<'V'<

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 {

int k=0,i,j;

for(i=0;i

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 m=E[j].fromV,n=E[j].endV;