//
// 图.cpp : Defines the entry point for the console application.
//
#include"stdafx.h"
#include #include #include #include #define MaxVerNum 30 /* 最大顶点数为100 */ typedef struct node { /* 表结点表示边或者弧 */ int adjvex; /* 邻接点,一般是顶点的序号或在表头向量中的下标 */ int Info; /*与边(或弧)相关的信息*/ struct node * next; /* 指向下一个邻接点的指针域 */ }EdgeNode; typedef struct vnode { /* 顶点结点 */ int vertex; /* 顶点域 */ EdgeNode * firstedge; /* 边表头指针 */ }VertexNode; typedef struct { VertexNode adjlist[MaxVerNum]; /* 邻接表 */ int n,e; /* 顶点数和边数 */ }ALGraph; /* ALGraph是以邻接表方式存储的图类型 */ ////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////邻接表结构定义 void CreateALGraph(ALGraph *G)/* 建立图的邻接表存储 */ { int i,j,k,a,b,c; EdgeNode * p; cout<<"请输入图的顶点数和边数。"< G->n=a; G->e=b; for(i=0;i { cout<<"请输入第"< G->adjlist[i].vertex=c; G->adjlist[i].firstedge=NULL; } for(k=0;k { cout<<"请输入第"< p=(EdgeNode*)malloc(sizeof(EdgeNode ) ) ; p->adjvex=j; /* 邻接点序号为j */ /* 将新边表结点p插入到顶点Vi的链表头部 */ p->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=p; } } /*CreateALGraph*/ /////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////图的邻接表创建 void DestroyALGraph(ALGraph *G)/* 销毁图的邻接表存储 */ { int i=0,k; EdgeNode * p,*q; for(k=0;k { p=G->adjlist[i].firstedge; while (p) /* 销毁第i个顶点的边表 */ { q=p; p=p->next; free(q); } G->adjlist[i].firstedge=NULL; } } ////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////图的邻接表销毁 #define false 0 #define true 1 int visited[MaxVerNum]; void Visit(ALGraph G,int v) { cout< int NextAdjVertex (ALGraph G, int v, in t w) /* 求图G的第v个顶点的邻接点w的下一个邻接点 （邻接表表示图） */ { EdgeNode *p; p=G.adjlist[v].firstedge; while (p && p-> adjvex != w ) p=p->next; //找第v 结点 if(p==NULL || p->next==NULL) return -1; //找不到第v 结点或第v 结点无后继 else return (p->next->adjvex); } int FirstAdjVertex(ALGraph G,int v) /* 求图G的第一个邻接点（邻接表表示图） */ { if(G.adjlist[v].firstedge!=NULL) return (G.adjlist[v].firstedge->adjvex); else return -1; //无第一个邻接点 } void DFS(ALGraph G,int v) /* 从第v个顶点出发深度优先遍历图G */ { int w; Visit(G,v); /* 访问第v个顶点 */ visited[v]=true; /* 把 v 顶点置True表访问过 */ for(w=FirstAdjVertex (G,v);w!=-1;w=NextAdjVertex (G,v,w) ) if (!visited[w]) DFS(G,w);/* 对v尚未访问的邻接顶点w递归调用DFS */ } void DFStraverse(ALGraph G) /*深度优先遍历图G*/ { int v; for(v=0;v //cout<<"请输入从第几个顶点出发深度优先遍历图。"< for(v=0;v DFS(G,v); }/*DFS*/ /////////////////////////////////////////////图的深度优先遍历 ////////////////////////////////////////////////////////////// #define MAX 100 typedef struct{ int data[MAX]; int front,rear; }SeqQueue,*PSeqQueue; PSeqQueue Init_SeqQueue() { PSeqQueue Q; Q=(PSeqQueue)malloc(sizeof(SeqQueue)); if(Q) { Q->front=0; Q->rear=0; } return Q; } void Destroy_SeqQueue(PSeqQueue *Q) { if(*Q) free(*Q); *Q=NULL; } int Empty_SeqQueue(PSeqQueue Q) { if(Q&&Q->front==Q->rear) return(1); else return(0); } int In_SeqQueue(PSeqQueue Q,int x) { if((Q->rear+1)%MAX==Q->front) { return 0; } else { Q->rear=(Q->rear+1)%MAX; Q->data[Q->rear]=x; return 1; } } int Out_SeqQueue(PSeqQueue Q,int *x) { if (Empty_SeqQueue(Q)) { return 0; } else { Q->front=(Q->front+1)%MAX; *x=Q->data[Q->front]; return 1; } } void BFS(ALGraph G, int v) {/* 从v0点开始，按广度优先遍历图G*/ int u,w; PSeqQueue Q; Q=Init_SeqQueue( ); Visit(G,v); visited[v]=true; In_SeqQueue(Q, v); /* 起始点入队列 */ while(!Empty_SeqQueue(Q)) { Out_SeqQueue(Q,&u); /* 出队列 v 顶点*/ for(w=FirstAdjVertex(G,v);w!=-1;w=NextAdjVertex(G,v,w)) { if(!visited[w]) { Visit(G,w); visited[w]=true;/* 访问w */ In_SeqQueue(Q,w); /* 访问过的w入队列 */ } }//搜索顶点v 的所有邻接点 } Destroy_SeqQueue(&Q); } void BFStraverse(ALGraph G) { /* 广度优先遍历图G的所有顶点 */ int v; for(v=0;v //cout<<"请输入从第几个顶点出发广度优先遍历图。"< for(v=0;v } ///////////////////////////////////////////////////图的广度优先遍历 ////////////////////////////////////////////////////////////////// /*#define MAXCOST 100 void Prim (int gm[ ][MaxVerNum],int n,int closevertex[ ]) { int lowcost[100],mincost; int i,j,k; for (i=1;i lowcost[i]=gm[0][i]; closevertex[i]=0; }//从顶点v0开始构造最小生成树 lowcost[0]=0; /* 从序号为0的顶点出发生成最小生成树 */ /*closevertex[0]=0;//保存最小生成树 for(i=1;i mincost=MAXCOST; j=1;k=1; while (j mincost=lowcost[j]; k=j; } j++; } printf("(%d,%d,%d)\ >vexnum-1 && j { int s1,s2; s1=f [ G->edgelist[j].vex1]; s2=f [ G->edgelist[j].vex2]; /*判断顶点s1,s2是否在一个连通分量内,不是产生一条最小边*/ if (s1!= s2) { TE[k].vex1= G->edgelist[j].vex1; TE[k].vex2= G->edgelist[j].vex2;//加入一条边 TE[k].weight= G->edgelist[j].weight; cout< for(i=0;i if (f[i]==s2) f[i]=s1;/*修改连通的编号*/ } j++; } } ///////////////////////////////////图的最小生成树Kruskal算法 //////////////////////////////////////////////////////////// #define INFINITY 30000 typedef struct { int vertexs[MaxVerNum]; /* 顶点表 */ int arcs[MaxVerNum][MaxVerNum];/* 邻接矩阵，即边表 */ int n,e; /* 顶点数和边数 */ } MGraph;/* MGragh是以邻接矩阵存储的图 */ /*void ShortestPath_1(MGraph *G,int v0,int P[ ][MaxVerNum], int D[]) { /*P[v ]表示路径， P[v ][i]=1表示到v0到v点的路径经过i顶点； D[v]表示到达v点的路径长度 */ /*int a,b,c,s,i,j,v,w,min; cout<<"请输入顶点个数和边个数。"< G->n=a; G->e=b; for(i=0;i { cout<<"请输入第"< G->vexs[i]=c; } for(i=0;i for(j=0;j if(i=j) G->edges[i][j]=0; else G->edges[i][j]=INFINITY; for(s=0;s { cout<<"请输入边的信息，即边的源点、终点、权值。"< G->edges[i][j]=w; } bool final[MaxVerNum]; // 标记已经求出的顶点 for(v=0;v { final[v]=False; D[v]=G->edges[v0][v]; for(w=0; w if (D[v] P[v][v0]=1; P[v][v]=1; } //初始化 D[v0]=0; final[v0]=True; /*开始，v0顶点属于S集*/ /*for(i=1; i /*{ min=INFINITY; for (w=0;w if (!final[w]&& D[w] v=w; min=D[w]; } final[v]=True; for(w=0;w>G->n;++w) /*更新当前最短路径*/ /* if (!final[w]&&(min+G->edges[v][w] D[w]=min+G->edges[v][w]; cout< P[w][w]=1; } } } }/*ShortestPath_1*/ // O(n2) void ShortestPath_Dij(MGraph *G,int v0,int p[],int d[]) //用于有向图 { /*起始点v0到其它点的最短路径 p[v]表示v的前驱顶点 d[v]表示v0到顶点v的 最短带 权路径长度 final[v]为1则表明已找到从v0到v的最短路径*/ int a,b,c,s,i,j,v,w,min; cout<<"请输入顶点个数和边个数。"< G->n=a; G->e=b; for(i=0;i { cout<<"请输入第"< G->vertexs[i]=c; } for(i=0;i for(j=0;j { if(i==j) G->arcs[i][j]=0; else G->arcs[i][j]=INFINITY; } for(s=0;s { cout<<"请输入边的信息，即边的源点、终点、权值。"< G->arcs[i][j]=w; } int final[MaxVerNum]; for(v=0;v<=G->n-1;v++) //初始化每个顶点与v0 { if(v==0) p[v]=-1;/////////////////////////////修改点 else{ final[v]=false; d[v]=G->arcs[v0][v]; p[v]=-1; //初始化，表示无前驱 if(d[v] }//v0到v有弧 ,v的前驱初始值为v0 } d[v0]=0;final[v0]=true; //初始时,v0属于S集 //开始主循环 每次求的v0到某个顶点v的最短路径 并加v到S集 for(i=1;i<=G->n;i++) //寻找其余G.vertexNum-1个顶点 { v=-1; min=INFINITY; for(w=0;w<=G->n-1;w++) if((!final[w])&&(d[w] v=w; //v为找到的最近点的下标 min=d[w]; } if(v==-1) break;//若v=-1表明所有与v0有通路的顶点均已找到了最短路径 退出主循环 final[v]=true; //将v加入S集 for(w=0;w<=G->n-1;w++) //更新当前最短路径及距离 if(!final[w]&&(min+G->arcs[v][w] d[w]=min+G->arcs[v][w]; p[w]=v; //修改w的前驱 } } } //-----------------------------------------------// void Print_DijPath(MGraph *G,int v0,int p[], int d[]) { //显示从顶点v0到其余顶点的最短路径及距离 int v,i; cout<<"The shortest path from "< { if(p[v]==-1) continue; //表明顶点v0到顶点v没有通路 cout< while(p[i]!=-1) { cout< } cout< } int Graph_Operate() { cout<<"--------0:选择退出----------"< cin>>a; ALGraph *h=(ALGraph*)malloc(sizeof(ALGraph)); ELGraph *l=(ELGraph*)malloc(sizeof(ELGraph)); MGraph *k=(MGraph*)malloc(sizeof(MGraph)); while(a) { switch(a){ case '0': return 0; case '1': CreateALGraph(h); cout<<"创建完成!"; break; case '2': DestroyALGraph(h); cout<<"销毁成功!"; break; case '3': DFStraverse(*h); break; case '4': BFStraverse(*h); break; case '5': cout<<"输入用Kruskal算法求最小生成树的 无向图 的信息。"< break; case '6': cout<<"输入用Dijkstra算法求最短路径的 有向图 的信息。"< int d[MaxVerNum]; int p[MaxVerNum]; ShortestPath_Dij(k,v0,p,d); Print_DijPath(k,v0,p,d); break; } cout<<"\ 输入你要继续执行的操作序号(0-6)"< } return 0; } void Show_Main_Menu() { cout<<"---------------------------------"< int main() { Show_Main_Menu(); cout<<"Please input what do you want to operate(g,e)"< cin>>oper; while(oper) { switch(oper) { case 'e': return 0; case 'g': Graph_Operate(); break; } cout<<"输入你要继续执行的操作字符(g,e)"< } return 0; }下载本文
