《图的最小生成树和最短路径》由会员分享，可在线阅读，更多相关《图的最小生成树和最短路径（10页珍藏版）》请在金锄头文库上搜索。
1、采用图的邻接矩阵方式查找图的最小生成树和最短路径的完整程序代码：#include #include #include #include #include #include #include #include #include using namespace std;#define MAXNUM 26#define MAXVALUE 32767/矩?阵领接图?的?定义?typedef structchar VertexMAXNUM; /vertexint EdgesMAXNUMMAXNUM; /edgeint IstraveMAXNUM; /flagint Vertex_num; /number
2、 of vertexint Edges_num; /number of edgesint Glaphtype; /0:no direction; 1:directionMaxtrixgraph;/创建矩?阵领接矩?阵void Creatmatrixgraph(Maxtrixgraph *G)int i,j,k,weight;char start,end;coutplease input the all vertex information:endl;for(i=0;iVertex_num;i+)coutthe i+1G-Vertexi;coutendlplease input the edge
3、s and value:endl;for(k=0;kEdges_num;k+)coutthe k+1startendweight;i=0;j=0;while(G-Vertexi != start)i+;while(G-Vertexj != end)j+;G-Edgesij = weight;if(G-Glaphtype = 0)G-Edgesji = weight;/输?出?邻接矩?阵void Outmatrix(Maxtrixgraph *G)int i,j;coutThe vertex is follow:endl;for(j=0;jVertex_num;j+)cout Vertexj;c
4、outendlThe edges matrix is follow:endl;for(i=0;iVertex_num;i+)coutVertexi;for(j=0;jVertex_num;j+)if(G-Edgesij = MAXVALUE)cout #;elsecout Edgesij;coutendl;/下?面?介绍图?的?邻接表创建方?法typedef struct edgenodeint Vertex; /vertex numberint weight; /quanstruct edgenode *next; /the next edgenodeEdgeNode;/图?的?邻接链表定义
5、?typedef structEdgeNode* AdjlistMAXNUM;int vertex_num;int edge_num;int Graphtype;ListGraph;/生成图?的?邻接表void Creatgraph(ListGraph *G)int i,weight,start,end;EdgeNode *s;for(i=0;ivertex_num;i+) /clear the node pointerG-Adjlisti=NULL;for(i=0;iedge_num;i+) /input the 2 node of each edge and weightcoutthe i
6、+1startendweight;s=(EdgeNode *)malloc(sizeof(EdgeNode);s-next=G-Adjliststart;s-Vertex=end;s-weight=weight;G-Adjliststart=s;if(G-Graphtype = 0)s=(EdgeNode *)malloc(sizeof(EdgeNode);s-next=G-Adjlistend;s-Vertex=start;s-weight=weight;G-Adjlistend=s;/输?出?邻接表void OutList(ListGraph *G)int i;EdgeNode *s;fo
7、r(i=0;ivertex_num;i+)coutVertex:iAdjlisti;while(s)coutVertex(weightnext;couthead=0;Q-tail=0;int Queuepush(Sequeue *Q,int ch)if(Q-tail + 1)%MAXNUM = Q-head)return 0;Q-DataQ-tail=ch;Q-tail=(Q-tail+1)%MAXNUM;return 1;int Queuepop(Sequeue *Q,int *ch)if(Q-head =Q-tail)return 0;*ch=Q-DataQ-head;Q-head=(Q-
8、head +1)%MAXNUM;return 1;int QueueIsempty(Sequeue *Q)if(Q-head = Q-tail)return 1;elsereturn 0;/广?度优?先遍历函数yvoid BFSM(Maxtrixgraph *G,int k)/start from vertex kint i,j;Sequeue Q;Queueinit(&Q);G-Istravek=1;coutVertexk;Queuepush(&Q,k);while(! QueueIsempty(&Q)Queuepop(&Q,&i);for(j=0;jVertex_num;j+)if(G-E
9、dgesij!=MAXVALUE & !G-Istravej)coutVertexj;G-Istravej=1;Queuepush(&Q,j);/广?度优?先搜?索算?法的?测a试?程序void BFSTraverse(Maxtrixgraph *G)for(int i=0;iVertex_num;i+)G-Istravei=0;cout广?度优?先遍历节点?：oendl;for(int i=0;iVertex_num;i+)if(! G-Istravei)BFSM(G,i);coutIstravei=1;coutVertexi;for(int j=0;jVertex_num;j+)if(G-
10、Edgesij!=MAXVALUE & !G-Istravej)DFSM(G,j);/图?的?深?度优?先搜?索遍历的?测a试?程序void DFSTraverse(Maxtrixgraph *G)for(int i=0;iVertex_num;i+)G-Istravei=0;cout深?度优?先遍历节点?：oendl;for(int i=0;iVertex_num;i+)if(!G-Istravei)DFSM(G,i);coutendl;/图?的?最?小?生成树程序void Smalltree(Maxtrixgraph G)int i,j,k,min,sum=0;int weightMAXNUM;char tmpvertexMAXNUM;tmpvertex0=0;weight0=MAXVALUE;for(i=
