void SpnTree (AdjList g)
//用“破圈法”求解带权连通无向图的一棵最小代价生成树。 {
typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数 node edge[];
scanf( \输入边数和顶点数。 for (i=1;i<=e;i++) //输入e条边：顶点，权值。
scanf(\
for (i=2;i<=e;i++) //按边上的权值大小，对边进行逆序排序。 {edge[0]=edge[i]; j=i-1;
while (edge[j].w k=1; eg=e; while (eg>=n) //破圈，直到边数e=n-1. {if (connect(k)) //删除第k条边若仍连通。 {edge[k].w=0; eg--; }//测试下一条边edge[k]，权值置0表示该边被删除 k++; //下条边 }//while }//算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现，若是连通图，一次进入dfs或bfs就可遍历完全部结点，否则，因为删除该边而使原连通图成为两个连通分量时，该边不应删除。前面第17,18题就是测连通分量个数的算法，请参考。“破圈”结束后，可输出edge中w不为０的n-1条边。 18．已知个n顶点的有向图，用邻接矩阵表示，编写函数计算每对顶点的最短路径。 参考答案： 本题用FLOYD算法直接求解如下： void ShortPath_FLOYD(AdjMatrix g) //求具有n个顶点的有向图每对顶点间的最短路径 {AdjMatrix length; //length[i][j]存放顶点vi到vj的最短路径长度。 for (i=1;i<=n;i++) for (j=1;j<=n;j++) length[i][j]=g[i][j]; //初始化。 for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (length[i][k]+length[k][j] length[i][j]=length[i][k]+length[k][j]; } 19．欲用四种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色（点相交不算相邻）。（1）试用一种数据结构表示地图上各国相邻的关系；（2）描述涂色过程的算法。 参考答案： 地图涂色问题可以用“四染色“定理。将地图上的国家编号（1到n），从编号1开始逐一涂色，对每个区域用1色，2色，3色，4色（下称“色数”）依次试探，若当前所取颜色与周围已涂色区域不重色，则将该区域颜色进栈；否则，用下一颜色。若1至4色均与相邻某区域重色，则需退栈回溯,修改栈顶区域的颜色。用邻接矩阵数据结构C[n][n]描叙地图上国家间的关系。n个国家用n阶方阵表示，若第i个国家与第j个国家 相邻，则Cij=1，否则Cij=0。用栈s记录染色结果，栈的下标值为区域号，元素值是色数。 void MapColor(AdjMatrix C) //以邻接矩阵C表示的n个国家的地区涂色 { int s[]; //栈的下标是国家编号，内容是色数 s[1]=1; //编号01的国家涂1色 i=2;j=1; //i为国家号，j为涂色号 while (i<=n) { while (j<=4 && i<=n) { k=1; //k指已涂色区域号 while (k //与相邻区不重色，涂色结果进栈，继续对下一区涂色进行试探 }//while (j<=4 && i<=n) if (j>4) {i--; j=s[i]+1;} //变更栈顶区域的颜色。 }//while(i<=n) }//结束MapColor 20．设有向图Ｇ以邻接表形式存储，试基于图的深度优先遍历方法设计一算法，用以判定图中是否存在从顶点vi到顶点vj的路径（i≠j）。 参考答案： 从顶点vi出发进行深度优先遍历，调用完成时所有与vi有路径相通的顶点都被访问到。 Boolean Path(ALGraph G,int i,int j){ //若有向图G中从顶点vi到顶点vj有路径相通，则返回TRUE，否则返回FALSE for(k=0;k if (visited[j]) return TRUE; else return FALSE; }//Path void DFS(ALGraph G,int i){//从顶点vi出发对图Ｇ进行深度优先遍历 visited[i]=TRUE; for(p=G.vertices[i].firstarc;p;p=p->next) //从顶点vi的未被访问的邻接点出发深度优先遍历图Ｇ if (!visited[p->adj]) DFS(G,p->adj); }//DFS 21．设有向图Ｇ以邻接表形式存储，试基于图的广度优先遍历方法设计一算法，用以判定图中是否存在从顶点vi到顶点vj的路径（i≠j）。 参考答案： int exist_path_BFS(ALGraph G,int i,int j){ int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i); while(!QueueEmpty(Q)) { DeQueue(Q,u); visited[u]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(k==j) return 1; if(!visited[k]) EnQueue(Q,k); }//for }//while return 0; }//exist_path_BFS 22．试无向图采用邻接表存储结构，试设计算法，判定图中任意给定的两个顶点间是否存在一条长为k的简单路径。 参考答案： 设要判定结点i和结点j间是否存在长为k的简单路径，则只需判定结点i的邻接点l和结点j间是否存在长为k-1的简单路径。 int visited[MAXSIZE]; int exist_path_len(ALGraph G,int i,int j,int k){ if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else return 0; //没找到 }//exist_path_len 23．已知有向图G中两个顶点u和v，试编写算法求图中从u到v的所有简单路径。 参考答案： int path[MAXSIZE],visited[MAXSIZE]; //暂存遍历过程中的路径 int Find_All_Path(ALGraph G,int u,int v,int k) { //初次调用时传入的参数应为G,u,v,0 path[k]=u; //加入当前路径中 visited[u]=1; if(u==v) { //找到了一条简单路径 printf(\ for(i=0;path[i];i++) printf(\ //打印输出 } else for(p=G.vertices[u].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) Find_All_Path(G,l,v,k+1); //继续寻找 } visited[u]=0; path[k]=0; //回溯 }//Find_All_Path