《数据结构》（C语言版）严蔚敏著 - 数据结构实验指导(7)

3、阅读并运行下面程序。 #include #define N 20 #define TRUE 1

#define INF 32766 /*邻接矩阵中的无穷大元素*/ #define INFIN 32767 /*比无穷大元素大的数*/

typedef struct

{ /*图的邻接矩阵*/

int vexnum,arcnum; char vexs[N]; int arcs[N][N]; }

graph;

void createGraph_w(graph *g,int flag); void prim(graph *g,int u); void dijkstra(graph g,int v); void showprim(); void showdij();

/*建带权图的邻接矩阵,若flag为1则为无向图，flag为0为有向图*/ void createGraph_w(graph *g,int flag) {

int i,j,w; char v;

g->vexnum=0; g->arcnum=0; i=0;

printf(\输入顶点序列(以#结束)：\\n\ while((v=getchar())!='#') {

g->vexs[i]=v; /*读入顶点信息*/ i++; }

g->vexnum=i;

for(i=0;i<6;i++) /*邻接矩阵初始化*/ for(j=0;j<6;j++)

g->arcs[i][j]=INF;

printf(\输入边的信息：\\n\

scanf(\读入边(i,j,w)*/ while(i!=-1) /*读入i为－1时结束*/ {

g->arcs[i][j]=w;

31

if(flag==1)

g->arcs[j][i]=w;

scanf(\ } }

void prim(graph *g,int u)/*出发顶点u*/ {

int lowcost[N],closest[N],i,j,k,min;

for(i=0;ivexnum;i++) /*求其他顶点到出发顶点u的权*/ {

lowcost[i]=g->arcs[u][i]; closest[i]=u; }

lowcost[u]=0;

for(i=1;ivexnum;i++) /*循环求最小生成树中的各条边*/ { min=INFIN;

for(j=0;jvexnum;j++) /*选择得到一条代价最小的边*/ if(lowcost[j]!=0&&lowcost[j]

min=lowcost[j]; k=j; }

printf(\/*输出该边*/

lowcost[k]=0; /*顶点k纳入最小生成树 */

for(j=0;jvexnum;j++) /*求其他顶点到顶点k 的权*/ if(g->arcs[k][j]!=0&&g->arcs[k][j]

lowcost[j]=g->arcs[k][j]; closest[j]=k; } } }

void printPath(graph g,int startVex,int EndVex) {

int stack[N],top=0; /*堆栈*/ int i,k,j;

int flag[N]; /*输出路径顶点标志*/ k=EndVex;

for (i=0;i

32

printf(\ flag[j]=1;

stack[top++]=k;

while (top>0) /*找j到k的路径*/ {

for (i=0;i

if (path[k][i]==1 && flag[i]==0) /*j到k的路径含有i顶点*/ {

if (g.arcs[j][i]!=INF ) /*j到i的路径含有中间顶点*/ {

printf(\ /*输出j到k的路径的顶点i*/ flag[i]=1; j=i;

k=stack[--top]; break; } else {

if (i!=k) stack[top++]=i; /*break;*/ } } } }

void dijkstra(graph g,int v){ /*dijkstra算法求单源最短路径*/ int path[N][N],dist[N],s[N]; int mindis,i,j,u,k;

for(i=0;i

for(j=0;j

dist[v]=0; s[v]=1;

for(i=0,u=1;i

for(j=0;j

33

if(s[j]==0)

if(dist[j]

mindis=dist[j]; } s[u]=1;

for(j=0;j

if((s[j]==0)&&dist[u]+g.arcs[u][j]

printf(\顶点%c->到各顶点的最短路径\\n\ for(i=0;i

printf(\顶点%c->顶点%c：\ if(dist[i]==INF||dist[i]==0) printf(\无路径\ else{

printf(\

printf(\经过顶点：\

printPath(g,v,i); /*输出v到i的路径*/ } } }

void showprim()/*最小生成树prim算法演示*/ {

graph ga;

createGraph_w(&ga,1); prim(&ga,0); }

void showdij(){ /*dijstra算法演示*/ graph ga;

createGraph_w(&ga,0); dijkstra(ga,0); }

int main(){

showprim(); /*prim算法演示*/ getchar();

showdij(); /*dijstra算法演示*/

34

return 0; }

? 下面的输入分别验证prim算法和dijstra算法。输入实例的第一部分为无向图，求

其最小生成树；输入的第二部分为有向图，求其最短路径。 最小生成树 最短路径 ABCDEF# 0,1,6 0,2,1 0,3,5 1,2,5 1,4,3 2,3,5 2,4,6 2,5,4 3,5,2 4,5,6 -1,-1,-1 ? 运行结果：（并画出两个图）

最小生成树

四、实验小结

五、教师评语

ABCDEF# 0,2,10 0,5,100 0,4,30 1,2,5 2,3,50 3,4,20 3,5,10 4,3,20 4,5,60 -1,-1,-1 最短路径 35

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《数据结构》（C语言版）严蔚敏著 - 数据结构实验指导(7)在线全文阅读。