图

#include<stdio.h> #include<string.h> #include<stdlib.h>#define TRUE 1 #define FALSE 0#define ERROR 0 #define OVERFLOW 0#define OK 1 #define INFINITY 65535 //表示无穷大-->在带权的图中用到，即网 #define MAX_VERTEX_NUM 20 //图的最大顶点数#define MAX_INFO 20 //每条弧附带信息最大长度 typedef int Status; typedef int VRType; //顶点关系类型 typedef char InfoType; //附加信息类型 typedef int VertexType; //顶点数据类型 //C语言中枚举中的数据是整型的，默认从0开始依次赋值 typedef enum {DG,DN,UDG,UDN} GraphKind; //图的种类:分别代表有向图，有向网，无向图，无向网 typedef struct { //邻接矩阵 VRType adj; //顶点关系类型，对无权图用1或0表示是否相邻；对带权图，就表示权值，有权值表示有边，没边数值就为INFINITY（无穷大） InfoType *info; //附加信息指针 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //定义一个数组用来存放图中的顶点 AdjMatrix arcs; //邻接矩阵 表示顶点之间的关系（其实就是有没有边） int vexnum; //图的当前顶点数 int arcnum; //图的弧数 GraphKind kind; //图的种类}MGraph; //------------------------返回图G中的 顶点v 在存放顶点的数组中 的位置---------------------------------int LocateVex(MGraph G,VertexType v) { for(int i = 0;i < G.vexnum; i++){ if(G.vexs[i] == v){ return i; } } return -1;}//------------------------创建无向图---------------------------------Status CreateUDG(MGraph &G) { int i,j,k,infoflag,len; char c; //设置一个暂存区和一个临时指针 char str[MAX_INFO]; char *info; VertexType v1,v2; len = 0; //确定顶点数/弧数/弧是否携带信息 printf("请分别输入 顶点数量、边的数量、边是否携带信息（要携带输入1否则输入0）\n"); scanf("%d%d%d",&G.vexnum,&G.arcnum,&infoflag); //确定各个顶点的值 printf("依次输入顶点（用-1表示顶点 V1 依此类推）\n"); for(i = 0;i < G.vexnum ; i++) scanf("%d",&G.vexs[i]); //初始化邻接矩阵 for(i = 0; i < G.vexnum; i++) for(j = 0;j < G.vexnum ; j++) { G.arcs[i][j].adj = 0; G.arcs[i][j].info = NULL; } //确定邻接矩阵 printf("图中有%d条边\n",G.arcnum); if(G.arcnum>0){ printf("请依次输入这些边(用两个顶点表示一条边)及其权值\n\n\n"); } for(k = 0; k < G.arcnum; k++) { scanf("%d%d",&v1,&v2); printf("%d条边输入完成\n\n\n",k+1); i = LocateVex(G,v1); j = LocateVex(G,v2); if(i >= 0 && j >= 0) G.arcs[i][j].adj = G.arcs[j][i].adj = 1; //无向图,对称矩阵 //如果顶点有附带信息,则输入并申请空间 if(infoflag) { printf("please enter the info:"); while( (c = getchar()) != '#') str[len++] = c; info = (char *) malloc(len * sizeof(char)); str[len] = '\0'; strcpy(info,str); G.arcs[i][j].info = G.arcs[j][i].info = info; } } G.kind = UDG; return OK; } //------------------------创建有向图---------------------------------Status CreateDG(MGraph &G) { int i,j,k,len,infoflag; VertexType v1,v2; char str[MAX_INFO]; char *info; char c; //确定顶点数/弧数 printf("请分别输入 顶点数量、弧的数量、弧是否携带信息（要携带输入1否则输入0）\n"); scanf("%d%d%d",&G.vexnum,&G.arcnum,&infoflag); //确定各个顶点的值 printf("依次输入顶点（用-1表示顶点 V1 依此类推）\n"); for(i = 0;i < G.vexnum ; i++) scanf("%d",&G.vexs[i]); //初始化邻接矩阵 for(i = 0; i < G.vexnum; i++) for(j = 0;j < G.vexnum ; j++) { G.arcs[i][j].adj = 0; //有向图 G.arcs[i][j].info = NULL; } //确定邻接矩阵 printf("图中有%d条弧\n",G.arcnum); if(G.arcnum>0){ printf("请依次输入这些弧(用两个顶点表示一条弧)及其权值\n\n\n"); } for(k = 0; k < G.arcnum; k++) { scanf("%d%d",&v1,&v2); printf("%d条弧输入完成\n\n\n",k+1); i = LocateVex(G,v1); j = LocateVex(G,v2); if(i >= 0 && j >= 0) G.arcs[i][j].adj = 1; //有向图 //如果顶点有附带信息,则输入并申请空间 if(infoflag) { printf("please enter the info:"); while( (c = getchar()) != '#') str[len++] = c; info = (char *) malloc(len * sizeof(char)); strcpy(info,str); G.arcs[i][j].info = info; } } G.kind = DG; return OK; } //------------------------创建有向网---------------------------------Status CreateDN(MGraph &G) { int i,j,k,len,infoflag,w; VertexType v1,v2; char str[MAX_INFO]; char *info; char c; //确定顶点数/弧数 printf("请分别输入 顶点数量、弧的数量、弧是否携带信息（要携带输入1否则输入0）\n"); scanf("%d%d%d",&G.vexnum,&G.arcnum,&infoflag); //确定各个顶点的值 printf("依次输入顶点（用-1表示顶点 V1 依此类推）\n"); for(i = 0;i < G.vexnum ; i++) scanf("%d",&G.vexs[i]); //初始化邻接矩阵 for(i = 0; i < G.vexnum; i++) for(j = 0;j < G.vexnum ; j++) { G.arcs[i][j].adj = INFINITY; //有向网 G.arcs[i][j].info = NULL; } //确定邻接矩阵 printf("图中有%d条弧",G.arcnum); if(G.arcnum>0){ printf("请依次输入这些弧(用两个顶点表示一条弧)及其权值\n\n\n"); } for(k = 0; k < G.arcnum; k++) { scanf("%d%d%d",&v1,&v2,&w); printf("%d条弧输入完成\n\n\n",k+1); i = LocateVex(G,v1); j = LocateVex(G,v2); if(i >= 0 && j >= 0) G.arcs[i][j].adj = w; //有向图 //如果顶点有附带信息,则输入并申请空间 if(infoflag) { printf("please enter the info:"); while( (c = getchar()) != '#') str[len++] = c; info = (char *) malloc(len * sizeof(char)); strcpy(info,str); G.arcs[i][j].info = info; } } G.kind = DN; return OK; } //------------------------创建无向网---------------------------------Status CreateUDN(MGraph &G) { int i,j,k,len,infoflag,w; VertexType v1,v2; char str[MAX_INFO]; char *info; char c; //确定顶点数/弧数 printf("请分别输入 顶点数量、边的数量、边是否携带信息（要携带输入1否则输入0）\n"); scanf("%d%d%d",&G.vexnum,&G.arcnum,&infoflag); //确定各个顶点的值 printf("依次输入顶点（用-1表示顶点 V1 依此类推）\n"); for(i = 0;i < G.vexnum ; i++) scanf("%d",&G.vexs[i]); //初始化邻接矩阵 for(i = 0; i < G.vexnum; i++) for(j = 0;j < G.vexnum ; j++) { G.arcs[i][j].adj = INFINITY; //无向网 G.arcs[i][j].info = NULL; } //确定邻接矩阵 printf("图中有%d条边\n",G.arcnum); if(G.arcnum>0){ printf("请依次输入这些边(用两个顶点表示一条边)及其权值\n\n\n"); } for(k = 0; k < G.arcnum; k++) { scanf("%d%d%d",&v1,&v2,&w); printf("%d条边输入完成\n\n\n",k+1); i = LocateVex(G,v1); j = LocateVex(G,v2); if(i >= 0 && j >= 0) G.arcs[i][j].adj = G.arcs[j][i].adj = w; //无向网 //如果顶点有附带信息,则输入并申请空间 if(infoflag) { printf("please enter the info:"); while( (c = getchar()) != '#') str[len++] = c; info = (char *) malloc(len * sizeof(char)); strcpy(info,str); G.arcs[i][j].info = info; } } G.kind = UDN; return OK; } //------------------------创建图---------------------------------Status CreateGraph(MGraph &G) { printf("请输入要创建的图的种类 (有向图:0,有向网:1,无向图:2,无向网:3):\n"); scanf("%d",&G.kind); switch(G.kind) { case UDG: return CreateUDG(G); break; case DG: return CreateDG(G); case UDN: return CreateUDN(G); break; case DN: return CreateDN(G); break; default: return ERROR; } } //------------------------普里姆算法构造 最小生成树---------------------------------void MiniSpanTree_PRIM(MGraph G,VertexType u){ //用普里姆算法从顶点u出发构造网G的最小生成树T，输出T的各条边 if(G.kind==DG||G.kind==UDG){ printf("\n此图中不存在权值无法构造最小生成树！\n"); return; } else{ printf("从顶点%d出发构造网的最小生成树为\n",u); if(G.arcnum==0){ printf("\n空树\n"); } } struct { //定义一个辅助数组closedge（紧邻的边），来记录从U到V-U具有最小代价的边 //集合U表示已记录的顶点，集合V表示全部顶点 VertexType adjvex; //顶点 VRType lowcost; //附在顶点上的一条边的权值 与上面的adjvex合起来就可以具体表示到想要表示的边了 }closedge[MAX_VERTEX_NUM]; int k=LocateVex(G,u); //顶点u的位置 for(int j=0;j<G.vexnum;j++){ //辅助数组初始化 if(j!=k){ closedge[j]={u,G.arcs[k][j].adj}; } } closedge[k].lowcost=0; //初始化U={u} for(int i=1;i<G.vexnum;i++){ //选择其余G.vexnum-1个顶点 //k=minimum(closedge); //书上本来是调用这个函数 由于用到的结构体是在主函数内部调用的 定义这个函数不方便 就用下面9行代替了 for(k=0;!closedge[k].lowcost;k++){ //保证closedge[k].lowcost不是0 } int min=INFINITY; for(int s=0;s<G.vexnum;s++){ //求出T的下一个结点：第k顶点(权值最小的点) if(closedge[s].lowcost<min&&closedge[s].lowcost!=0){ k=s; min=closedge[s].lowcost; } } printf("%d_____(%d)_____%d\n",closedge[k].adjvex,closedge[k].lowcost,G.vexs[k]); //输出生成树的边 closedge[k].lowcost=0; //第k顶点并入U集 （用lowcost域==0来表示并入U集的顶点） for(int j=0;j<G.vexnum;j++){ if(G.arcs[k][j].adj<closedge[j].lowcost){ //新顶点并入U后重新选择最小边 closedge[j]={G.vexs[k],G.arcs[k][j].adj}; } } } printf("\n\n\n");}//------------------------遍历辅助 变量和函数---------------------------------Status visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量) TRUE表示已访问 FALSE表示未访问void(*VisitFunc)(VertexType v); //函数变量//------------------------辅助函数 1 :返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1---------------------------------int FirstAdjVex(MGraph G,VertexType v){ // 初始条件：图G存在，v是G中某个顶点 int i, j = 0, k; k = LocateVex(G, v); if (k < 0) return ERROR; if(G.kind%2==1){ //表示要遍历的不是图是网 j=INFINITY; } for (i = 0; i < G.vexnum; i++) if (G.arcs[k][i].adj != j) return i; return -1; } //------------------------辅助函数 2 :返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 ---------------------------------int NextAdjVex(MGraph G,VertexType v,VertexType w){ // 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点 int i, j = 0, k1, k2; k1 = LocateVex(G, v); // k1为顶点v在图G中的序号 k2 = LocateVex(G, w); // k2为顶点w在图G中的序号 if(G.kind%2==1){ //表示要遍历的不是图是网 j=INFINITY; } for (i = k2+1; i < G.vexnum; i++) if (G.arcs[k1][i].adj != j) return i; return -1; } //------------------------辅助函数 3 :访问---------------------------------void visit(VertexType i){ printf("%d ",i);} //------------------------辅助函数 4（多个函数） 队列 :---------------------------------typedef VRType QElemType; // 队列元素类型typedef struct QNode{ QElemType data; struct QNode *next;}*QueuePtr;typedef struct LinkQueue{ QueuePtr front, rear;}LinkQueue;void InitQueue(LinkQueue &Q) //初始化队列{ Q.front = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit(OVERFLOW); Q.front->next = NULL; Q.rear = Q.front;}void EnQueue(LinkQueue &Q, QElemType e) //入队列{ QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); p->next = NULL; memcpy(&(p->data), &e, sizeof(QElemType)); Q.rear->next = p; Q.rear = p;}Status QueueEmpty(LinkQueue Q) //判断队列是否为空{ if (Q.front == Q.rear) return TRUE; else return FALSE;}Status DeQueue(LinkQueue &Q, QElemType &e) //出队列{ QueuePtr p = Q.front, q; if (Q.front == Q.rear) return FALSE; q = p->next; memcpy(&e, &(q->data), sizeof(QElemType)); p->next = q->next; if (Q.rear == q) Q.rear = Q.front; free(q); return OK;}//------------------------深度优先遍历---------------------------------void DFS(MGraph G,int v){ //从第v个顶点出发递归地深度优先遍历图G。 int w; visited[v] = TRUE; // 设置访问标志为TRUE(已访问) VisitFunc(G.vexs[v]); // 访问第v个顶点 for(w = FirstAdjVex(G,G.vexs[v]); w >= 0; w = NextAdjVex(G,G.vexs[v],G.vexs[w])) if(!visited[w]) DFS(G,w); // 对v的尚未访问的序号为w的邻接顶点递归调用DFS } void DFSTraverse(MGraph G,void(*Visit)(VertexType v)){ // 初始条件：图G存在，Visit是顶点的应用函数。操作结果：从第1个顶点起，深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次 printf("\n深度优先遍历\n"); int v; VisitFunc=Visit; // 使用全局变量VisitFunc，使DFS不必设函数指针参数 for(v=0;v<G.vexnum;v++) visited[v]=FALSE; // 访问标志数组初始化(未被访问) for(v=0;v<G.vexnum;v++) if(!visited[v]) DFS(G,v); // 对尚未访问的顶点v调用DFS printf("\n"); } //------------------------广度优先遍历---------------------------------void BFSTraverse(MGraph G,void(*Visit)(VertexType)){ int v,u,w; LinkQueue Q; // 使用辅助队列Q和访问标志数组visited printf("\n广度优先遍历\n"); for(v=0;v<G.vexnum;v++) visited[v]=FALSE; // 置初值 InitQueue(Q); // 置空的辅助队列Q for(v=0;v<G.vexnum;v++){ if(!visited[v]){ // v尚未访问 visited[v]=TRUE; // 设置访问标志为TRUE(已访问) Visit(G.vexs[v]); EnQueue(Q,v); // v入队列 while(!QueueEmpty(Q)){ // 队列不空 DeQueue(Q,u); // 队头元素出队并置为u for(w = FirstAdjVex(G,G.vexs[u]); w >= 0; w=NextAdjVex(G,G.vexs[u],G.vexs[w])){ if(!visited[w]){ // w为u的尚未访问的邻接顶点的序号 visited[w]=TRUE; Visit(G.vexs[w]); EnQueue(Q,w); } } } } } printf("\n"); } //------------------------主函数---------------------------------int main(){ MGraph G; CreateGraph(G); MiniSpanTree_PRIM(G,-1); DFSTraverse(G,visit); BFSTraverse(G,visit); return 0;}