建立无向图的邻接多重表.pdf

建立无向图的邻接多重表 数据结构 C 语言版 #include #include #define MAX_NAME 3 / 顶点字符串的最大长度 +1 #define MAX_INFO 80 / 相关信息字符串的最大长度+1 typedef char InfoType; typedef char VertexTypeMAX_NAME; / 字符串类型 / AMLGraph.h 无向图的邻接多重表存储表示 #define MAX_VERTEX_NUM 20 typedef enumunvisited,visitedVisitIf; typedef struct EBox VisitIf mark; / 访问标记 int ivex,jvex; / 该边依附的两个顶点的位置 struct EBox *ilink,*jlink; / 分别指向依附这两个顶点的下一 条边 InfoType *info; / 该边信息指针 EBox; typedef struct VertexType data; EBox *firstedge; / 指向第一条依附该顶点的边 VexBox; typedef struct VexBox adjmulistMAX_VERTEX_NUM; int vexnum,edgenum; / 无向图的当前顶点数和边数 AMLGraph; typedef int QElemType; / 单链队列队列的链式存储结构 typedef struct QNode QElemType data; / 数据域 struct QNode *next; / 指针域 QNode,*QueuePtr; typedef struct QueuePtr front,/队头指针，指针域指向队头元素 rear; /队尾指针，指向队尾元素 LinkQueue; / 若 G中存在顶点 u, 则返回该顶点在无向图中位置; 否则返回 -1 int LocateVex(AMLGraph G,VertexType u) int i; for(i=0;imark=unvisited; / 设初值 p-ivex=i; p-jvex=j; p-info=NULL; p-ilink=(*G).adjmulisti.firstedge; / 插在表头 (*G).adjmulisti.firstedge=p; p-jlink=(*G).adjmulistj.firstedge; / 插在表头 (*G).adjmulistj.firstedge=p; if(IncInfo) / 边有相关信息 printf(“请 输 入 该 弧 的 相 关 信 息 (info=(char*)malloc(l+1)*sizeof(char); strcpy(p-info,s); return 1; / 返回 v 的值 VertexType* GetVex(AMLGraph G,int v) if(v=G.vexnum|vivex=i) return G.adjmulisti.firstedge-jvex; else return G.adjmulisti.firstedge-ivex; else return -1; / 返回 v 的( 相对于 w的)下一个邻接顶点的序号。 若 w是 v 的最后一 个邻接点 , 则返回-1 int NextAdjVex(AMLGraph G,VertexType v,VertexType w) int i,j; EBox *p; i=LocateVex(G,v); / i是顶点 v 的序号 j=LocateVex(G,w); / j是顶点 w的序号 if(iivex=i / 找下一个邻接顶点 else if(p-jvex=i / 找下一个邻接顶点 else / 是邻接顶点 w break; if(p if(p else if(p if(p if(p else if(p return -1; / 在 G中增添新顶点 v( 不增添与顶点相关的弧 , 留待 InsertArc()去 做) int InsertVex(AMLGraph *G,VertexType v) if(*G).vexnum=MAX_VERTEX_NUM) / 结点已满，不能插入 return 0; if(LocateVex(*G,v)=0) / 结点已存在 , 不能插入 return 0; strcpy(*G).adjmulist(*G).vexnum.data,v); (*G).adjmulist(*G).vexnum.firstedge=NULL; (*G).vexnum+; return 1; / 在 G中删除弧 int DeleteArc(AMLGraph *G,VertexType v,VertexType w) int i,j; EBox *p,*q; i=LocateVex(*G,v); j=LocateVex(*G,w); if(ijvex=j) / 第 1 条边即为待删除边 ( 情况 1) (*G).adjmulisti.firstedge=p-ilink; else if(p else / 第 1 条边不是待删除边 while(p) / 向后查找弧 if(p-ivex=i p=p-ilink; / 找下一个邻接顶点 else if(p-jvex=i p=p-jlink; / 找下一个邻接顶点 else / 是邻接顶点 w break; if(!p) / 没找到该边 return 0; if(p-ivex=i else q-jlink=p-ilink; else if(p-ivex=j else q-jlink=p-jlink; / 以下由另一顶点起找待删除边且删除之 p=(*G).adjmulistj.firstedge; / p指向顶点 w的第 1 条边 if(p-jvex=i) / 第 1 条边即为待删除边 ( 情况 1) (*G).adjmulistj.firstedge=p-ilink; if(p-info) / 有相关信息 free(p-info); free(p); else if(p-ivex=i) / 第 1 条边即为待删除边 ( 情况 2) (*G).adjmulistj.firstedge=p-jlink; if(p-info) / 有相关信息 free(p-info); free(p); else / 第 1 条边不是待删除边 while(p) / 向后查找弧 if(p-ivex=j p=p-ilink; / 找下一个邻接顶点 else if(p-jvex=j p=p-jlink; / 找下一个邻接顶点 else / 是邻接顶点 v break; if(p-ivex=i else q-jlink=p-jlink; if(p-info) / 有相关信息 free(p-info); free(p); else if(p-ivex=j else q-jlink=p-ilink; if(p-info) / 有相关信息 free(p-info); free(p); (*G).edgenum-; return 1; / 删除 G中顶点 v 及其相关的边 int DeleteVex(AMLGraph *G,VertexType v) int i,j; VertexType w; EBox *p; i=LocateVex(*G,v); / i为待删除顶点的序号 if(iivex=j+1) p-ivex-; p=p-ilink; else p-jvex-; p=p-jlink; return 1; void DestroyGraph(AMLGraph *G) int i; for(i=(*G).vexnum-1;i=0;i-) DeleteVex(G,(*G).adjmulisti.data); / 在 G中增添弧 int InsertArc(AMLGraph *G,VertexType v,VertexType w) int i,j,l,IncInfo; char sMAX_INFO; EBox *p; i=LocateVex(*G,v); / 一端 j=LocateVex(*G,w); / 另一端 if(imark=unvisited; p-ivex=i; p-jvex=j; p-info=NULL; p-ilink=(*G).adjmulisti.firstedge; / 插在表头 (*G).adjmulisti.firstedge=p; p-jlink=(*G).adjmulistj.firstedge; / 插在表头 (*G).adjmulistj.firstedge=p; printf(“该边是否有相关信息 (1: 有 0: 无): “); scanf(“%d%*c“, / 吃掉回车符 if(IncInfo) / 边有相关信息 printf(“请输入该边的相关信息 (info=(char*)malloc(l+1)*sizeof(char); strcpy(p-info,s); (*G).edgenum+; return 1; int visiteMAX_VERTEX_NUM; / 访问标志数组 ( 全局量) int(*VisitFunc)(VertexType v); void DFS(AMLGraph G,int v) int j; EBox *p; VisitFunc(G.adjmulistv.data); visitev=1; p=G.adjmulistv.firstedge; while(p) j=p-ivex=v?p-jvex:p-ivex; if(!visitej) DFS(G,j); p=p-ivex=v?p-ilink:p-jlink; / 算法 7.4 / 从第 1 个顶点起 , 深度优先遍历图 G,并对每个顶点调用函数Visit void DFSTraverse(AMLGraph G,int(*visit)(VertexType) int v; VisitFunc=visit; for(v=0;vnext=NULL; / 队头指针指向空， 无数据域，这样构 成了一个空队列 return 1; / 若 Q为空队列 , 则返回 1, 否则返回 0 int QueueEmpty(LinkQueue Q) if(Q.front=Q.rear) return 1; else return 0; / 插入元素 e 为 Q的新的队尾元素 int EnQueue(LinkQueue *Q,QElemType e) QueuePtr p=(QueuePtr)malloc(sizeof(QNode); if(!p) / 存储分配失败 exit(0); / 生成一个以为 e 为数据域的队列元素 p-data=e; p-next=NULL; / 将该新队列元素接在队尾的后面 (*Q).rear-next=p; (*Q).rear=p; return 1; / 若队列不空 , 删除 Q的队头元素 , 用e 返回其值 , 并返回 1, 否则返回 0 int DeQueue(LinkQueue *Q,QElemType *e) QueuePtr p; if(*Q).front=(*Q).rear) return 0; p=(*Q).front-next; / 队头元素 *e=p-data; (*Q).front-next=p-next; if(*Q).rear=p) (*Q).rear=(*Q).front; free(p); return 1; / 从第 1 个顶点起 , 按广度优先非递归遍历图G,并对每个顶点调用函 数 / Visit一次且仅一次。使用辅助队列Q和访问标志数组 visite void BFSTraverse(AMLGraph G,int(*Visit)(VertexType) int v,u,w; VertexType w1,u1; LinkQueue Q; for(v=0;v=0;w=NextAdjVex(G,u1,strcpy(w1, *GetVex(G,w) if(!visitew) / w为 u 的尚未访问的邻接顶点的序 号 visitew=1; Visit(G.adjmulistw.data); EnQueue( printf(“n“); / 置边的访问标记为未被访问 void MarkUnvizited(AMLGraph G) int i; EBox *p; for(i=0;imark=unvisited; if(p-ivex=i) p=p-ilink; else p=p-jlink; / 输出无向图的邻接多重表G void Display(AMLGraph G) int i; EBox *p; MarkUnvizited(G); / 置边的访问标记为未被访问 printf(“%d个顶点： n“,G.vexnum); for(i=0;iivex=i) / 边的 i 端与该顶点有关 if(!p-mark) / 只输出一次 printf(“%s%s “,G.adjmulisti.data,G.adjmulistp-jvex.data); p-mark=visited; if(p-info) / 输出附带信息 printf(“相关信息 : %s “,p-info); p=p-ilink; else / 边的 j 端与该顶点有关 if(!p-mark) / 只输出一次 printf(“%s%s “,G.adjmulistp-ivex.data,G.adjmulisti.data); p-mark=visited; if(p-info) / 输出附带信息 printf(“相关信息 : %s “,p-info); p=p-jlink; printf(“n“); int visit(VertexType v) printf(“%s “,v); return 1; int main() int k,n; AMLGraph g; VertexType v1,v2; CreateGraph( Display(g); printf(“修改顶点的值，请输入原值新值: “); scanf(“%s%s“,v1,v2); PutVex( printf(“插入新顶点，请输入顶点的值: “); scanf(“%s“,v1); InsertVex( printf(“插入与新顶点有关的边，请输入边数: “); scanf(“%d“, for(k=0;kn;k+) printf(“请输入另一顶点的值 : “); scanf(“%s“,v2); InsertArc( Display(g); printf(“深度优先搜索的结果 :n“); DFSTraverse(g,visit); printf(“广度优先搜索的结果 :n“); BFSTraverse(g,visit); DestroyGraph( system(“pause“); return 0; /* 输出效果： 请输入无向图G 的顶点数 , 边数 , 边是否含其它信息( 是:1 ，否:0): 3,2,0 请输入 3 个顶点的值 (3 个字符): a b c 请顺序输入每条边的两个端点( 以空格作为间隔 ): a b a c 3 个顶点： a b c 2 条边: ac a b 修改顶点的值，请输入原值新值: a d 插入新顶点，请输入顶点的值: e 插入与新顶点有关的边，请输入边数: 1 请输入另一顶点的值 : b 该边是否有相关信息 (1: 有 0: 无): 0 4 个顶点： d b c e 3 条边: dc d b eb 深度优先搜索的结果 : d c b e 广度优先搜索的结果 : d b e c 请按任意键继续 . . . */