实验六 无向图中求两点间的所有简单路径Word文件下载.docx
- 文档编号:6871671
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:17
- 大小:72.23KB
实验六 无向图中求两点间的所有简单路径Word文件下载.docx
《实验六 无向图中求两点间的所有简单路径Word文件下载.docx》由会员分享,可在线阅读,更多相关《实验六 无向图中求两点间的所有简单路径Word文件下载.docx(17页珍藏版)》请在冰点文库上搜索。
//设置标记}
算法的基本思想
程序需要输入城市编号及城市的编号对以实现城市间的高速公路的输入。
然后输入某两个城市,得出城市间的所有简单路径。
得到无向图中某两个城市间的简单路径,考虑使用基于深度优先思想,通过相应的设置标志的方式使最终能不重复地走遍所有的简单路径。
程序流程
程序主要由四个步骤组成:
(1)
输入城市总数
(2)
输入正确的城市编号列表
(3)
输入所有的有高速公路直接连接的城市对编号
(4)
循环输入需要寻找路径的城市对的编号寻找它们之间的所有简单路径。
三、详细设计
实现概要设计中的数据类型
为了方便编写这个程序,图用二阶矩阵来存储。
图的构建和基本操作:
class
Graphm
:
public
Graph
{
private:
int
numVertex,
numEdge;
**matrix;
int
*mark;
public:
Graphm(int
numVert)
i,
j;
numVertex
=
numVert;
numEdge
0;
mark
new
int[numVert];
for
(i=0;
i<
numVertex;
i++)
mark[i]
UNVISITED;
matrix
(int**)
int*[numVertex];
matrix[i]
int[numVertex];
(int
j=0;
j<
j++)
matrix[i][j]
}
<
1>
返回结点的第一条邻边。
由于用邻接矩阵来存储,当下标matrix[v][i]不等于
0
时,就找到了邻边。
成功就返回邻边的位置。
first(int
v)
i;
if
(matrix[v][i]
!
0)
return
return
}
2>
返回下一条邻边。
当下标matrix[v][i]不等于0
成功就返回邻
边的位置。
next(int
v1,
v2)
{
for(i=v2+1;
(matrix[v1][i]
0)
3>
加边。
传入结点,若该边不存在,则结点数+1,并添加该边。
void
setEdge(int
v2)
(matrix[v1][v2]
==
numEdge++;
matrix[v1][v2]
1;
4>
获取结点的个数。
直接返回个数。
n()
5>
获取边的数量。
直接返回边的数量。
e()
查找:
从起始的城市对应的顶点开始,逐次访问其邻接顶点。
访问一个顶点时,标记为1,将其存入数组中。
如果被访问的点在其此次所在的路径中之前已被访问(包括此次访问到的是起始顶点),或该顶点没有邻接顶点了且该顶点不是目的顶点,就不再继续访问其邻接顶点,此条路径不再继续。
如果该顶点是目的顶点,则将该条路径上之前访问的包括此次访问的顶点全部输出,显示所找到的一条简单路径。
PathAll(Graphm
*G,int
u,int
v,int
*path,string*
str,int
&
d)
//d是到当前为止已走过的路径长度,调用时初值为-1
w,i;
G->
setMark(u,1);
d++;
//路径长度增1
path[d]=u;
//将当前顶点添加到路径中
(u==v&
d>
=1)
//输出一条路径
cout<
"
这两个城市间一条的简单路径为:
;
=d;
str[path[i]]<
endl;
(w=G->
first(u);
w<
n();
w=G->
next(u,w))
if
(G->
getMark(w)==0)
PathAll(G,w,v,path,str,d);
setMark(u,0);
//恢复,可以再寻找
d--;
//去掉这个点
算法的时空分析
邻接矩阵的空间代价为Θ(|V|2),查找设共计访问的结点次数为k,则易知函数的时间开
销为Ɵ(k)。
输入和输出的格式
输入
请输入城市数量
请输入城市编号:
0001
0002
请输入城市编号
:
0003
……
城市编号列表输入完毕!
请输入之间有高速公路连接的城市编号c1和c2:
请输入要查找的两个城市之间的路
等待输入
输出
从c1到c2之间的路为
四、测试结果
五、用户使用说明(可选)
1、本程序的运行环境为DOS操作系统,执行文件为实验六2.exe
2、运行程序时:
(1)显示提示“请输入结点总数”,此时输入结点数。
(2)数据输入完毕后,查找所有简单路径,若有则输出若没有输出这两个点不连通。
六、实验心得
这次实验让我更加了解深度优先搜索遍历,对课堂内容更加了解。
七、附录
#include<
iostream>
fstream>
string.h>
iomanip>
usingnamespacestd;
classAStack
private:
intsize;
//栈的大小
inttop;
//栈中元素的多少
string*listArray;
public:
AStack(intsz=0)//构建栈
{
size=sz;
top=0;
listArray=newstring[sz];
}
~AStack()//销毁栈
delete[]listArray;
}
boolpush(conststring&
item)//压栈
if(top==size)returnfalse;
//如果栈已满则returnfalse
else
{
listArray[top++]=item;
returntrue;
}
boolpop(string&
it)//出栈
if(top==0)returnfalse;
//如果栈为空栈,则returnfalse
else
{
it=listArray[--top];
intlength()const//获取栈的长度
returntop;
voidprint()
stringCh;
AStackb(length());
while(pop(Ch))
b.push(Ch);
while(b.pop(Ch))
cout<
Ch<
"
push(Ch);
};
classPoint
stringLessonName;
intViMark;
classGraph
{//Implementadjacencymatrix
intnumVertex,numEdge;
//Storenumberofverticesedges
int**matrix;
//Pointertoadjacencymatrix
Point*mark;
//Pointertomarkarray
Graph(intnumVert)
{//Makegraphw/numVertvertices
inti,j;
numVertex=numVert;
numEdge=0;
mark=newPoint[numVert];
//Initializemarkarray
for(i=0;
i<
i++)
mark[i].ViMark=-1;
matrix=(int**)newint*[numVertex];
//Makematrix
matrix[i]=newint[numVertex];
numVertex;
i++)//Edgesstartw/0weight
for(intj=0;
j<
j++)matrix[i][j]=0;
~Graph()
delete[]mark;
for(inti=0;
delete[]matrix[i];
delete[]matrix;
intn()
returnnumVertex;
inte()
returnnumEdge;
intfirst(intv)
{//Returnv'
sfirstneighbor
inti;
if(matrix[v][i]!
=0&
mark[i].ViMark==-1)returni;
returni;
//Returnnifnone
intnext(intv1,intv2)
//Getv1'
sneighborafterv2
for(i=v2+1;
if(matrix[v1][i]!
mark[i].ViMark==-1)
//cout<
此时next的i值是:
v1+1<
i+1<
//Setedge(v1,v2)towgt
voidsetEdge(intv1,intv2,intwgt)
if(matrix[v1][v2]==0)numEdge++;
matrix[v1][v2]=wgt;
voiddelEdge(intv1,intv2)
{//Deleteedge(v1,v2)
if(matrix[v1][v2]!
=0)
numEdge--;
matrix[v1][v2]=0;
intweight(intv1,intv2)
returnmatrix[v1][v2];
stringgetVal(intv)
returnmark[v].LessonName;
intgetMark(intv)
{
returnmark[v].ViMark;
voidsetVal(intv,stringval)
mark[v].LessonName=val;
voidsetMark(intv,intMark)
mark[v].ViMark=Mark;
voidFind(stringsearch,int&
v)
i++)
if(mark[i].LessonName==search)
v=i;
return;
Yourinputiswrong"
voidDFS(Graph*G,intv1,intorigin,intv2,AStack&
b,intM[100][100],intD[100],int&
count)
{
b.push(G->
getVal(v1));
//D[count]=v1;
//count++;
intv;
G->
setMark(v1,1);
if(G->
getVal(v1)==G->
getVal(v2))
for(intj=0;
j++)
setEdge(i,j,M[i][j]);
两城间的路径为:
b.print();
b.pop(Ch);
setMark(v2,-1);
count++;
for(intw=G->
first(v1);
w<
w=G->
next(v1,w))
setEdge(w,v1,0);
getMark(w)==-1||w==5)
现在要访问的结点是:
w+1<
DFS(G,w,origin,v2,b,M,D,count);
Find(Ch,v);
setMark(v,-1);
main()
intn;
intv1;
intv2;
intM[100][100];
stringCh1;
stringCh2;
intD[100];
intcount=0;
请输入结点总数:
cin>
>
n;
Grapha(n);
Ch;
a.setVal(i,Ch);
请输入城市之间的高速公路:
Ch1;
Ch2;
while(Ch1!
="
0"
)
a.Find(Ch1,v1);
a.Find(Ch2,v2);
a.setEdge(v1,v2,10);
a.setEdge(v2,v1,10);
for(intk=0;
k<
k++)
M[j][k]=a.weight(j,k);
请输入要查找的两个城市:
Ch1>
AStackb(n);
DFS(&
a,v1,v1,v2,b,M,D,count);
if(count==0)
此两点不连通"
system("
pause"
);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验六 无向图中求两点间的所有简单路径 实验 图中求 两点 所有 简单 路径