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

时间复杂度： O(n2 )

（5）求最短路径，连通性判断 int dist[MAXSIZE][MAXSIZE]; int path[MAXSIZE][MAXSIZE]; template

void Floyd(MGraph G) {

for(int i=0;i

//

寻找最短路径

for(int j=0;j

dist[i][j]=G.arcs[i][j];

if(dist[i][j]!=MAX_VALUE) path[i][j]=i; else

path[i][j]=-1;

}

for(int k=0;k

for(int i=0;i

for(int j=0;j

if(dist[i][k]+dist[k][j]

dist[i][j]=dist[i][k]+dist[k][j]; path[i][j]=k;

}

cout<<\任意两点间的最短路径长度 int l=1;

for(int i=0;i

for(int j=0;j

cout<

if(l>G.arcNum) {cout<

}

}

( 以矩阵表示）： \

更新迭代数组 Disk[][]

时间复杂度： O(n3)

3.

程序运行结果 （ 1）流程图：

初始化带权值的无向图

深度优先遍历，广度优先遍历

用普利姆算法求最小生成树

用克鲁斯卡尔算法求最小生成树

初始化带权值的有向图

用 Floyd 算法求任意两点间最短路径，并判断连通性

删除图

（ 2）本程序所用的图

带权值的无向图

V0

9

6 V1

带权值的有向图

2 V2

V0

6 4

2

V2

3 9 V1

（ 3）程序结果

4.

总结

（1）遇到的问题：私有数据访问权的问题，在编程时应该注意

（ 2）心得体会：通过这次实验，我掌握了图基本操作的实现方法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念等等。 （ 3）改进：

可以适当对某些步骤进行合并或省略，使程序更加简洁。

源代码：

#include using namespace std; const int MAXSIZE=20; const int MAX_EDGE=20; const int MAX_VALUE=1000; struct VEdge{

int fromV;// int endV;// int weight;//

};

VEdge EdgeList[MAX_EDGE]; template class MGraph { public:

MGraph(T a[],int n,int e); MGraph(T a[],int n,int e,int h); void DFS(int v); void BFS(int v);

void Prim(MGraph G);

void Kruskal(VEdge E[],int n,int e); int vNum,arcNum;

int arcs[MAXSIZE][MAXSIZE];// int arc[MAXSIZE][MAXSIZE];

private:

T vertex[MAXSIZE];

};

用于储存权值的数组

起始顶点

边的权值

终止顶点

template //

{

int i,j,k,l;

构造带权值的有向图

MGraph::MGraph(T a[],int n,int e,int h)