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

发布时间 : 星期二 文章数据结构与算法专题实验报告 - 图文更新完毕开始阅读

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