图的深度遍历和广度遍历以及最小生成树.docx

/本程序主要包含以下功能/采用邻接矩阵构造图/图的深度遍历和广度遍历/采用普里姆算法和克鲁斯卡尔算法构造最小生成树#include#include #define INFINITY 999#define MAX_VERTEX_NUM 20#define OK 1#define ERROR -1typedef char VertexType;typedef char InfoType;typedef VertexType QElemType;bool visitedMAX_VERTEX_NUM;/ 访问标志数组 typedef struct /*辅助数组*/ VertexType adjvex; int lowcost;closedgeMAX_VERTEX_NUM;typedef struct int begin;int end;int flag;int weight;edge; edge edges50;typedef struct ArcCellint adj;InfoType *info;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum; MGraph;typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;int InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) return ERROR;Q.front-next=NULL;return OK;int DestroyQueue(LinkQueue &Q)while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;/DestroyQueueint EnQueue(LinkQueue &Q,QElemType e)QueuePtr p; /p=(QueuePtr)malloc(sizeof(QNode);if(!p) return ERROR;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;int DeQueue(LinkQueue &Q,QElemType &e)if(Q.front=Q.rear) return ERROR;QueuePtr p;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK;int QueueEmpty(LinkQueue Q)if(Q.rear=Q.front) return 1;else return 0; int LocateVex(MGraph G,VertexType u)int i;for(i = 0; i =0 & kG.vexnum) /k合理 for(int i=0;i=0 & i=0 & jG.vexnum) /i,j合理 for(int k=j+1;kG.vexnum;k+) if(G.arcsik.adj!=INFINITY) return k; return -1; int CreateUDN(MGraph &G) / 算法 7.2 / 采用数组（邻接矩阵）表示法，构造无向网G。 int i,j,k,w,p=0; VertexType v1,v2; printf(G.vexnum : ); scanf(%d,&G.vexnum); printf(G.arcnum :); scanf(%d,&G.arcnum); getchar(); /* 加上此句getchar()! */ / scanf(%d,%d,%d,&G.vexnum, &G.arcnum, &IncInfo); for (i=0; iG.vexnum; i+ ) printf(G.vexs%d : ,i); scanf(%c,&G.vexsi); getchar(); / 构造顶点向量 for (i=0; iG.vexnum; +i ) / 初始化邻接矩阵 for (j=0; jG.vexnum; +j ) G.arcsij.adj = INFINITY; /adj,info G.= NULL; for (k=0; kG.arcnum; +k ) / 构造邻接矩阵 printf(v1 (char) : ); scanf(%c, &v1);getchar(); printf(v2 (char) : ); scanf(%c, &v2);getchar(); printf(w (int) : ); scanf(%d, &w); getchar(); / 输入一条边依附的顶点及权值 i = LocateVex(G, v1); j = LocateVex(G, v2); / 确定v1和v2在G中位置 G.arcsij.adj = w; / 弧的权值 / if (IncInfo) scanf(G.); / 输入弧含有相关信息 G.arcsji.adj = G.arcsij.adj; / 置的对称弧 edgesp.begin=i; edgesp.end=j; edgesp.weight=G.arcsij.adj; edgesp.flag=0; p+; printf(图的邻接矩阵为：n); for ( i = 0; i G.vexnum; i+)for ( j = 0; j G.vexnum; j+) printf(%4d ,G.arcsij.adj); printf(n); return OK; / CreateUDNvoid DFS(MGraph G, int v) / 从第v个顶点出发递归地深度优先遍历图G。 int w; visitedv = true; printf(%c ,G.vexsv);/ 访问第i个顶点 for (w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G, v, w) if (!visitedw) / 对v的尚未访问的邻接顶点w递归调用DFS DFS(G, w);void DFSTraverse(MGraph G) / 对图G作深度优先遍历。 int v; for (v=0; vG.vexnum; +v) visitedv = false; / 访问标志数组初始化 for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFSvoid BFSTraverse(MGraph G ) / 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。 QElemType v,w; LinkQueue Q; QElemType u; for (v=0; vG.vexnum; +v) visitedv = false; InitQueue(Q); / 置空的辅助队列Q for (v=0; v=0; w=NextAdjVex(G, u, w) if (!visitedw) / u的尚未访问的邻接顶点w入队列Q visitedw = true; printf(%c ,G.vexsw); EnQueue(Q, w); /if /while /if / BFSTraverseint minimum(closedge SZ,MGraph G)int i=0,j,k,min;while(!SZi.lowcost)i+;min=SZi.lowcost; / 第一个不为0的值 k=i;for(j=i+1;j0)if(minSZj.lowcost)min=SZj.lowcost;k=j;return k; /=普里姆算法=void MiniSpanTree_PRIM(MGraph G, VertexType u) / 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。 / 记录从顶点集U到VU的代价最小的边的辅助数组定义： / struct / VertexType adjvex; / VRType lowcost; / closedgeMAX_VERTEX_NUM;printf(普里姆算法最小生成树为：); int i,j,k; closedge closedge; k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 辅助数组初始化 if (j!=k) closedgej.adjvex=u; closedgej.lowcost=G.arcskj.adj; closedgek.lowcost = 0; / 初始，Uu printf(n); for (i=1; i0, viV-U printf( %dn,closedgek.adjvex, G.vexsk,G.arcsLocateVex( G,closedgek.adjvex )k.adj); / 输出生成树的边 closedgek.lowcost = 0; / 第k顶点并入U集 for (j=0; jG.vexnum; +j) if (G.arcskj.adj closedgej.lowcost) / 新顶点并入U后重新选择最小边 / closedgej = G.vexsk, G.arcskj.adj ; closedgej.adjvex=G.vexsk; closedgej.lowcost=G.arcskj.adj; / MiniSpanTree/=克鲁斯卡尔算=void Swapn(edge *edges,int i, int j) int temp; temp = edgesi.begin; edgesi.begin = edgesj.begin; edgesj.begin = temp; temp = edgesi.end; edgesi.end = edgesj.end; edgesj.end = temp; temp = edgesi.weight; edgesi.weight = edgesj.weight; edgesj.weight = temp; void sort(edge edges,MGraph G)/对权值进行排序 int i, j;for ( i = 0; i G.arcnum; i+)for ( j = i + 1; j edgesj.weight)Swapn(edges, i, j);printf(按造价排序之后的边顺序为(序号 边 代价):n);for (i = 0; i G.arcnum; i+)printf(%d. %dn, i,G.vexsedgesi.begin, G.vexsedgesi.end, edgesi.weight);int Find(int *parent, int f)while ( parentf 0)f = parentf;return f;void MiniSpanTree_KRUSKAL(MGraph G)/生成最小生成树 int i, j, n, m,Mincost=0; int parent100; sort(edges, G);for (i = 0; i G.arcnum; i+)parenti = 0;printf(克鲁斯卡尔算法最小生成树为:n);for (i = 0; i G.arcnum; i+) n = Find(parent, edgesi.begin);m = Find(parent, edgesi.end);if (n != m)parentn = m;printf( %dn,G.vexs edgesi.begin,G.vexs edgesi.end, edgesi.weight);Mincost+=edgesi.weight;printf(使各个顶点连通的最小代价为：Minc