图的数据结构

作者: pdnbplus | 发布时间: 2024/07/13 | 阅读量: 124

# 图的数据结构 -- 潘登同学的图论笔记

@

节点数据结构

在数据结构中我们可以知道,图由节点和边构成,那么想实现图的数据结构就必然离不开节点Node,为了避免混淆,我的节点同一命名为Vertex

那么实现Vertex需要一些什么属性和方法呢?

  • 节点的名称
  • 节点的与什么节点连接以及连接的权值
  • 增加相邻节点(或者叫修改相邻节点的边权值)
  • 获得相邻节点(就是通过这个节点知道他的相邻节点是什么)
  • 获得节点名称(由Vertex对象获得自己的名称)
  • 获得相邻边数据(通过相邻的节点的名称知道他们之间的权值)
  • 显示设置(如果在命令行把Vertex输入, 显示的东西, 如果不写的话, 就会显示对象地址)
class Vertex:
    def __init__(self, key):
        self.id = key
        self.connectedTo = {}     # connectedTo用于储存相邻节点 key是相邻节点(对象而不是名称) value是连接权值

    def addNeighbor(self, nbr, weight=0):   # 增加相邻边,默认weight为0
        '''
        input:
            nbr: Vertex object
            weight: int
        return:
            None
        '''
        self.connectedTo[nbr] = weight

    def getConnections(self):   # 获得相邻节点
        '''
        input: None
        return: Vertex object
        '''
        return self.connectedTo.keys()

    def getId(self):   # 获得节点名称
        '''
        input: None
        return: key(str)
        '''
        return self.id

    def getWeight(self, nbr):   # 获得相邻边数据
        '''
        input: Vertex object
        return: weight(int)
        '''
        return self.connectedTo[nbr]

    def __str__(self):   # 显示设置(__str__是内置方法,也就是不需要显示的使用这个方法就可以用这个函数)
        return str(self.id) + 'connectTo:' + \
               str([x.id for x in self.connectedTo])


if __name__ == '__main__':
    # 与节点相关的数据, 链接表
    a_info = {'x1':['y3', 'y5']}
    # 新建节点
    x1 = Vertex('x1')
    y3 = Vertex('y3')
    y5 = Vertex('y5')
    # 根据邻接表添加相邻节点
    x1.addNeighbor(y3, 1)
    x1.addNeighbor(y5, 5)
    # 测试定义的函数功能
    # 获取节点id
    print(x1.getId())
    print(y5.getId())
    # 获取节点的相邻节点
    print(x1.getConnections())
    print(x1)
    # 由相邻节点获得与相邻节点的权值
    print(x1.getWeight(y5))

图数据结构

实现完节点了,接下来就是实现图了;

那么图的数据结构都包括什么呢?

  • 图的一种储存数据的方式就是邻接表,采取邻接表来储存节点
  • 图的节点个数
  • 在图中增加节点
  • 通过节点的key获得节点对象
  • 判断节点在不在图中(in 内置函数)
  • 新增两节点的边
  • 获取所有节点的名称
  • 迭代器的实现(通过for 循环把vertex对象取出)

话不多说 上代码!

import Vertex  # 导入上面写的代码
class Graph:
    def __init__(self):
        self.vertList = {}  # 这个虽然叫list但是实质上是字典
        self.numVertices = 0  # 记录节点个数

    def addVertex(self, key):   # 增加节点
        '''
        input: Vertex key (str)
        return: Vertex object
        '''
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)   # 创建新节点
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self, key):   # 通过key获取节点信息
        '''
        input: Vertex key (str)
        return: Vertex object
        '''
        if key in self.vertList:
            return self.vertList[key]
        else:
            return None

    def __contains__(self, n):  # 判断节点在不在图中
        '''
        input: Vertex key (str)
        return: bool
        '''
        return n in self.vertList

    def addEdge(self, from_key, to_key, cost=1):    # 新增边
        '''
        input:
            from_key: vertex key (str)
            to_key: vertex key (str)
            cost: int
        return:
            None
        '''
        if from_key not in self.vertList:      # 不再图中的顶点先添加
            self.addVertex(from_key)
        if to_key not in self.vertList:
            self.addVertex(to_key)
        # 调用起始顶点的方法添加邻边
        self.vertList[from_key].addNeighbor(self.vertList[to_key], cost)

    def getVertices(self):   # 获取所有顶点的名称
        return self.vertList.keys()

    def __iter__(self):  # 迭代取出
        return iter(self.vertList.values())  # 采用iter直接转成可迭代对象

    def __len__(self):  # 查看节点个数
        return self.numVertices

if __name__ == '__main__':
    # 邻接表
    g_dict ={'1':[['2', 10], ['3', 10]],
             '2':[['3', 2], ['4', 4], ['5', 8]],
             '3':[['5', 9]],
             '4':[['6', 10]],
             '5':[['4', 6], ['6', 10]]}
    # 创建graph对象
    g = Graph()
    # 在Graph中vertList的数据结构其实就是上面这个
    # 遍历g_dict
    for from_key in g_dict:
                for to_key in g_dict[from_key]:
                    g.addEdge(from_key, to_key[0], [0, to_key[1]])
    # 测试通过节点名称获取节点
    print(g.getVertex('3'))
    # 获得所有节点的名称
    print(g.getVertices())
    # 查看节点个数
    print(len(g))
    # 判断节点在不在图中
    print('7' in g, '3' in g)

OK!!, 现在我们已经成功实现了图的数据结构

细心的同学已经注意到了, 上面刚刚出现了邻接表这个词语, 当然总是跟他相提并论的还有邻接矩阵,我们先把这两个概念说清楚;

图的邻接表

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

在具体讲解邻接表存储图的实现方法之前,先普及一个"邻接点"的概念。在图中,如果两个点相互连通,即通过其中一个顶点,可直接找到另一个顶点,则称它们互为邻接点;

邻接指的是图中顶点之间有边或者弧的存在;

例如,存储图 1a) 所示的有向图,其对应的邻接表如图 1b) 所示:

邻接表

拿顶点 V1 来说,与其相关的邻接点分别为 V2 和 V3,因此存储 V1 的链表中存储的是 V2 和 V3 在数组中的位置下标 1 和 2;

简化起见

我喜欢把邻接表定义为一个字典, 字典的keys储存出发点, values是一个长度为 2 的list, list的第一个元素表示到达点, 第二个元素表示weight

  • 具体代码就是这样
# 邻接表
g_dict ={'1':[['2', 10], ['3', 10]],
     '2':[['3', 2], ['4', 4], ['5', 8]],
     '3':[['5', 9]],
     '4':[['6', 10]],
     '5':[['4', 6], ['6', 10]]}
'1':[['2', 10], ['3', 10]] 就表示顶点'1'出发到达顶点'2'的权值是10, 到达顶点'3'的权值是10;

图的邻接矩阵

图的邻接矩阵大家都很熟悉, 就是用一个矩阵来表示点与点之间的关系, 沿用上面邻接表的例子;

  • 具体长这样
import numpy as np
np.array([[0, 10, 10, np.inf, np.inf, np.inf],
          [np.inf, 0, 2, 4, 8, np.inf],
          [np.inf, np.inf, 0, np.inf, 9, np.inf],
          [np.inf, np.inf, np.inf, 0, np.inf, 10],
          [np.inf, np.inf, np.inf, 6, 0, 10],
          [np.inf, np.inf, np.inf, np.inf, np.inf, 0]])

邻接矩阵 好了!我们已经介绍完图的数据结构了, 那现在我们开始系统的学习图论吧!!