邻接表无向图是指通过邻接表表示的无向图。
上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点，而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。
上图右边的矩阵是G1在内存中的邻接表示意图。每一个顶点都包含一条链表，该链表记录了"该顶点的邻接点的序号"。例如，第2个顶点(顶点C)包含的链表所包含的节点的数据分别是"0,1,3"；而这"0,1,3"分别对应"A,B,D"的序号，"A,B,D"都是C的邻接点。就是通过这种方式记录图的信息的。
邻接表无向图的代码说明
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是顶点所包含的数据，而first_edge是该顶点所包含链表的表头指针。
(03) ENode是邻接表顶点所包含的链表的节点对应的结构体。
ivex是该节点所对应的顶点在vexs中的索引，而next_edge是指向下一个节点的。
2. 创建矩阵
2.1 创建图(用已提供的矩阵)
C语言实现代码：
#include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<string.h> #define MAX 100 typedef struct graph { char vexs[MAX]; int vexnum; int edgnum; int matrix[MAX][MAX]; }Graph,*PGraph; static int get_position(Graph g,char ch) { int i; for(i=0;i<g.vexnum;i++) if(g.vexs[i]==ch) return i; return -1; } Graph* 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; Graph *pG; if((pG=(Graph*)malloc(sizeof(Graph)))==NULL) return NULL; memset(pG,0,sizeof(Graph)); pG->vexnum=vlen; pG->edgnum=elen; for(i=0;i<pG->vexnum;i++) { pG->vexs[i]=vexs[i]; } for(i=0;i<pG->edgnum;i++) { p1=get_position(*pG,edges[i][0]); p2=get_position(*pG,edges[i][1]); pG->matrix[p1][p2]=1; pG->matrix[p2][p1]=1; } return pG; } void print_graph(Graph G) { int i,j; printf("matrix Graph:\n"); for(i=0;i<G.vexnum;i++) { for(j=0;j<G.vexnum;j++) printf("%d ",G.matrix[i][j]); printf("\n"); } } int main() { Graph *pG; pG=create_graph(); print_graph(*pG); }
运行结果：
