数据结构——图3354存储结构——邻表邻表的处理方法1 .图中的顶点按一维排列存储。 当然，顶点可以存储在单链表中，但是数组更容易读取顶点信息，更方便。 此外，在顶点数组中，每个数据元素都必须包含指向第一个相邻节点的指针，以便于找到顶点的边缘信息。
2 .图中各顶点v的所有邻点构成一个线性表，邻点的数量不定，所以用单链表存储，有向图称为顶点v的边表，有向图将顶点v称为弧尾的出边表。
例如，图7-4-6所示是有向图的邻接表结构.
如图所示，顶点表中的每个节点由两个域表示： data和firstedge，data是数据域，存储顶点信息，firstedge指向边表中的第一个节点，即该顶点的第1-1个相邻节点边缘节点由两个域组成： adjvex和next。 adjvex是邻接点字段，保存某个顶点的邻接点在顶点表中的下标，next保存指向边表中下一个节点的指针。 例如，当v顶点和vo、vz相互为邻接点时，在v1的边表中，adjvex分别为vo的0和v的2。
这种结构也便于我们获取有关图的信息。 例如，要知道某个顶点的程度，请查找该顶点边表中的节点数。 为了判断从顶点v到v是否存在边缘，只需测试顶点v的边缘表中adjvex中是否存在节点v的下标j即可。 求出顶点的所有邻接点，实际上扫描这个顶点的边表，得到的adjvex场对应的顶点是邻接.接点。
对于有向图，相邻表的结构相似。 例如，图7-4-7中第一个图的邻接表是第二个图。 但是，请注意，由于有向图有方向，所以将顶点作为弧的尾部来存储边的表，可以很容易地得到各顶点的出度。 但是，为了便于确定顶点的进入和以顶点为弧头的弧，有时也会制作有向图的反邻表。 也就是说，为每个顶点v创建以v为弧头的表。 如图7-4-7的第三张图所示。
此时，可以容易地计算某个顶点的入射度或出射度为多少，并且也可以容易地判断两个顶点上是否有弧。
关于加权网络图，如图7-4-8所示，在边表节点定义中再追加一个权重的数据字段，存储权重信息即可。
有了这些结构图，您就可以清楚地看到以下节点定义的代码：
#define MAXVEX 100 /*最大顶点数，用户定义*/typedef char VertexType； /*顶点类型必须由用户定义。 * /类型def int edge type； /*边的权重类型必须由用户定义。 */typedef struct EdgeNode /*边表的节点*/{int adjvex； /*邻点字段，其顶点对应的下标*/EdgeType weight； /*用于保存权重。 对于非网络图表，不需要* /结构边缘节点*下一步。 /*链域，指向下一个相邻节点*/}边缘节点； 类型结构顶点节点/*顶点表节点*/{VertexType data； /*顶点字段，保存顶点信息*/EdgeNode* firstedge； /*边缘标头指针*/}vertexNode，AdjList[MAXVEX]； typedef struct { adj列表adj列表； int numvertexes，numEdges； /*图中当前顶点数和边数*/} GraphAdjList； 关于邻接表的制作，也就是顺理成章的趋势。 有向图的邻接表制作代码如下。
/*创建图的邻接表结构的*/voidcreatealgraph (graphadjlist * g ) {int i，j，k； 边缘节点* e； printf (输入顶点数和边数：n )； scanf('%d、%d '、G-numvertexes、G-numEdges )； /*输入顶点数和边数*/for(I=0； iG-numvertexes； 导入I(/)顶点信息并创建顶点表(/)扫描g-adjlist[I].data； /*输入顶点信息*/G-adjList[i].firstedge=NULL； /*边表为空表*/}for(k=0； kG-numEdges； k(/)边表(/(printf )输入) Vi，Vj上的顶点编号(n ) )； scanf('%d，%d )，I，j )； /*输入边(vi，v3 )上的顶点编号(/e=) edgenode ) (malloc ) sizeof (edge node ) )； /*在内存中生成区域*//*边缘表节点*/e-adjvex=j相邻号为j */e-next=g-adj list [ I ].first edge； /*e指向当前顶点的节点*/G-adjList[i].firstedge=e； /*指向当前顶点的指针为e */e=(边缘节点* ) malloc (大小) edgenode )； /*在内存中生成区域*//*边缘表节点*/e-adjvex=i相邻号为I */e-next=g-adj list [ I ].first edge； /*e指向当前顶点的节点*/G-adjList[i].firstedge=e； /*指向当前顶点的指针为e*/}}有向图时，由于1边的对应都是2个顶点，因此在循环中对I和j一次分别插入。 对于n个顶点e条的边，本算法的时间复杂度容易为o(ne )。