数据结构-图-章节5

章节5 图的邻接表存储法

通常，图更多的是采用链表存储，具体存储方式有3种，分别是邻接表、邻接多重表和十字链表。

邻接表存储法，既适用于存储无向图，也适用于存储有向图。

邻接点：在图中，如果两个点相互连通，即通过其中一个顶点，可直接找到另一个顶点，则称它们互为邻接点。

邻接指的是图中顶点之间有边的存在

邻接表存储图的实现方式是，给图中的各个顶点独自建立一个链表，用节点存储该顶点，用链表中其他节点存储各自的临接点。

与此同时，为了便于管理这些链表，通常会将所有链表的头结点存储到数组中。也正因为各个链表的头结点存储的是各个顶点，因此各链表在存储邻接点数据时，仅需要存储该邻接顶点位于数组中的位置下标即可。

例如图1a所示的有向图，其对应的邻接表如图b所示：

图1

拿顶点v1来说，其相关的邻接点分别为v2和v3，因此存储v1的链表中存储的是v2和v3在数组中的位置下标1和2

使用邻接表计算无向图中顶点的入度和出度会非常简单，只需从数组中找到该顶点然后统计此链表中的节点的数量即可。

对于利用邻接表求某顶点的入度，有两种方式： 1 遍历整个邻接表中的节点，统计数据域与该顶点所在的数组位置下相同的节点数量，即为该顶点的入度。 2 建立一个逆邻接表，该表中的各顶点邻接表专门用于存储此顶点为弧头的所有顶点在数组中的位置下标。如建立一张图1a对应的逆邻接表，图4所示

图4

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG