图的所有演示程序

《图的所有演示程序》由会员分享，可在线阅读，更多相关《图的所有演示程序（19页珍藏版）》请在金锄头文库上搜索。

1、图的所有演示程序图的所有演示程序#include #include #include #define MaxVertexNum 20 /最大顶点数设为 20 #define MAXCOST 32767typedef int VertexType; /顶点类型设为字符型 typedef int EdgeType; /边的权值设为整型 typedef struct VertexType vexsMaxVertexNum; /顶点表EdgeType edgesMaxVertexNumMaxVertexNum; /邻接矩阵 int n,e; /图中顶点数和边数MGraph; /邻接矩阵存储的图类型*/

2、typedef struct EdgeNode /图的结点的结构 int adjvex; /邻接点域 struct EdgeNode * next; /指向下一个邻接点的指针域 int w; /info 表示边或弧的信息 EdgeNode; typedef struct /表头（指针数组）分量的信息 VertexType vertex; /顶点信息 int degree;EdgeNode * firstedge; /边表头指针 VertexNode; typedef VertexNode AdjListMaxVertexNum;typedef struct /图的邻接表 AdjList adj

3、list; int n,e; /顶点数和边数 ALGraph;/*int visitedMaxVertexNum;void createmgraph(MGraph *printf(“请输入顶点数和边数（输入格式为：顶点数，边数）：n“);scanf(“%d,%d“,printf(“请输入顶点信息（输入格式为：顶点号）n“);for(i=0;in;i+)scanf(“%d“,for(i=0;in;i+)for(j=0;jn;j+)G-edgesij=MAXCOST;if(i=j) G-edgesij=0;printf(“请输入有向图（1） ，无向图（0）的信息:n“);scanf(“%d“,pr

4、intf(“请输入每条对边的两个顶点的序号及其权值（输入格式为：i,j,weight）:n“);for(k=0;ke;k+)scanf(“%d,%d,%d“,G-edgesij=weight;if(w!=1) G-edgesji=weight; */void createALGraph(ALGraph *EdgeNode *s;int tag;printf(“请输入有向图（1）或无向图（0）: “);scanf(“%d“,printf(“请输入顶点数和边数（输入格式为：顶点数，边数）：n“);scanf(“%d,%d“,G-n=tn;G-e=te;printf(“请输入顶点信息（顶点信息从 0

5、 开始。输入格式为：顶点号）n“);for(i=0;in;i+) /对表头指针数组进行初始化操作scanf(“%d“,G-adjlisti.firstedge=NULL; /对指向第一条边的指针置NULLfor(i=0;in;i+) G-adjlisti.degree=0;printf(“请输入边的信息（输入格式为,若不带权，则 w=0）：i,j,wn“);for(k=0;ke;k+)scanf(“%d,%d,%d“, /读入与该边关联的两个顶点s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=j; /表首添加法构建链表，将边加入到第 i 个链表 s-

6、w=w;s-next=G-adjlisti.firstedge;G-adjlisti.firstedge=s;G-adjlistj.degree+;if(tag=0) /若是无向图，还要将此边加入到第 j 个链表 s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=i;s-w=w;s-next=G-adjlistj.firstedge;G-adjlistj.firstedge=s;/建立图的邻接表存储结构结束 /*void DFSAL(ALGraph *G,int i) /遍历图从第 i 个顶点开始EdgeNode *p;printf(“V%d “,G-

7、adjlisti.vertex);visitedi=1; p=G-adjlisti.firstedge;while(p)if(!visitedp-adjvex)DFSAL(G,p-adjvex); p=p-next;void DFSTraverseAL(ALGraph *G)int i;for(i=0;in;i+)visitedi=0;for(i=0;in;i+)if(!visitedi) DFSAL(G,i);/以邻接表作为图的存储结构的广度优先搜索遍历算法如下：typedef struct /类似于二叉树的按层次遍历int dataMaxVertexNum;int rear,front;

8、sqqueue; /队列的存储结构 void BFS(ALGraph *G, int vi) /从 vi 出发进行广度优先搜索遍历 sqqueue Q; int v; EdgeNode *p;Q.front=0;Q.rear=0; /队初始化 visitedvi=1; /标记 vi 已访问 printf(“V%d “,vi); /访问初始顶点 Q.dataQ.rear+=vi; /初始顶点入队 while (Q.front!=Q.rear) /队列不为空 v=Q.dataQ.front; /按访问次序依次出队列 Q.front=(Q.front+1) % MaxVertexNum; /循环队列

9、，修改队头指针 p=G-adjlistv.firstedge; /找 v 的邻接点 while (p)if (visitedp-adjvex=0)visitedp-adjvex=1;printf(“V%d “,p-adjvex);Q.dataQ.rear=p-adjvex; /进队，修改队尾指针Q.rear=(Q.rear+1) % MaxVertexNum; p=p-next; /找 v 的下一个邻接点 void BFSAL(ALGraph *G)int i;for(i=0;in;i+)visitedi=0;for(i=0;in;i+)if(visitedi=0) BFS (G,i); vo

10、id prim(MGraph *G, int v) struct int adjvex; /该边依附于集合 U 中的顶点 int lowcost; /该边的权值 EdgeType edgesMaxVertexNumMaxVertexNum; closedgeMaxVertexNum;int i,j,k,min;for (i=0;in;i+) /对辅助数组初始化 closedgei.lowcost=G-edgesvi; /赋矩阵的第 v 行 i列的值 closedgei.adjvex=v; /赋顶点 i 相关联的顶点 vclosedgev.lowcost=0;for (i=1;in;i+) /从

11、 U 之外求离 U 中某一顶点最近的顶点 min=MAXCOST; / MAXCOST 为允许的最大权值 for(j=0;jn;j+)if (closedgej.lowcost!=0 printf(“n“);printf(“(%d,%d,%d) n“, G-vexsclosedgek.adjvex, G-vexsk, min);/输出相应的顶点与权值，G.vexs 为顶点表 closedgek.lowcost=0; /k 加入到 U 中后，对应的权值为 0 for (j=0;jn;j+) /对数组的分量值进行调整，更新 V-U 集合中顶点的 closedge 值 if (closedgej.l

12、owcost!=0 closedgej.adjvex=k; printf(“n“);typedef struct int v1,v2;int cost; EdgeType1; EdgeType1 edgesMaxVertexNum;void Kruskal(EdgeType1 edges,int n) int vsetMaxVertexNum;int i,j,k,vf1,vf2;for (i=0;in;i+) /初始化集合 T 中各顶点的路径值 finali=0; /初始化，顶点在 T 集合中 disti.length=G-edgesvi;if (disti.lengthn;i+) /其余 G

13、-n-1 个顶点依次加入 T min=MAXCOST; k=-1; /MAXCOST 为允许的最大权值 for(j=0;jn;j+) /找 T 集合中当前路径长度最小的顶点 if (!finalj)j+) /调整 T 集合中顶点的最短路径及距离 if (!finalj)if (G-edgeskjedgeskjedgeskj; distj.pre=k; /调整顶点 j 到源点的路径else break; /T 中不再有从源点可达的顶点 for(i=0;in;i+) /借助栈输出从源点到其余各顶点的最短路径 / if(i!=v s.top=-1; s.data+s.top=i; j=disti.pre;while(j!=-1) s.data+s.top=j; j=distj.pre; /将其前驱顶点依次置入栈中printf(“ 路径上的顶点： “);while(s.top!=-1) printf(“%4d “,G-vexss.datas.top-); /输出路径中各顶点 printf(“n“);/ /采用邻接矩阵存储时，求任意两顶点间的最短路径的弗洛伊德算法如下：void ppath(MGraph *G ,int path