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

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

对于图

而言,其中

表示顶点集合,

表示边集合。

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

graph

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

digraph

邻接表

无向图 graph 表示

graph_adjacency_list

有向图 digraph 表示

digraph_adjacency_list

若采用邻接表表示,则需要申请

个列表,每个列表存储一个顶点出发的所有相邻顶点。如果图

为有向图,则

个列表存储的总顶点个数为

;如果图

为无向图,则

个列表存储的总顶点个数为

(暂不考虑自回路)。即邻接表方式的存储空间复杂度为

邻接矩阵

无向图 graph 表示

graph_adjacency_matrix

有向图 digraph 表示

digraph_adjacency_matrix

若采用邻接矩阵表示,则需要申请空间大小为

的二维数组,在二位数组中保存每两个顶点之间的连通关系,则无论有向图或无向图,邻接矩阵方式的存储空间复杂度皆为

。若只记录图中顶点是否连通,不记录权值大小,则可以使用一个二进制位来表示二维数组的每个元素,并且根据无向图的特点可知,无向图的邻接矩阵沿对角线对称,所以可以选择记录一半邻接矩阵的形式来节省空间开销。

两种存储结构对比

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

代码附录

邻接表结构
# 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: 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习与自然语言处理

判断有向图是否有圈

1. 拓扑排序 拓扑排序是对有向无圈图的顶点的一种排序:如果存在一条vi到vj的路径,则vj排在vi后面(因为只要满足这个特性就是拓扑序列,所以它不一定是唯一的...

51080
来自专栏python读书笔记

《python算法教程》Day5 - DFS遍历图(邻接字典)DFS简介代码示例

这是《python算法教程》的第5篇读书笔记。这篇笔记的主要内容为运用DFS(深度优先搜索,depth first search)对图(邻接字典)进行遍历。 D...

666110
来自专栏向治洪

图算法之bfs、dfs、prim、Dijkstra

概述 在图算法中经常要执行遍历每个顶点和每条边的操作,即图搜索。许多图算法都以图搜索为基础,如2-着色问题、连通性计算基于深度优先搜寻(depth-first ...

73260
来自专栏kalifaの日々

C++迪杰斯特拉最短路径算法实现

input 第一行表示这个图有4条边,下面五行代表这个图的5条边。 4 0 2 2 0 1 5 1 3 2 2 3 6 -1 0 0 ? 输入样例 out 分别...

35640
来自专栏zaking's

用js来实现那些数据结构15(图01)

21040
来自专栏数据结构与算法

BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

49660
来自专栏从流域到海域

图(Graph)的常用代码集合

图的相关概念请查阅离散数学图这一章或者数据结构中对图的介绍。代码来自课本。 /*Graph存储结构*/ //邻接矩阵表示法 #define MAX_VERTEX...

39660
来自专栏尾尾部落

[剑指offer] 跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

9820
来自专栏mathor

搜索(1)

 在讨论图的遍历问题之前,我们先来讨论一下图的存储问题,也就是我们在写程序的时候如何保存、表示一个图。首先我们会用连续的整数编号来表示点集。比如1号顶点、2号顶...

14010
来自专栏算法与数据结构

数据结构 图

1-1 无向连通图至少有一个顶点的度为1 错误: 无向连通图考点: 1. 每条边连接两个顶点,所有顶点的度之和等于边数的2倍 2.记住两个特殊的无相连通图模型:...

45870

扫码关注云+社区

领取腾讯云代金券