数据结构实验六图(2)

}

int main(){

vnode adjlist[N]; int n,*p; p=&n;

createGraph_list(adjlist,p); return 0; }

? 根据输入，输出有向图的拓扑排序序列。并画出有向图。输入: ABCDEF# 0,1 1,2 2,3 4,1 4,5 -1,-1 ? 运行结果：

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; 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 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

mindis=INFIN;

for(j=0;j

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)

printf(\无路径\ else{

printf(\

printf(\经过顶点：\

for(j=0;j

printf(\ printf(\ } } }

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算法演示*/ 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 ? 运行结果：（并画出两个图）

三、实验小结

四、教师评语