最短路径与最小生成树Word下载.docx
《最短路径与最小生成树Word下载.docx》由会员分享，可在线阅读，更多相关《最短路径与最小生成树Word下载.docx（11页珍藏版）》请在冰点文库上搜索。
intinfo;
}ArcNode;
typedefstructVNode
chardata;
ArcNode*firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct
AdjListverties;
intvexnum,arcnum;
}ALGraph;
ALGraphG;
//对象G
intLocateVek（ALGraph,char）;
//返回结点位置
intminimum（close）;
//返回最小数
voidMinSpanTree_PRIM（ALGraph,char）;
//最小生成树
voidCreate（ALGraph&
）;
//创建邻接表
intmain（）
chara;
inti=1;
Create（G）;
/*for（inti=1;
i<
=G.vexnum;
i++）
{
for（s=G.verties[i].firstarc;
s!
=NULL;
s=s->
nextarc）
cout<
<
G.verties[i].data<
"
---"
G.verties[s->
adjvex].data<
===="
s->
info<
endl;
}*/
while（i）
cout<
输入起点:
"
;
cin>
>
a;
MinSpanTree_PRIM（G,a）;
如果结束输入'
0'
否则输入'
1'
:
i;
}
return0;
}
intLocateVek（ALGraphG,charu）
inti;
for（i=1;
if（u==G.verties[i].data）
returni;
return-1;
intminimum（closem）//返回最小数
inti=0,j,n=200;
if（m[i].lowcost<
n&
&
m[i].lowcost!
=0）
{
n=m[i].lowcost;
j=i;
}
returnj;
voidMinSpanTree_PRIM（ALGraphG,charu）
intj,k,a;
closeclosedge;
ArcNode*s,*p,*q;
for（j=1;
j<
=MAX_VERTEX_NUM;
j++）
closedge[j].lowcost=MAX;
//把所有值都赋为最大
k=LocateVek（G,u）;
if（j!
=k）
closedge[j].adjvex=u;
for（s=G.verties[k].firstarc;
if（j==s->
adjvex）
{closedge[j].lowcost=s->
info;
break;
}
closedge[k].lowcost=0;
cout<
最小生成树:
{"
//查找并输出最小生成树
for（j=1;
G.vexnum;
k=minimum（closedge）;
（"
closedge[k].adjvex<
"
<
G.verties[k].data<
）"
closedge[k].lowcost=0;
for（inti=1;
{
for（p=G.verties[k].firstarc;
p!
p=p->
if（p->
closedge[i].lowcost&
i==p->
{
closedge[i].adjvex=G.verties[k].data;
closedge[i].lowcost=p->
}
}cout<
}"
边及对应权值:
//输出边及对应权值
for（j=G.vexnum;
j>
=1;
j--）
if（closedge[j].lowcost==0&
G.verties[j].data!
=u）
{cout<
closedge[j].adjvex
G.verties[j].data
）=="
a=closedge[j].adjvex;
for（q=G.verties[j].firstarc;
q!
q=q->
if（a-64==q->
cout<
q->
}
G）
inti,j,k,x;
chara,b;
ArcNode*s;
输入顶点数（1-20）:
输入边数:
G.arcnum;
输入顶点信息:
cin>
G.verties[i].data;
G.verties[i].firstarc=NULL;
=G.arcnum;
输入相邻两结点和权值"
a>
b;
cin>
x;
j=a-64;
k=b-64;
//将字符型转化成整数型
s=newArcNode;
s->
info=x;
adjvex=k;
nextarc=G.verties[j].firstarc;
G.verties[j].firstarc=s;
adjvex=j;
nextarc=G.verties[k].firstarc;
G.verties[k].firstarc=s;
二、最短路径
fstream>
cstdlib>
conio.h>
enumMark{UNVISITED,VISITED};
typedefstructDocuNode
intn;
Markm;
}DocuNode;
typedefstructDocu
DocuNode*Node;
int**edge;
}Docu;
MarkgetMark（Docu*D,inti）
returnD->
Node[i].m;
voidsetMark（Docu*D,intv,Markm）
D->
Node[v].m=m;
intfirst（Docu*D,intv）
for（i=0;
i<
D->
n;
i++）
if（（D->
edge[v][i]）!
=-1）
returni;
intnext（Docu*D,intv,intw）
for（i=w+1;
intweight（Docu*D,intv,intw）
edge[v][w];
intminVertex（Docu*D,int*B）
inti,v;
for（i=0;
n;
if（getMark（D,i）==UNVISITED）
v=i;
break;
for（i++;
if（getMark（D,i）==UNVISITED&
（（（（B[i]<
B[v]）&
B[i]!
=-1）||（B[v]==-1））））
returnv;
voidDijkstra（Docu*D,int*B,ints）
inti,v,w;
v=minVertex（D,B）;
if（B[v]==-1）return;
setMark（D,v,VISITED）;
for（w=first（D,v）;
w<
w=next（D,v,w））
if（（B[w]>
（B[v]+weight（D,v,w）））||（B[w]==-1））
B[w]=B[v]+weight（D,v,w）;
Docu*D;
ifstreamfin（"
Docu.txt"
inti,j;
D=（Docu*）malloc（sizeof（Docu））;
fin>
//从文件中读取节点数
Node=（DocuNode*）malloc（sizeof（DocuNode））;
Node[i].m=UNVISITED;
//将所有节点设为未被访问的
edge=（int**）calloc（1,sizeof（int*）*D->
n）;
if（!
edge）//若内存未分配成功
error"
edge[i]=（int*）calloc（1,sizeof（int）*D->
edge[i]）//若内存未分配成功
for（j=0;
j<
j++）
edge[i][j];
//从文件中读取边权值
intstart,end;
起点:
start;
终点:
end;
int*B;
B=（int*）malloc（D->
n*sizeof（int））;
B[i]=D->
edge[start][i];
Dijkstra（D,B,start）;
B[end];
getch（）;
升级会员 