图Word格式文档下载.docx
- 文档编号:8406583
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:25
- 大小:124.92KB
图Word格式文档下载.docx
《图Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《图Word格式文档下载.docx(25页珍藏版)》请在冰点文库上搜索。
virtualResultCodeRemove(intu,intv)=0;
virtualboolExist(intu,intv)const=0;
protected:
intn,e;
};
classSeqQueue
SeqQueue(intmSize);
~SeqQueue(){delete[]q;
}
boolIsEmpty()const{returnfront==rear;
boolIsFull()const{return(rear+1)%maxSize==front;
boolFront(T&
x)const;
boolEnQueue(Tx);
boolDeQueue();
voidClear(){front=rear=0;
private:
intfront,rear;
intmaxSize;
T*q;
SeqQueue<
T>
:
SeqQueue(intmSize)
maxSize=mSize;
q=newT[maxSize];
front=rear=0;
boolSeqQueue<
Front(T&
x)const
if(IsEmpty())
{
returnfalse;
}
x=q[(front+1)%maxSize];
returntrue;
EnQueue(Tx)//在队尾插入
if(IsFull())
cout<
<
"
Full"
endl;
q[rear=(rear+1)%maxSize]=x;
returntrue;
DeQueue()//删除队头元素
Underflow"
front=(front+1)%maxSize;
classMGraph:
publicGraph<
//邻接矩阵类
MGraph(intmSize,constT&
noedg);
~MGraph();
ResultCodeInsert(intu,intv,T&
w);
ResultCodeRemove(intu,intv);
boolExist(intu,intv)const;
voidDFS();
voidBFS();
T**a;
TnoEdge;
voidDFS(intv,bool*visited);
voidBFS(intv,bool*visited);
MGraph<
noedg)//构造函数
n=mSize;
e=0;
noEdge=noedg;
a=newT*[n];
for(inti=0;
i<
n;
i++)
a[i]=newT[n];
for(intj=0;
j<
j++)
a[i][j]=noEdge;
a[i][j]=0;
~MGraph()//析构函数
delete[]a[i];
delete[]a;
ResultCodeMGraph<
Insert(intu,intv,T&
w)//插入函数
if(u<
0||v<
0||u>
n-1||v>
n-1||u==v)
returnFailure;
if(a[u][v]!
=noEdge)
returnDuplicate;
a[u][v]=w;
e++;
returnSuccess;
template<
Remove(intu,intv)//删除函数
if(a[u][v]==noEdge)
returnNotPresent;
a[u][v]=noEdge;
e--;
boolMGraph<
Exist(intu,intv)const//判断边是否存在
n-1||u==v||a[u][v]==noEdge)
returnfalse;
voidMGraph<
DFS()//深度遍历
bool*visited=newbool[n];
visited[i]=false;
for(i=0;
if(!
visited[i])
DFS(i,visited);
delete[]visited;
DFS(intv,bool*visited)
visited[v]=true;
"
v;
for(inti=0;
if(a[v][i]!
=noEdge&
&
a[v][i]!
=0&
!
DFS(i,visited);
BFS()//广度遍历
bool*visited=newbool[n];
visited[i]=false;
for(i=0;
if(!
BFS(i,visited);
delete[]visited;
BFS(intv,bool*visited)
SeqQueue<
int>
q(n);
q.EnQueue(v);
while(!
q.IsEmpty())
q.Front(v);
q.DeQueue();
visited[i]=true;
i;
q.EnQueue(i);
//结点类
classENode
ENode(){nextArc=NULL;
ENode(intvertex,Tweight,ENode*next)
adjVex=vertex;
w=weight;
nextArc=next;
intadjVex;
Tw;
ENode*nextArc;
classLGraph:
//邻接表类
LGraph(intmSize);
~LGraph();
ResultCodeInsert(intu,intv,T&
ResultCodeRemove(intu,intv);
boolExist(intu,intv)const;
ENode<
**a;
LGraph<
LGraph(intmSize)//构造函数
n=mSize;
e=0;
a=newENode<
*[n];
a[i]=NULL;
~LGraph()
*p,*q;
p=a[i];
q=p;
while(p)
p=p->
nextArc;
deleteq;
delete[]a;
boolLGraph<
if(u<
*p=a[u];
while(p&
p->
adjVex!
=v)
p)
elsereturntrue;
ResultCodeLGraph<
w)//插入
returnFailure;
if(Exist(u,v))
returnDuplicate;
ENode<
*p=newENode<
(v,w,a[u]);
a[u]=p;
Remove(intu,intv)//删除
*p=a[u],*q;
q=NULL;
while(p&
if(q)
q->
nextArc=p->
else
a[u]=p->
deletep;
intmain()//主函数
intn,g,operate;
cout<
请输入元素的个数:
;
cin>
>
A(n,INFTY);
B(n);
请输入边的条数:
g;
int*a=newint[g];
int*b=newint[g];
int*w=newint[g];
请输入边及权值:
a[i]>
b[i]>
w[i];
A.Insert(a[i],b[i],w[i]);
B.Insert(a[i],b[i],w[i]);
该图的深度优先遍历为:
A.DFS();
该图的广度优先遍历为:
A.BFS();
do
请输入您要的操作\n1:
查找2:
删除3:
退出\n"
cin>
operate;
}while(operate!
=1&
operate!
=2&
=2);
if(operate==1)
请输入要搜索的边:
intc,d;
c>
d;
if(A.Exist(c,d))
邻接矩阵中该边存在!
邻接矩阵中该边不存在!
if(B.Exist(c,d))
邻接表中该边存在!
邻接表中该边不存在!
elseif(operate==2)
请输入要删除的边:
inte,f;
e>
f;
if(A.Remove(e,f)==Success)
邻接矩阵中删除该边成功!
elseif(A.Remove(e,f)==NotPresent)
输入错误!
if(B.Remove(e,f)==Success)
邻接表中删除该边成功!
elseif(B.Remove(e,f)==NotPresent)
邻接表中输入错误!
删除后该图的深度优先遍历为:
删除后该图的广度优先遍历为:
elseif(operate==3)
return0;
}while(0==0);
五、测试与调试
六、实验小结
本次实验很难,运行成功后不仅加深了我对图的理解,更加增长了我的士气,那种敢于解决问题的勇气,以及解决问题的方法。
在进行编程时,不可能一次成功,要勤加注释,方便在修正错误时进行更改。
飞机最少换乘次数问题:
设有n个城市,编号为0∽n-1,m条航线的起点和终点由用户输入提供。
寻找一条换乘次数最少的线路方案。
二、概要设计
实用有向图表示城市间的航线,航线权值是零,使用Dijkstra算法实现求换乘最少方案。
三、
详细设计
四、程序代码
string.h>
constintINF=2147483647;
enumResultCode{Underflow,Duplicate,Failure,Success,NotPresent,OutOfBounds};
classGraph//抽象类
public:
virtualResultCodeInsert(intu,intv,Tw)=0;
protected:
//邻接矩阵类
MGraph(intmSize,constTnoedg);
~MGraph();
ResultCodeInsert(intu,intv,Tw);
intChoose(int*d,bool*s);
voidDijkstra(intv,T*d,int*path);
T**a;
TnoEdge;
MGraph(intmSize,constTnoedg)
noEdge=noedg;
a=newT*[n];
a[i]=newT[n];
for(intj=0;
a[i][j]=noEdge;
a[i][i]=0;
~MGraph()
delete[]a[i];
Insert(intu,intv,Tw)
if(a[u][v]!
a[u][v]=w;
e++;
returnSuccess;
Remove(intu,intv)
if(a[u][v]==noEdge)
returnNotPresent;
a[u][v]=noEdge;
e--;
Exist(intu,intv)const
intMGraph<
Choose(int*d,bool*s)//求最小d[i]
inti,minpos;
Tmin;
min=INF;
minpos=-1;
if(d[i]<
=min&
s[i])
min=d[i];
minpos=i;
returnminpos;
Dijkstra(intv,T*d,int*path)//迪杰斯特拉算法
inti,k,w;
if(v<
0||v>
n-1)
throwOutOfBounds;
bool*s=newbool[n];
s[i]=false;
d[i]=a[v][i];
if(i!
=v&
d[i]<
INF)
path[i]=v;
else
path[i]=-1;
s[v]=true;
d[v]=0;
for(i=1;
k=Choose(d,s);
s[k]=true;
for(w=0;
w<
w++)
s[w]&
(d[k]+a[k][w])<
d[w])
d[w]=d[k]+a[k][w];
path[w]=k;
intmain()
intn,m;
城市总数:
航线总数:
m;
MGraph<
A(n,INF);
intc,f;
请输入每条航线的起点和终点:
第"
i+1<
条航线:
A.Insert(c,f,1);
chars;
do{
intv,w;
请输入你的起点和终点:
v>
w;
while(v<
0||w<
0||w>
请重新输入:
int*b=newint[n];
int*d=newint[n];
int*path=newint[n];
A.Dijkstra(v,d,path);
inte=n-1;
b[j]=-2;
if(w!
j=w;
while(path[j]!
=-1)
b[e]=path[j];
j=path[j];
if(e==n-1||d[j]==INF)
该路间无线路!
从"
v<
到"
的换乘次数最小的线路方案为:
for(intk=0;
k<
k++)
if(b[k]!
=-2)
b[k]<
"
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- docx
![提示](https://static.bingdoc.com/images/bang_tan.gif)