首页 > 代码库 > 邻接表有向图的介绍
邻接表有向图的介绍
邻接表有向图是指通过邻接表表示的有向图。
上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点，而且包含了"<A,B>,<B,C>,<B,E>,<B,F>,<C,E>,<D,C>,<E,B>,<E,D>,<F,G>"共9条边。
上图右边的矩阵是G2在内存中的邻接表示意图。每一个顶点都包含一条链表，该链表记录了"该顶点所对应的出边的另一个顶点的序号"。例如，第1个顶点(顶点B)包含的链表所包含的节点的数据分别是"2,4,5"；而这"2,4,5"分别对应"C,E,F"的序号，"C,E,F"都属于B的出边的另一个顶点。
邻接表有向图的代码说明
1. 基本定义
// 邻接表中表对应的链表的顶点typedef struct _ENode{ int ivex; // 该边所指向的顶点的位置 struct _ENode *next_edge; // 指向下一条弧的指针}ENode, *PENode;// 邻接表中表的顶点typedef struct _VNode{ char data; // 顶点信息 ENode *first_edge; // 指向第一条依附该顶点的弧}VNode;// 邻接表typedef struct _LGraph{ int vexnum; // 图的顶点的数目 int edgnum; // 图的边的数目 VNode vexs[MAX];}LGraph;
(01) LGraph是邻接表对应的结构体。 vexnum是顶点数，edgnum是边数；vexs则是保存顶点信息的一维数组。
(02) VNode是邻接表顶点对应的结构体。 data是顶点所包含的数据，而firstedge是该顶点所包含链表的表头指针。
(03) ENode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引，而nextedge是指向下一个节点的。
2. 创建矩阵
邻接表C实现代码：
#include<stdlib.h>#include<stdio.h>#include<string.h>#include<malloc.h>#define MAX 100typedef struct ENode{ int ivex; struct ENode *next_edge;}ENode;typedef struct VNode{ char data; struct ENode *first_edge;}VNode;typedef struct LGraph{ int vexnum; int edgnum; VNode vexs[MAX];}LGraph;int get_position(LGraph g,char ch){ int i; for(i=0;i<g.vexnum;i++) if(ch==g.vexs[i].data) return i; return -1;}LGraph* create_graph(){ char vexs[]= {‘A‘,‘B‘,‘C‘,‘D‘,‘E‘,‘F‘,‘G‘}; char edges[][2]= {{‘A‘,‘C‘},{‘A‘,‘D‘},{‘A‘,‘F‘},{‘B‘,‘C‘},{‘C‘,‘D‘},{‘E‘,‘G‘},{‘F‘,‘G‘}}; int vlen=sizeof(vexs)/sizeof(vexs[0]); int elen=sizeof(edges)/sizeof(edges[0]); int i,p1,p2; ENode *node2; LGraph *pG; if((pG=(LGraph*)malloc(sizeof(LGraph)))==NULL) return NULL; memset(pG,0,sizeof(pG)); pG->edgnum=elen; pG->vexnum=vlen; for(i=0;i<pG->vexnum;i++) { pG->vexs[i].data=http://www.mamicode.com/vexs[i]; pG->vexs[i].first_edge=NULL; } for(i=0;i<pG->edgnum;i++) { p1=get_position(*pG,edges[i][0]); p2=get_position(*pG,edges[i][1]); node2=(ENode*)malloc(sizeof(ENode)); node2->ivex=p2; node2->next_edge=NULL; if(pG->vexs[p1].first_edge==NULL) pG->vexs[p1].first_edge=node2; else { ENode *tmp=pG->vexs[p1].first_edge; while(tmp->next_edge) { tmp=tmp->next_edge; } tmp->next_edge=node2; } } return pG;}void print_graph(LGraph G){ int i; printf("List Graph:\n"); ENode *node=NULL; for(i=0;i<G.vexnum;i++) { printf("%d(%c): ", i, G.vexs[i].data); node=G.vexs[i].first_edge; while(node) { printf("%d(%c) ", node->ivex, G.vexs[node->ivex].data); node=node->next_edge; } printf("\n"); }}int main(){ LGraph *pG; pG=create_graph(); print_graph(*pG);}
运行结果：
邻接表有向图的介绍
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。