Python数据结构与算法——图

Stella981
• 阅读 587

图的定义

Python数据结构与算法——图

图(graph) 是由一些点(vertex) 和这些点之间的连线(edge) 所组成的;其中,点通常称为顶点(vertex),而点到点之间的连线通常称之为边或者弧(edge)。通常记为G=(V,E)。

要注意的是:线性表可以是空表,树可以是空树,图不可以是空图,图可以没有边,但是至少要有一个顶点。

图的术语

顶点

顶点⼜称节点,是图的基础部分。它可以有⾃⼰的名字,我们称作“键”。顶点也可以带有附加信息,我们称作“有效载荷”。

边是图的另⼀个基础部分。两个顶点通过⼀条边相连,表⽰它们之间存在关系。边既可以是单向的,也可以是双向的。如果图中的所有边都是单向的,我们称之为有向图 。

权重

边可以带权重,⽤来表⽰从⼀个顶点到另⼀个顶点的成本。例如在路线图中,从⼀个城市到另⼀个城市,边的权重可以表⽰两个城市之间的距离。

路径

无论是无向图还是有向图,从一个顶点到另一顶点途径的所有顶点组成的序列(包含这两个顶点),称为一条路径。

如果路径中第一个顶点和最后一个顶点相同,则此路径称为"环"(或"回路")。

Python数据结构与算法——图

图的实现

可以通过多种⽅式在Python中实现图的抽象数据类型。你会看到,在使⽤不同的表达⽅式来实现图的抽象数据类型时,需要做很多取舍。有两种⾮常著名的图实现,它们分别是邻接矩阵 和邻接表 。 本节会解释这两种实现,并且⽤Python类来实现邻接表。

邻接矩阵

要实现图,最简单的⽅式就是使⽤⼆维矩阵。在矩阵实现中,每⼀⾏和每⼀列都表⽰图中的⼀个顶点。第 V ⾏和第 W 列交叉的格⼦中的值表⽰从 顶点V 到 顶点W 的边的权重。如果两个顶点被⼀条边连接起来,就称它们是相邻的。

Python数据结构与算法——图

优点

简单。对于⼩图来说,邻接矩阵可以清晰地展⽰哪些顶点是相连的。

缺点

对于存储稀疏数据来说,矩阵并不⾼效。

邻接表

为了实现稀疏连接的图,更⾼效的⽅式是使⽤邻接表。在邻接表实现中,我们为图对象的所有顶点保存⼀个主列表,同时为每⼀个顶点对象都维护⼀个列表,其中记录了与它相连的顶点。在对Vertex 类的实现中,我们使⽤字典(⽽不是列表),字典的键是顶点,值是权重。

Python数据结构与算法——图

优点

能够紧凑地表⽰稀疏图。此外,邻接表也有助于⽅便地找到与某⼀个顶点相连的其他所有顶点。

图的代码实现

class Graph:

    def __init__(self):
        self.vertices = {}
        self.num_of_vertices = 0

    def add_vertex(self, key):
        new_vertex = Vertex(key)
        self.vertices[key] = new_vertex
        self.num_of_vertices = self.num_of_vertices + 1

        return new_vertex

    def get_vertex(self, n):
        if n in self.vertices:
            return self.vertices[n]
        return None

    def contains(self, n):
        return n in self.vertices

    def add_edge(self, f, t, cost=0):
        if f not in self.vertices:
            new_vertex = self.add_vertex(f)

        if t not in self.vertices:
            new_vertex = self.add_vertex(t)

        self.vertices[f].add_neighbor(self.vertices[t], cost)

    def get_vertices(self):
        return self.vertices.keys()

    def __iter__(self):
        return iter(self.vertices.values())


class Vertex:

    def __init__(self, key):
        self.id = key
        self.connect_to = {}

    def add_neighbor(self, nbr, weight=0):
        self.connect_to[nbr] = weight

    def __str__(self):
        return str(self.id) + "connect to" + str([x.id for x in self.connect_to])

    def get_id(self):
        return self.id

    def get_connections(self):
        return self.connect_to.keys()

    def get_weight(self, nbr):
        return self.connect_to[nbr]
点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Stella981 Stella981
2年前
Python3:sqlalchemy对mysql数据库操作,非sql语句
Python3:sqlalchemy对mysql数据库操作,非sql语句python3authorlizmdatetime2018020110:00:00coding:utf8'''
Stella981 Stella981
2年前
Python之time模块的时间戳、时间字符串格式化与转换
Python处理时间和时间戳的内置模块就有time,和datetime两个,本文先说time模块。关于时间戳的几个概念时间戳,根据1970年1月1日00:00:00开始按秒计算的偏移量。时间元组(struct_time),包含9个元素。 time.struct_time(tm_y
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
2个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这