Python如何自定义邻接表图类
作者:夜空下的凝视 发布时间:2021-01-12 04:41:43
Python自定义邻接表图类
图抽象数据类型(ADT)的术语
顶点(Vertex):也称节点(node),是图的基础部分。具有名称标识“key”。顶点也可以有附加信息项“playload”。
边(Edge):也称弧(arc),也是图的基础组成部分。如果一条边连接两个顶点,则表示两者具有联系。边可以是单向的,也可以是双向的。如果图中的边都是单向的,则称这个图是“有向图(directed graph/digraph)”。
权重(Weight):为了表达从一个顶点到另一个顶点的“代价”,可以给边赋权。
路径(Path):图中的路径,是由边依次连接起来的顶点序列。无权路径的长度为边的数量。带权路径的长度为所有边的权重之和。
圈(Cycle):有向图里的圈是首尾顶点相同的路径。没有圈的图称为“无圈图(acyclic graph)”,没有圈的有向图称为“有向无圈图(directed acyclic graph 或 DAG)”。
实现图的两个著名方法:邻接矩阵(adjacency matrix)和邻接表(adjacency list)。
邻接矩阵和邻接表的优缺点
二维矩阵中,每行和每列都代表图中的顶点。如果顶点v到顶点w之间有边相连,则将值储存在矩阵的v行、w列。每一格的值代表了从顶点v到顶点w边的权重。
邻接矩阵的优点:是简单,然而,大部分的矩阵是空的,这种情况则称矩阵是“稀疏”的。矩阵并不是一个储存稀疏数据的有效途径。
实现稀疏图的更高效方法是使用邻接表(adjacency list)。
在这个实现方法中,包含一个含有所有顶点的主列表(master list),主列表中的每个顶点,再关联一个与自身有边连接的所有顶点的列表。
在实现顶点类的方法中使用字典而不是列表,字典中的键(key)对应顶点,值(value)则保存顶点连接边的权重。
邻接表的优点:是能高效地表示一个稀疏图。邻接表还能很容易的找到某个顶点与其他顶点的所有连接。
自定义顶点类
class Vertex(object):
# 初始化顶点
def __init__(self, key):
self.id = key #初始化顶点的键
self.connectedTo = {}#初始化顶点的值
# 添加邻居顶点,参数nbr是邻居顶点的键,默认权重为0
def addNeighbor(self, nbr, weight=0):
self.connectedTo[nbr] = weight
def __str__(self):
return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])
# 获取该顶点所有邻居顶点的键
def getConnections(self):
return self.connectedTo.keys()
# 获取顶点的键
def getId(self):
return self.id
# 获取到某邻居顶点的权重
def getWeight(self, nbr):
return self.connectedTo[nbr]
# 自定义图类
class Graph(object):
# 初始化图
def __init__(self):
self.vertList = {}#初始化邻接表
self.numVertices = 0 #初始化顶点数
# 添加顶点
def addVertex(self, key):
newVertex = Vertex(key)#创建顶点
self.vertList[key] = newVertex #将新顶点添加到邻接表中
self.numVertices = self.numVertices + 1 #邻接表中顶点数+1
return newVertex
# 获取顶点
def getVertex(self, n):
if n in self.vertList:#若待查询顶点在邻接表中,则
return self.vertList[n] #返回该顶点
else:
return None
# 使之可用in方法
def __contains__(self, n):
return n in self.vertList
# 添加边,参数f为起始顶点的键,t为目标顶点的键,cost为权重
def addEdge(self, f, t, cost=0):
if f not in self.vertList:#起始顶点不在邻接表中,则
self.addVertex(f) #添加起始顶点
if t not in self.vertList:#目标顶点不在邻接表中,则
self.addVertex(t)#添加目标顶点
self.vertList[f].addNeighbor(self.vertList[t], cost)#在邻接表中添加起始点的目标点及权重
# 获取邻接表中所有顶点的键
def getVertices(self):
return self.vertList.keys()
# 迭代显示邻接表的每个顶点的邻居节点
def __iter__(self):
return iter(self.vertList.values())
g = Graph() #实例化图类
for i in range(6):
g.addVertex(i) #给邻接表添加节点
print(g.vertList)#打印邻接表
g.addEdge(0, 1, 5) #给邻接表添加边及权重
g.addEdge(0, 5, 2)
g.addEdge(1, 2, 4)
g.addEdge(2, 3, 9)
g.addEdge(3, 4, 7)
g.addEdge(3, 5, 3)
g.addEdge(4, 0, 1)
g.addEdge(5, 4, 8)
g.addEdge(5, 2, 1)
for v in g: #循环每个顶点
for w in v.getConnections(): #循环每个顶点的所有邻居节点
print("(%s, %s)" % (v.getId(), w.getId())) #打印顶点和其邻居节点的键
结果为:
{0: <__main__.Vertex object at 0x00000000021BF828>, 1: <__main__.Vertex object at 0x00000000021BF860>, 2: <__main__.Vertex object at 0x00000000021BF898>, 3: <__main__.Vertex object at 0x00000000021BF8D0>, 4: <__main__.Vertex object at 0x00000000021BF908>, 5: <__main__.Vertex object at 0x00000000021BF940>}
(0, 1)
(0, 5)
(1, 2)
(2, 3)
(3, 4)
(3, 5)
(4, 0)
(5, 4)
(5, 2)
python图的邻接表表示
我就废话不多说了,上代码
"""图的邻接表表示"""
class GraphNode(object):
"""节点类"""
def __init__(self,_elem=None):
self._elem = _elem # 数据域
self._next = None # 指针域
class Graph(object):
"""图类"""
def __init__(self):
"""初始化一个序列"""
self._graph = []
def createPeak(self,newNode):
"""创建一个图顶点"""
self._graph.append(newNode)
return self._graph
def createSide(self):
"""创建图的边"""
for node in self._graph:
graphNode = node
print(f"请输入{graphNode._elem}的邻接点,以-1结束")
while True:
_graphNode = GraphNode() # 初始化每个节点的邻接点
end = input("请输入: ")
if end == '-1':
self.printGraph()
break
else:
"""临时列表图中的节点值,用来后续判断"""
temp = []
for item in self._graph:
temp.append(item._elem)
if end not in temp:
"""输入的邻接节点不在顶点中"""
print("输入的节点不属于图中的顶点,重新输入")
continue
elif end == graphNode._elem:
"""输入的顶点就是当前顶点"""
print("输入的是当前节点,重新输入")
continue
else:
# 新建节点
_graphNode._elem = end
# 指针向后移
_graphNode._next = graphNode._next
graphNode._next = _graphNode
graphNode = graphNode._next
def printGraph(self):
"""遍历当前节点列表"""
for node in self._graph:
print(f"顶点{node._elem}的邻接链表: ",end='')
while node != None:
if node._next != None:
print(f'{node._elem}-->',end='')
else:
print(f'{node._elem}', end='')
node = node._next
print() # 换节点,换行
if __name__ == '__main__':
count = int(input('请输入顶点个数: '))
s = Graph()
# 创建节点
peakNodeStr = input('请输入顶点: ')
peakNodes = peakNodeStr.split(' ')
# 将输入的节点实例化之后添加到图的链表中
for peakNode in peakNodes:
peak = GraphNode(peakNode)
s.createPeak(peak)
print('图中的节点:',end='')
for peak in s._graph:
print(peak._elem,end=' ')
print()
# 创建边
s.createSide()
来源:https://blog.csdn.net/qq_38882327/article/details/89328198
猜你喜欢
- 接触python已有一段时间了,下面针对python基础知识的使用做一完整梳理:1)避免‘\n'等特殊字符的两种方式:a)利用转义字
- 前言……最近在学习yolo1、yolo2和yolo3,写这篇博客主要是为了让自己对yolo2的结
- 前言本文主要是用 cpu 版本的 tensorflow 2.1 搭建深度学习模型,完成对电影评论的情感分类任务。 本次实践的数据来源于IMD
- 介绍:pyenv-virtualenv是pyenv的一个插件,作用如同virtualenv一样,是用来管理虚拟环境的,配合pyenv主体使用
- 在过去的十年中,MySQL已经成为广受欢迎的数据库,而WordPress博客使用的是MySQL数据库,虽然使用插件可以解决一些问题,但是实现
- 1、选取最适用的字段属性MySQL可以很好的支持大数据量的存取,但是一般说来,数据库中的表越小,在它上面执行的查询也就会越快。因此,在创建表
- python3字符串操作 x = 'abc' y = 'defgh' print(x + y)
- setup.py:#!/usr/bin/env python# coding=utf-8from distutils.core import
- 一般事件事件浏览器支持描述onClickIE3|N2|O3鼠标点击事件,多用在某个对象控制的范围内的鼠标点击onDblClickIE4|N4
- 为了自定义一个模板标签,你需要告诉Django当遇到你的标签时怎样进行这个过程。当Django编译一个模板时,它将原始模板分成一个个 节点
- 在python中,可以把for循环写在一行,生成一个新的列表,使用起来非常方便,下面举几个简单例子体会一下。1.简单的for...[if].
- python-----从本地摄像头和网络摄像头截取图片 ,具体代码如下所示:import cv2# 获取本地摄像头# folder_path
- 需求在使用django admin时希望后台的Textarea多行文本框可以按yaml格式编写,数据库保存为Text文本类型,字段和接口中读
- 一、前情提要最近在写一个项目,需要用到子线程,但是我们小学二年级就学过操作系统, 线程的执行是由系统的CPU调度算法所决定的,调度算法按照一
- 一、面向对象三大特征之继承python三大特征:封装、继承、多态三者中继承最为核心,实际应用多,感受较为直观封装和多态略微抽象1、继承的概念
- 好多网友问起来,·深度学习网址导航·深度学习整站系统 的后台管理能否增加批量删除功能,如何加:就是列出N篇文章或网址信息,每篇文章或网址前有
- 注意:这种方法十分受光线变化影响自己在家拿着手机瞎晃的成果图:源代码:# -*- coding: utf-8 -*- ""
- 基本开发环境· Python 3.6· Pycharm相关模块使用目标网页分析输入想看的小说内容,点击搜索这里会返回很多结果,我只选择第一个
- 当然有其它工具可以做这件事,但如果客户不允许你在服务器乱装东西时这个脚本就会有用了。 代码如下:DECLARE @tbImportTable
- aspImage是ServerObjects站点上非常好的一个组件,它可以使我们利用Asp实现很多对于图形的处理功能,他的功能强大,如果你需