邻接表有向图是指通过邻接表表示的有向图。
上面的图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 100 typedef 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=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); }
运行结果：
