邻接表 在图论和计算机科学中，邻接表（英语：adjacency list）是表示了图中与每一个顶点相邻的边集的集合，这里的集合指的是无序集。 如果是无向图，那么每条边由两个结点组成，分别代表边的两个端点；如果是有向图，那么每条边是一个结点对，分别代表边的始点和终点。 计算机科学中的应用. 在计算机科学中，邻接表描述一种紧密相关的数据结构，用于表征图。在邻接表的表示中，对于图中的每个顶点，将保存所有其它与之相连的顶点（即“邻接表”）。例如，由吉多·范罗苏姆提出的，使用哈希表将每个顶点和该顶点的邻接点数组关连起来，就可以看作是上述表示方法的一种实现。又如，在Cormenetal中，顶点数组的每个元素都指向一个邻接点单链表。 邻接表结构的困难之一是无法明确在什么地方保存相关边的长度或花销。为了解决这个问题，一些算法，如 Goodrich and Tamassia所提出的面向对象邻接表，有时也称「关联度」，它为每个顶点保存一个对象表，每个对象表示指向顶点的那条边的关联度。为了完善这个结构，每条边必须指向两个组成其端点的顶点。这个额外的边对象使得它比直接列出所有边的邻接表消耗更多的内存，但它不失为一种保存边相关信息的好方法。 C 实现. /* 图的邻接表存储表示 */ #define MAX_VERTEX_NUM 20 typedef enum{DG,DN,UDG,UDN}GraphKind; /* {有向图,有向网,无向图,无向网} */ typedef struct ArcNode int adjvex; /* 该弧所指向的顶点的位置 */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ InfoType *info; /* 网的权值指针） */ }ArcNode; /* 表结点 */ typedef struct VertexType data; /* 顶点信息 */ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */ }VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */ typedef struct AdjList vertices; int vexnum,arcnum; /* 图的当前顶点数和弧数 */ GraphKind kind; /* 图的种类标志 */ }ALGraph; /* 图的邻接表存储的基本操作(15个)*/ #include"bo2-8.c" /* 不带头结点的单链表基本操作 */ #include"func2-1.c" /* 不带头结点的单链表扩展操作 */ int LocateVex(ALGraph G,VertexType u) { /* 初始条件：图G存在，u和G中顶点有相同特征 */ /* 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1 */ int i; for(i=0;i=2) /* 无向图或网，产生第2个表结点，并插在第j个元素(入弧)的表头 */ e.adjvex=i; /* e.info不变，不必再赋值 */ ListInsert(&(*G).vertices[j].firstarc,1,e); /* 插在第j个元素的表头，在bo2-8.c中 */ void CreateGraphF(ALGraph *G) { /* 采用邻接表 存储结构，由文件构造没有相关信息图或网G(用一个函数构造4种图) */ int i,j,k,w; /* w是权值 */ VertexType va,vb; /* 连接边或弧的2顶点 */ ElemType e; char filename[13]; FILE *graphlist; printf("请输入数据文件名(f7-1.txt或f7-2.txt)："); scanf("%s",filename); printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): "); scanf("%d",&(*G).kind); graphlist=fopen(filename,"r"); /* 以读的方式打开数据文件，并以graphlist表示 */ fscanf(graphlist,"%d",&(*G).vexnum); fscanf(graphlist,"%d",&(*G).arcnum); for(i=0;i=2) /* 无向图或网，产生第2个表结点，并插在第j个元素(入弧)的表头 */ e.adjvex=i; /* e.info不变，不必再赋值 */ ListInsert(&(*G).vertices[j].firstarc,1,e); /* 插在第j个元素的表头，在bo2-8.c中 */ fclose(graphlist); /* 关闭数据文件 */ void DestroyGraph(ALGraph *G) { /* 初始条件：图G存在。操作结果：销毁图G */ int i; ElemType e; for(i=0;ii) /* 顶点序号>i(保证动态生成的权值空间只释放1次) */ free(e.info); else /* 图 */ DestroyList(&(*G).vertices[i].firstarc); /* 销毁弧或边链表，在bo2-8.c中 */ (*G).vexnum=0; /* 顶点数为0 */ (*G).arcnum=0; /* 边或弧数为0 */ VertexType* GetVex(ALGraph G,int v) { /* 初始条件：图G存在，v是G中某个顶点的序号。操作结果：返回v的值 */ if(v>=G.vexnum||v-1) /* v是G的顶点 */ strcpy((*G).vertices[i].data,value); return OK; return ERROR; int FirstAdjVex(ALGraph G,VertexType v) { /* 初始条件：图G存在，v是G中某个顶点 */ /* 操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1 */ LinkList p; int v1; v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */ p=G.vertices[v1].firstarc; if(p) return p->data.adjvex; else return -1; Status equalvex(ElemType a,ElemType b) { /* DeleteArc()、DeleteVex()和NextAdjVex()要调用的函数 */ if(a.adjvex==b.adjvex) return OK; else return ERROR; int NextAdjVex(ALGraph G,VertexType v,VertexType w) { /* 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点 */ /* 操作结果：返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个邻接点，则返回-1 */ LinkList p,p1; /* p1在Point()中用作辅助指针，Point()在func2-1.c中 */ ElemType e; int v1; v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */ e.adjvex=LocateVex(G,w); /* e.adjvex为顶点w在图G中的序号 */ p=Point(G.vertices[v1].firstarc,e,equalvex,&p1); /* p指向顶点v的链表中邻接顶点为w的结点 */ if(!p||!p->next) /* 没找到w或w是最后一个邻接点 */ return -1; else /* p->data.adjvex==w */ return p->next->data.adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */ void InsertVex(ALGraph *G,VertexType v) { /* 初始条件：图G存在，v和图中顶点有相同特征 */ /* 操作结果：在图G中增添新顶点v(不增添与顶点相关的弧，留待InsertArc()去做) */ strcpy((*G).vertices[(*G).vexnum].data,v); /* 构造新顶点向量 */ (*G).vertices[(*G).vexnum].firstarc=NULL; (*G).vexnum++; /* 图G的顶点数加1 */ Status DeleteVex(ALGraph *G,VertexType v) { /* 初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧 */ int i,j,k; ElemType e; LinkList p,p1; j=LocateVex(*G,v); /* j是顶点v的序号 */ if(jnext=p->next; /* 从链表中删除p所指结点 */ else /* p指向首元结点 */ (*G).vertices[i].firstarc=p->next; /* 头指针指向下一结点 */ if((*G).kinddata.info); /* 释放动态生成的权值空间 */ free(p); /* 释放v为入度的结点 */ for(k=j+1;kj的结点，其序号-1 */ e.adjvex=k; p=Point((*G).vertices[i].firstarc,e,equalvex,&p1); /* Point()在func2-1.c中 */ if(p) p->data.adjvex--; /* 序号-1(因为前移) */ return OK; Status InsertArc(ALGraph *G,VertexType v,VertexType w) { /* 初始条件：图G存在，v和w是G中两个顶点 */ /* 操作结果：在G中增添弧，若G是无向的，则还增添对称弧 */ ElemType e; int i,j; i=LocateVex(*G,v); /* 弧尾或边的序号 */ j=LocateVex(*G,w); /* 弧头或边的序号 */ if(i=2) /* 无向，生成另一个表结点 */ e.adjvex=i; /* e.info不变 */ ListInsert(&(*G).vertices[j].firstarc,1,e); /* 将e插在弧头的表头 */ return OK; Status DeleteArc(ALGraph *G,VertexType v,VertexType w) { /* 初始条件：图G存在，v和w是G中两个顶点 */ /* 操作结果：在G中删除弧，若G是无向的，则还删除对称弧 */ int i,j; Status k; ElemType e; i=LocateVex(*G,v); /* i是顶点v(弧尾)的序号 */ j=LocateVex(*G,w); /* j是顶点w(弧头)的序号 */ if(i=2) /* 无向，删除对称弧 */ e.adjvex=i; DeleteElem(&(*G).vertices[j].firstarc,&e,equalvex); return OK; else /* 没找到待删除的弧 */ return ERROR; Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */ void(*VisitFunc)(char* v); /* 函数变量(全局量) */ void DFS(ALGraph G,int v) { /* 从第v个顶点出发递归地深度优先遍历图G。算法7.5 */ int w; visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */ VisitFunc(G.vertices[v].data); /* 访问第v个顶点 */ for(w=FirstAdjVex(G,G.vertices[v].data);w>=0;w=NextAdjVex(G,G.vertices[v].data,G.vertices[w].data)) if(!visited[w]) DFS(G,w); /* 对v的尚未访问的邻接点w递归调用DFS */ void DFSTraverse(ALGraph G,void(*Visit)(char*)) { /* 对图G作深度优先遍历。算法7.4 */ int v; VisitFunc=Visit; /* 使用全局变量VisitFunc，使DFS不必设函数指针参数 */ for(v=0;v=0;w=NextAdjVex(G,G.vertices[u].data,G.vertices[w].data)) if(!visited[w]) /* w为u的尚未访问的邻接顶点 */ visited[w]=TRUE; Visit(G.vertices[w].data); EnQueue(&Q,w); /* w入队 */ printf("\n"); void DFS1(ALGraph G,int v,void(*Visit)(char*)) { /* 从第v个顶点出发递归地深度优先遍历图G。仅适用于邻接表存储结构 */ ArcNode *p; /* p指向表结点 */ visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */ Visit(G.vertices[v].data); /* 访问该顶点 */ for(p=G.vertices[v].firstarc;p;p=p->next) /* p依次指向v的邻接顶点 */ if(!visited[p->data.adjvex]) DFS1(G,p->data.adjvex,Visit); /* 对v的尚未访问的邻接点递归调用DFS1 */ void DFSTraverse1(ALGraph G,void(*Visit)(char*)) { /* 对图G作深度优先遍历。DFS1设函数指针参数 */ int v; for(v=0;vnext) /* p依次指向u的邻接顶点 */ if(!visited[p->data.adjvex]) /* u的邻接顶点尚未被访问 */ visited[p->data.adjvex]=TRUE; /* 该邻接顶点设为已被访问 */ Visit(G.vertices[p->data.adjvex].data); /* 访问该邻接顶点 */ EnQueue(&Q,p->data.adjvex); /* 入队该邻接顶点序号 */ printf("\n"); void Display(ALGraph G) { /* 输出图的邻接矩阵G */ int i; LinkList p; switch(G.kind) case DG: printf("有向图\n"); break; case DN: printf("有向网\n"); break; case UDG:printf("无向图\n"); break; case UDN:printf("无向网\n"); printf("%d个顶点：\n",G.vexnum); for(i=0;idata.adjvex) /* 有向或无向两次中的一次 */ printf("%s→%s ",G.vertices[i].data,G.vertices[p->data.adjvex].data); if(G.kind%2) /* 网 */ printf(":%d ",*(p->data.info)); p=p->nextarc; printf("\n"); 权衡. 可用于替代邻接表的主要有邻接矩阵。用稀疏邻接矩阵表示邻接表时，将占用更少的空间。这是因为它能避免为"不存在"的边分配任何空间。在一台32位计算机上，如果使用原始的数组结构实现邻接表，那么对于一个无向图来说，它大约需要占用formula_1字节的存储空间，其中formula_2表示边的个数。每条边都将会在两个邻接表中重复出现，并分别占用4字节空间。 相反地，由于邻接矩阵中的每个元素仅占用一位（bit），故可以以非常紧密的方式来存储，仅占用formula_3个字节，其中formula_4代表顶点个数。除了节省空间外，这种紧密存储也发扬了locality of reference。 注意到一个图至多能有formula_5条边（允许循环）。令formula_6表示图的"致密度"，则由formula_7，可知邻接表将占用更多的空间，准确地说，仅当formula_8'以说只有当图比较稀疏的时候，才有可能以较少的空间来存储邻接表。不过，以上分析只有在仅考虑边的连接性，而不考虑关于边的任何数值信息时才有效。 除了空间方面的考虑外，不同的数据结构也使得不同的操作变得更容易。在一个邻接表中，给定一个顶点，可以很容易地找出它的所有邻边，因为只需要读取它的邻接表就可以了。在一个邻接矩阵中，相同的操作则需要扫描一行，花费大约formula_9（大O标记）时间。而如果你想知道给定的两个顶点间是否存在有边，在邻接矩阵里可以立刻查到，在邻接表中则需要花费以边的最小关联度成比例的时间。