开发者社区> 登天蚂蚁> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

数据结构(八):邻接表与邻接矩阵

简介: 邻接表和邻接矩阵是图的两种常用存储表示方式,用于记录图中任意两个顶点之间的连通关系,包括权值。 对于图 而言,其中 表示顶点集合, 表示边集合。
+关注继续查看
img_553969a3ce50c410df680cbbc8bf2458.jpe

邻接表和邻接矩阵是图的两种常用存储表示方式,用于记录图中任意两个顶点之间的连通关系,包括权值。

对于图 G=(V, E) 而言,其中 V 表示顶点集合,E 表示边集合。

对于无向图 graph,图的顶点集合和边集合如下:

V = \{1,2,3,4,5\}
E =\{(1,2),(1,3),(1,4),(2,3),(3,4),(3,5)\}

img_726986470f346ff425842e0a0602b78b.png
graph

对于有向图 digraph,图的顶点集合和边集合如下:

V = \{1,2,3,4,5\}
E =\{<1,2>,<1,3>,<1,4>,<2,3>,<3,1>,<3,5>,<4,3>\}

img_c332765b9a1fb1907130f951349425a2.png
digraph

邻接表

无向图 graph 表示

img_5d4cfc9ac9ba3627737b4fca2a7835ca.png
graph_adjacency_list

有向图 digraph 表示

img_57d12e56c929c84c14248ac0939c7c2e.png
digraph_adjacency_list

若采用邻接表表示,则需要申请 |V| 个列表,每个列表存储一个顶点出发的所有相邻顶点。如果图 G 为有向图,则 |V| 个列表存储的总顶点个数为 |E|;如果图 G 为无向图,则 |V| 个列表存储的总顶点个数为 2 |E|(暂不考虑自回路)。因为需要申请大小为 |V| 的数组来保存节点,对节点分配序号,所以需要申请大小为 |V| 的额外存储空间,即邻接表方式的存储空间复杂度为 O(|V|+|E|)

邻接矩阵

无向图 graph 表示

img_07c71cf4dcd5bc8230cb3d15cd0631bb.png
graph_adjacency_matrix

有向图 digraph 表示

img_31e9ae64f8472b72d7b20ca8a9fb3286.png
digraph_adjacency_matrix

若采用邻接矩阵表示,则需要申请空间大小为 |V|^2 的二维数组,在二位数组中保存每两个顶点之间的连通关系,则无论有向图或无向图,邻接矩阵方式的存储空间复杂度皆为 O(|V|^2)。若只记录图中顶点是否连通,不记录权值大小,则可以使用一个二进制位来表示二维数组的每个元素,并且根据无向图的特点可知,无向图的邻接矩阵沿对角线对称,所以可以选择记录一半邻接矩阵的形式来节省空间开销。

两种存储结构对比

根据邻接表和邻接矩阵的结构特性可知,当图为稀疏图、顶点较多,即图结构比较大时,更适宜选择邻接表作为存储结构。当图为稠密图、顶点较少时,或者不需要记录图中边的权值时,使用邻接矩阵作为存储结构较为合适。

代码附录

邻接表结构
# graph node definition
class Node(object):
    def __init__(self, index, weight, next = None):
        self.index = index
        self.weight = weight
        self.next = next

# adjacency list definition
class AdjacencyList(object):
    def __init__(self, number):
        self.number = number
        self.list = [None] * number

    # insert node
    def insert(self, origin, index, weight = 1):
        node = Node(index, weight, self.list[origin - 1])
        self.list[origin - 1] = node

测试代码:

if __name__ == '__main__':
    graph = AdjacencyList(5)
    graph.insert(1, 2)
    graph.insert(1, 3)
    graph.insert(1, 4)
    graph.insert(2, 3)
    graph.insert(3, 1)
    graph.insert(3, 5)
    graph.insert(4, 3)
    for i in range(graph.number):
        print('node', (i + 1), 'links:', end = ' ')
        node = graph.list[i]
        while node:
            print(node.index, end = ' ')
            node = node.next
        print()

输出结果:

node 1 links: 4 3 2 
node 2 links: 3 
node 3 links: 5 1 
node 4 links: 3 
node 5 links: 
邻接矩阵结构
# adjacency list definition
class AdjacencyMatrix(object):
    def __init__(self, number):
        self.number = number
        self.list = [[None] * number for i in range(number)]

    # insert node
    def insert(self, origin, index, weight = 1):
        self.list[origin - 1][index - 1] = weight

测试代码:

if __name__ == '__main__':
    graph = AdjacencyMatrix(5)
    graph.insert(1, 2)
    graph.insert(1, 3)
    graph.insert(1, 4)
    graph.insert(2, 3)
    graph.insert(3, 1)
    graph.insert(3, 5)
    graph.insert(4, 3)
    for i in range(graph.number):
        print('node', (i + 1), 'links:', end = ' ')
        j = 0
        while j < graph.number:
            print(j + 1, end = ' ') if graph.list[i][j] else None
            j += 1
        print()

输出结果:

node 1 links: 2 3 4 
node 2 links: 3 
node 3 links: 1 5 
node 4 links: 3 
node 5 links: 

github 链接:邻接表与邻接矩阵

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据结构——双链表
数据结构——双链表
15 0
数据结构之链表
数据结构之链表
41 0
数据结构之链表
一、概念 (1)数组的线性序是由数组的下标决定的,链表中的顺序是由各对象中的指针所决定的 (2)链表结点结构 node *prev; node *next; int key; (3)链表结点 node *head; node *nil;//哨兵 (4)对链表的操作 LIST-SEARCH(L, k) LIST-INSERT(L, x) LIST-DELETE(
940 0
数据结构--线性表
基本概念 线性表:有n(n>=0)个相同数据类型数据元素组成的线性结构。其实现方法见图。 线性结构:除了第一个和最后一个数据元素,其余各元素只有一个前驱元素和后继元素,第一个数据元素只有一个后继元素,最后一个数据元素只有一个前驱元素。
702 0
邻接矩阵与邻接表
// 邻接矩阵 #include&lt;stdio.h&gt; #include&lt;string.h&gt; #define MAXN 100 int Edge[MAXN][MAXN]; int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); int
1105 0
+关注
登天蚂蚁
相信量变引发质变,相信厚积薄发
30
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载