第七章-图(2)图的存储结构

xiaoxiao2021-02-28  7

1、顺序存储结构:由于图的结构比较复杂,任意两个顶点直接之间都有可能存在联系,因此无法以数据元素在存储区中的物理位置来表示元素之间的关系(但可以借助数组的数据类型表示元素之间的关系)

2、链式存储结构:可用多重链表:

                                                (1)邻接表:

                                                (1)邻接多重表:

                                                (1)十字链表:

3、数组表示法:用两个数组分表存储数据元素(顶点)的信息和数据元素之间的关系

typedef enum{ DG,DN,UDG,UDN } GraphKind; //{有向图,有向网,无向图,无向网} //--------图的数组(邻接矩阵)存储表示------// typedef struct ArcCell{ int adj; // int 可用 VRType代替 ,VRType是顶点关系类型。对无权图,用1或者0 // 表示相邻否; 对带权图,则为权值类型 // InforType *info; //该弧相关信息指针 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{ char vexs[MAX_VERTEX_NUM]; //顶点向量 书中用 VertexType 代替 char AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类标志 }MGraph;

          G1和G2转换为邻接矩阵:

4、邻接表:是图的一种链式存储结构

//--------图的邻接表存储表示---------------// typedef struct ArcNode{ int adjvex; //该弧所指向的顶点的位置 int quan; struct ArcNode *nextarc; //指向下一条弧的指针 }ArcNode,*AList; //表结点 typedef struct VNode{ char data; //顶点信息 AList firstarc; //指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VERTEX_NUM]; //头结点 typedef struct{ AdjList vertices; int vexnum,arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类标志 }ALGraph; //------------------------------------------------//

邻接矩阵法的优点:容易实现图的操作,如:求某顶点的度,判断顶点之间是否右边(弧)。找顶点的邻接点等等

邻接矩阵的缺点:n个顶点需要 n*n 个单元存储边(弧):空间效率为 O(n^2) ,对稀疏矩阵而言尤其浪费空间。

5、十字链表:暂无。

6、邻接多重链表:暂无。

#include<stdio.h> #include<stdlib.h> #include<limits.h> #define ERROR 0 #define OK 1 #define INFINITY INT_MAX //最大值 #define MAX_VERTEX_NUM 21 //最大顶点个数 #define STACK_INT_SIZE 100 // #define STACKINCREAMENT 10 // typedef enum{ DG,DN,UDG,UDN } GraphKind; //{有向图,有向网,无向图,无向网} //--------图的数组(邻接矩阵)存储表示------// typedef struct ArcCell{ int adj; // int 可用 VRType代替 ,VRType是顶点关系类型。对无权图,用1或者0 // 表示相邻否; 对带权图,则为权值类型 // InforType *info; //该弧相关信息指针 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{ char vexs[MAX_VERTEX_NUM]; //顶点向量 书中用 VertexType 代替 char AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类标志 }MGraph; //----------------------------------------// //--------图的邻接表存储表示---------------// typedef struct ArcNode{ int adjvex; //该弧所指向的顶点的位置 int quan; struct ArcNode *nextarc; //指向下一条弧的指针 }ArcNode,*AList; //表结点 typedef struct VNode{ char data; //顶点信息 AList firstarc; //指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VERTEX_NUM]; //头结点 typedef struct{ AdjList vertices; int vexnum,arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类标志 }ALGraph; //------------------------------------------------// //--------------队列与栈的操作----------------// typedef struct QNode{ char data; struct QNode *next; }QNode,*QueuePre; typedef struct{ QueuePre front; //头指针 QueuePre rear; //尾指针 }LinkQueue; //队列 typedef struct{ int *base; int *top; int stacksize; }SqStack; //栈 //----------------------------------------// typedef struct{ char adjvex; int lowcost; }closedges[MAX_VERTEX_NUM]; //求最小生成树中的额辅助数组 int option; int visited[MAX_VERTEX_NUM]; //顶点访问标记数组 int indegree[MAX_VERTEX_NUM]; //顶点入度记录数组 int ve[MAX_VERTEX_NUM]; //顶点权值记录数组 //邻接矩阵的类型设置 int SetGraphKind(MGraph &G,int option){ switch(option){ case 1: G.kind=DG;break; case 2: G.kind=DN;break; case 3: G.kind=UDG;break; case 4: G.kind=UDN;break; default: return ERROR; } return OK; } //邻接表的类型设置 int SetGraphKind(ALGraph &G,int option){ switch(option){ case 1: G.kind=DG;break; case 2: G.kind=DN;break; case 3: G.kind=UDG;break; case 4: G.kind=UDN;break; default: return ERROR; } return OK; } //邻接矩阵顶点定位 int LocateVex(MGraph G,char v){ int m; for(m=1;m<=G.vexnum;m++) if(G.vexs[m]==v) return m; return ERROR; return OK; } //邻接表顶点定位 int LocateVex(ALGraph G,char v){ int m; for(m=1;m<=G.vexnum;m++){ if(G.vertices[m].data==v) return m; } printf("你输入的顶点不存储!"); return ERROR; } //队列的创建 int InitQueue(LinkQueue &Q){ Q.front=Q.rear=(QueuePre)malloc(sizeof(QNode)); if(!Q.front) return ERROR; Q.front->next=NULL; return OK; } //元素入队 int EnQueue(LinkQueue &Q,int e){ QueuePre p; p=(QueuePre)malloc(sizeof(QNode)); if(!p) return OK; p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; } //元素除队列 int DeQueue(LinkQueue &Q,int &e){ QueuePre p; if(Q.front==Q.rear) return ERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; //将队列的下一元素赋值给 Q.front if(Q.rear==p) Q.rear=Q.front; free(p); return OK; } //判断队列是否为空 int QueueEmpty(LinkQueue Q){ if(Q.front==Q.rear) return OK; return ERROR; } //创建栈 int InitStack(SqStack &S){ S.base=(int *)malloc(STACK_INT_SIZE*sizeof(int)); if(!S.base) return ERROR; S.top=S.base; S.stacksize=STACK_INT_SIZE; return OK; } //元素入栈 int Push(SqStack &S,int e){ if(S.top-S.base>=S.stacksize){ S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(int)); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREAMENT; } *S.top++=e; return OK; } //元素出栈 int Pop(SqStack &S,int &e){ if(S.top==S.base) return ERROR; e=*(S.top--); return OK; } //创建邻接矩阵 int CreatGraph(MGraph &G){ int i,j,k,w; char x,y; if(!SetGraphKind(G,option)){ printf("对图类型的设置失败"); return ERROR; } printf("请输入邻接矩阵: 顶点的个数 、弧的个数:"); scanf("%d %d",&G.vexnum,&G.arcnum); //构造顶点向量 if(G.vexnum>20){ //顶点个数过多 printf("你输入的顶点个数超过最大值"); return ERROR; } printf("请输入 %d 个顶点的值",G.vexnum); for(i=1;i<=G.vexnum;i++){ fflush(stdin); scanf("%c",&G.vexs[i]); //构造顶点向量的值 } if(G.kind==DG || G.kind==UDG){ //如果是 (有向图) 或者 (无向图) for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[i][j].adj=0; //初始化,初始化为没有关系的 if(G.kind==DG){ //有向图 printf("请输入有向图的两个相邻的顶点<x,y>(如果互相邻接则<x,y>也要输入)\n"); for(k=1;k<=G.arcnum;k++){ //输入每条弧所对应 fflush(stdin); scanf("%c %c",&x,&y); //返回 x,y的位置 i=LocateVex(G,x); j=LocateVex(G,y); G.arcs[i][j].adj=1; } } else{ //无向图 printf("请输入无向图的两个邻接顶点(x,y)\n"); for(k=1;k<=G.arcnum;k++){ fflush(stdin); scanf("%c %c",&x,&y); i=LocateVex(G,x); j=LocateVex(G,y); G.arcs[i][j].adj=1; G.arcs[j][i].adj=G.arcs[i][j].adj; //因为 无向图 是对称矩阵 } } } else{ //如果是(有向网)和(无向网) for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[i][j].adj=INT_MAX; //初始化 if(G.kind==DN){ printf("请输入有向网的两个相邻的顶点<x,y>以及相应的权值 w (如果互相邻接则 <x,y> 也要输入):\n"); for(k=1;k<=G.arcnum;k++){ fflush(stdin); scanf("%c %c %d",&x,&y,&w); i=LocateVex(G,x); j=LocateVex(G,y); G.arcs[i][j].adj=w; } } else{ printf("请输入无向网的两个相邻的顶点 (x,y) 以及相应的权值 w :\n");; for(k=1;k<=G.arcnum;k++){ fflush(stdin); scanf("%c %c %d",&x,&y,&w); i=LocateVex(G,x); j=LocateVex(G,y); G.arcs[i][j].adj=w; G.arcs[j][i].adj=G.arcs[i][j].adj; } } } return OK; } //创建邻接表 int CreatAList(ALGraph &G){ int i,j,m,n,key[MAX_VERTEX_NUM]; char x,y,w; AList p,q; SetGraphKind(G,option); printf("邻接表,请输入顶点的个数和弧个数:"); scanf("%d %d",&G.vexnum,&G.arcnum); if(G.vexnum>20){ //顶点个数过多 printf("你输入的顶点个数超过最大值"); return ERROR; } printf("请输入 %d 个顶点数:\n",G.vexnum); for(i=1;i<=G.vexnum;i++){ fflush(stdin); scanf("%c",&G.vertices[i].data); //构造顶点向量的值 G.vertices[i].firstarc=NULL; //指向下一条弧的指针 先初始化为 NULL key[i]=0; // } if(G.kind==DG){ //有向图 printf("请输入弧(如 A B ,其中 AB 与 BA是不同的弧):"); for(j=1;j<=G.arcnum;j++){ //输入弧 fflush(stdin); scanf("%c %c",&x,&y); m=LocateVex(G,x); //定位 n=LocateVex(G,y); p=G.vertices[m].firstarc; // AList p,q q=(AList)malloc(sizeof(ArcNode)); if(!q) return ERROR; q->nextarc=NULL; //q初始化的过程 q->adjvex=n; while(key[m] && p->nextarc){ p=p->nextarc; key[m]++; } if(!key[m]){ //key[m]为0 G.vertices[m].firstarc=q; key[m]++; } else p->nextarc=q; } } if(G.kind==UDG){ //无向图 printf("请输入弧(如 A B ,其中 AB 与 BA是不同的弧):"); for(j=1;j<=2*G.arcnum;j++){ //输入弧 fflush(stdin); scanf("%c %c",&x,&y); m=LocateVex(G,x); //定位 n=LocateVex(G,y); p=G.vertices[m].firstarc; // AList p,q q=(AList)malloc(sizeof(ArcNode)); if(!q) return ERROR; q->nextarc=NULL; //q初始化的过程 q->adjvex=n; while(key[m] && p->nextarc){ p=p->nextarc; key[m]++; } if(!key[m]){ //key[m]为0 G.vertices[m].firstarc=q; key[m]++; } else p->nextarc=q; } } if(G.kind==DN){ //有向网 printf("请输入依次弧以及这条弧的权值(如 A B 8,其中 AB 与 BA是不同的弧):"); for(j=1;j<=G.arcnum;j++){ //输入弧 fflush(stdin); scanf("%c %c %d",&x,&y,&w); m=LocateVex(G,x); //定位 n=LocateVex(G,y); p=G.vertices[m].firstarc; // AList p,q q=(AList)malloc(sizeof(ArcNode)); if(!q) return ERROR; q->nextarc=NULL; //q初始化的过程 q->quan=w; q->adjvex=n; //q 所在的位置 while(key[m] && p->nextarc){ p=p->nextarc; key[m]++; } if(!key[m]){ //key[m]为0 G.vertices[m].firstarc=q; key[m]++; } else p->nextarc=q; } } if(G.kind==UDN){ //无向图 printf("请输入依次弧以及这条弧的权值(如 A B 8,其中 AB 与 BA是不同的弧):"); for(j=1;j<=2*G.arcnum;j++){ //输入弧 fflush(stdin); scanf("%c %c %d",&x,&y,&w); m=LocateVex(G,x); //定位 n=LocateVex(G,y); p=G.vertices[m].firstarc; // AList p,q q=(AList)malloc(sizeof(ArcNode)); if(!q) return ERROR; q->nextarc=NULL; //q初始化的过程 q->quan=w; q->adjvex=n; //q 所在的位置 while(key[m] && p->nextarc){ p=p->nextarc; key[m]++; } if(!key[m]){ //key[m]为0 G.vertices[m].firstarc=q; key[m]++; } else p->nextarc=q; } } return OK; } void DG_(MGraph G1,ALGraph G2){ int i,j,k,m,key; AList s; printf("******************************"); printf("请你选择对有向图的基本操作及应用:\n 1.创建邻接矩阵 \n 2.创建邻接表 \n 3.拓扑结构 \n 4.退出 \n"); printf("******************************"); for(k=0; ;){ key=0; printf("请选择:"); scanf("%d",&m); switch(m){ case 1:CreatGraph(G1); //创建邻接矩阵 printf("有向图的邻接矩阵: \n"); for(i=1;i<=G1.vexnum;i++){ //将邻接矩阵输出 for(j=1;j<=G1.vexnum;j++) printf(" %d",G1.arcs[i][j].adj); printf("\n"); } break; case 2:CreatAList(G2); //创建邻接表 printf("有向图的邻接表: \n"); for(i=1;i<=G2.vexnum;i++){ //将邻接表输出 printf("%c",G2.vertices[i]); s=G2.vertices[i].firstarc; while(s){ j=s->adjvex; //该顶点在数组中的位置 fflush(stdin); printf("<%c",G2.vertices[i]); printf(",%c>",G2.vertices[j]); s=s->nextarc; } printf("\n"); } break; // case 3:printf("有向图的拓扑排序:\n"); // TopologicalSort(G2);break; case 4: key=1;break; }printf("\n"); if(key)break; } printf("\n\n"); } void UDG_(MGraph G1,ALGraph G2){ int i,j,k,m,key; AList s; printf("******************************"); printf("请你选择对有向网的基本操作及应用:\n 1.创建邻接矩阵 \n 2.创建邻接表 \n 3.关键路径 \n 4.退出 \n"); printf("******************************"); for(k=0; ;){ key=0; printf("请选择:"); scanf("%d",&m); switch(m){ case 1:CreatGraph(G1); //创建邻接矩阵 printf("有向网的邻接矩阵: \n"); for(i=1;i<=G1.vexnum;i++){ //将邻接矩阵输出 for(j=1;j<=G1.vexnum;j++){ if(G1.arcs[i][j].adj==INT_MAX) printf("#"); else printf("%d",G1.arcs[i][j].adj); } printf("\n"); } break; case 2:CreatAList(G2); //创建邻接表 printf("有向网的邻接表: \n"); for(i=1;i<=G2.vexnum;i++){ //将邻接表输出 printf("%c",G2.vertices[i]); s=G2.vertices[i].firstarc; while(s){ j=s->adjvex; //该顶点在数组中的位置 fflush(stdin); printf("<%c",G2.vertices[i]); printf(",%c>",G2.vertices[j]); printf("%d",s->quan); s=s->nextarc; } printf("\n"); } break; // case 3:printf("有向网的关键路径:\n"); // CriticalPath(G2);break; case 4: key=1;break; }printf("\n"); if(key)break; } printf("\n\n"); } void UDN_(MGraph G1,ALGraph G2){ int i,j,k,m,key; AList s; char u; printf("******************************"); printf("请你选择对无向网的基本操作及应用:\n 1.创建邻接矩阵 \n 2.创建邻接表 \n 3.生成最小树 \n 4.退出 \n"); printf("******************************"); for(k=0; ;){ key=0; printf("请选择:"); scanf("%d",&m); switch(m){ case 1:CreatGraph(G1); //创建邻接矩阵 printf("无向网的邻接矩阵: \n"); for(i=1;i<=G1.vexnum;i++){ //将邻接矩阵输出 for(j=1;j<=G1.vexnum;j++){ if(G1.arcs[i][j].adj==INT_MAX) printf("#"); else printf("%d",G1.arcs[i][j].adj); } printf("\n"); } break; case 2:CreatAList(G2); //创建邻接表 printf("有向网的邻接表: \n"); for(i=1;i<=G2.vexnum;i++){ //将邻接表输出 printf("%c",G2.vertices[i]); s=G2.vertices[i].firstarc; while(s){ j=s->adjvex; //该顶点在数组中的位置 fflush(stdin); printf("<%c",G2.vertices[i]); printf(",%c>",G2.vertices[j]); printf("%d",s->quan); s=s->nextarc; } printf("\n"); } break; // case 3:printf("请输入第一个顶点\n"); // fflush(stdin); // scanf("%c",&u); // CriticalPath(G2);break; case 4: key=1;break; }printf("\n"); if(key)break; } printf("\n\n"); } void DN_(MGraph G1,ALGraph G2){ int i,j,k,m,key; AList s; printf("******************************"); printf("请你选择对无向图的基本操作及应用:\n 1.创建邻接矩阵 \n 2.创建邻接表 \n 3.深度遍历 \n 4.广度遍历 \n 5.退出 \n"); printf("******************************"); for(k=0; ;){ key=0; printf("请选择:"); scanf("%d",&m); switch(m){ case 1:CreatGraph(G1); //创建邻接矩阵 printf("无向图的邻接矩阵: \n"); for(i=1;i<=G1.vexnum;i++){ //将邻接矩阵输出 for(j=1;j<=G1.vexnum;j++){ printf(" %d",G1.arcs[i][j].adj); } printf("\n"); } break; case 2:CreatAList(G2); //创建邻接表 printf("无向图的邻接表: \n"); for(i=1;i<=G2.vexnum;i++){ //将邻接表输出 printf("%c",G2.vertices[i]); s=G2.vertices[i].firstarc; while(s){ j=s->adjvex; //该顶点在数组中的位置 fflush(stdin); printf("<%c",G2.vertices[i]); printf(",%c>",G2.vertices[j]); s=s->nextarc; } printf("\n"); } break; // case 3:printf("无向图的深度优先:\n"); // DFSTraverse(G2);break; // case 4: // printf("无向图的广度优先:\n"); // BFSTraverse(G2);break; case 5: key=1;break; }printf("\n"); if(key)break; } printf("\n\n"); } //主函数 void main(){ MGraph G1; ALGraph G2; int i,n; for(i=0; ; ){ n=0; printf("\n"); printf("*************图的基本操作及其应用***************\n"); printf("1、有向图的基本操作及应用\n"); printf("2、无向图的基本操作及应用\n"); printf("3、有向网的基本操作及应用\n"); printf("4、无向网的基本操作及应用\n"); printf("5、退出\n"); printf("**************************************\n"); printf("请输入你的选择:"); scanf("%d",&option); printf("\n\n"); switch(option){ case 1: DG_(G1,G2);break; case 2: DN_(G1,G2);break; case 3: UDG_(G1,G2);break; case 4: UDN_(G1,G2);break; case 5: n=1;break; default: printf("你输入的编码有误!");break; } if(n) break; //n不为0 的时候退出 printf("\n\n"); } }

代码转载自:https://wenku.baidu.com/view/18137e1c6bd97f192279e927.html?rec_flag=default&mark_pay_doc=2&mark_rec_page=1&mark_rec_position=2&clear_uda_param=1

                                                (1)                                                 (1)
转载请注明原文地址: https://www.6miu.com/read-2250205.html

最新回复(0)