数据结构与算法专题实验报告 - 图文

else if (s>=0&&s=0&&e0) {

cost[s][e =cost[e][s]=len; // 实现无向图的操作

i++; } else

cout<<\边值错误，请重新输入!\} }

void shortdjs() //寻找最短路径的算法函数的实现 {

int s[MAX];

int mindis,dis,i,j,v0=0,u; for(i=0;i

dist[i]=cost[v0][i]; path[i].pnode[0]=v0; path[i].num=0; s[i]=0; } s[v0]=1;

for(i=1;i

mindis=up; for (j=1;j

if(s[j]==0&&dist[j]

{ u=j;

mindis=dist[j];

}

s[u]=1; //当s[u]=1时表示权值为无穷大 for (j=1;j

dis=dist[u]+cost[u][j]; if(dist[j]>dis) {

dist[j]=dis; path[j].num++;

path[j].pnode[path[j].num]=u; } }

path[i].num++;

path[i].pnode[path[i].num]=i; } }

void dispath() // 输出最短路径 {

int i,j;

cout<

cout<终点) 最短长度 最短路径\ for(i=1;i

cout<<\ if(dist[i]

cout<

cout<<\for (j=0;j

cout<<\} }

void main () //主函数 {

creatgraph(); //直接调用三个函数就行 shortdjs(); dispath(); }

返回

第4题 最短路径

1 题目：

创建一个具有n（n≥1）个顶点的无向图的邻接矩阵，并对其按照“深

度优先搜索”和“广度优先搜索”方法进行遍历。

2 目标：

1.编写C程序予以实现。

2.程序要求能输入图的顶点数、边数以及边的关系，并自动生成邻接矩阵。 3.结果输出邻接矩阵和遍历的路径。 4.熟悉无向图的两种遍历算法。

3 设计思想：

1．

考虑用一个n维数组来存放无向图，若两个结点之间有边，则n维数组对应下标的那个元素值为1，否则为0；

2．

在输入图的顶点数和边数时我充分考虑了边界条件，顶点数G.vexnum在[0，MAXV]范围内，边数在[0，G.vexnum*(G.vexnum-1)/2]范围内，在这个

范围内，程序继续向下执行，否则返回重新输入；

3． 4．

输出邻接矩阵的实质是输出 n维数组，我用两重循环来实现； 深度优先遍历我采用迪杰特斯拉算法，不过要在此算法中间加一个判断，所有的结点是否都已经遍历过，如果是就退出，如果不是，则按顺序从序号小的开始向大的寻找，找到一个没有遍历过的结点继续调用深度优先遍历算法；

5． 6．

广度优先遍历我采用了非递归算法，其实质和深度优先遍历算法相同； 在主函数中直接调用

CreatGraph(G)， DispMatrix(G) ，

DepthDisp(G,v) ，WidthDisp(G)函数即可。

4 算法描述：

step1:设置无向图最多的顶点数// 这个设置为了更好的输出邻接矩阵；

step2: 定义无向图的数据结构； step3:实现生成无向图函数CreatGraph(G)

a. 输入顶点数n，判断它是否在允许的范围内，不在则返回重新输入；

b. 输入无向图的边数G.arcnum，判断它是否在允许的范围内，不在则返回重新输

入 ；

c. 输入边，for语句(k=1 to G.arcnum){ 输入两顶点v,w，判断v!=w &

0

step4:实现输出邻接矩阵函数 DispMatrix(Graph &G) ， 双重for循环实

现输出无向图的邻接矩阵；

step5:实现深度优先遍历的递归算法函数DepthDisp(Graph &G,int v) a. 从v开始遍历，设置计数器num=0 ，并置顶点v已访问；

b. for语句（i=1 to G.vexnum）判断 G.arcs[v][i]!=0&&visited[i]==0，

如果是递归调用深度优先遍历的递归算法函数DepthDisp(G, i)，如果不是则退出；

c. 用for和if 语句判断是否所有的顶点都已经遍历完，

if num