Python如何自定义邻接表图类

目录
  • Python自定义邻接表图类
    • 图抽象数据类型(ADT)的术语
    • 邻接矩阵和邻接表的优缺点
    • 自定义顶点类
  • python图的邻接表表示
  • 总结

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()

总结

以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • Python数据结构之图的存储结构详解

    一.图的定义 图是一种比树更复杂的一种数据结构,在图结构中,结点之间的关系是任意的,任意两个元素之间都可能相关,因此,它的应用极广.图中的数据元素通常被称为顶点 ( V e r t e x ) (Vertex) (Vertex), V V V是顶点的有穷非空集合, V R VR VR是两个顶点之间的关系的集合(可以为空),可以表示为图 G = { V , { V R } } G=\{V,\{VR\}\} G={V,{VR}}. 二.相关术语 2.1 无向图 给定图 G = { V , { E }

  • python实现邻接表转邻接矩阵

    目录 python邻接表转邻接矩阵 图的存储—邻接矩阵与邻接表 邻接矩阵 邻接表 入度与出度 书面练习 编程练习 总结 python邻接表转邻接矩阵 闲话少说,前段时间看到有同学问怎么把邻接表转成邻接矩阵,想了想做了一下,仅供参考.= = _python 2.7 _ 包:networkX,numpy # coding:utf-8 #将一个图,network转换为邻接矩阵 import networkx  as nx import numpy as np G = nx.read_weighted_

  • 如何基于python实现不邻接植花

    有 N 个花园,按从 1 到 N 标记.在每个花园中,你打算种下四种花之一. paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径. 另外,没有花园有 3 条以上的路径可以进入或者离开. 你需要为每个花园选择一种花,使得通过路径相连的任何两个花园中的花的种类互不相同. 以数组形式返回选择的方案作为答案 answer,其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类.花的种类用 1, 2, 3, 4 表示.保证存在答案. 示例 1: 输入:N = 3, p

  • Python如何自定义邻接表图类

    目录 Python自定义邻接表图类 图抽象数据类型(ADT)的术语 邻接矩阵和邻接表的优缺点 自定义顶点类 python图的邻接表表示 总结 Python自定义邻接表图类 图抽象数据类型(ADT)的术语 顶点(Vertex):也称节点(node),是图的基础部分.具有名称标识“key”.顶点也可以有附加信息项“playload”. 边(Edge):也称弧(arc),也是图的基础组成部分.如果一条边连接两个顶点,则表示两者具有联系.边可以是单向的,也可以是双向的.如果图中的边都是单向的,则称这个图

  • java实现图的邻接表存储结构的两种方式及实例应用详解

    前言 本篇来谈一谈图的邻接表实现的两种方式,首先我们明确一点"学会图的邻接表实现的关键点在于":你所建立的图的邻接表的对象是什么! 首先我们看一下<算法导论>中关于图的邻接表的定义: 图G=(V,E)的邻接表表示有一个包含 |V| 个列表的数组Adj所组成,其中每个列表对应于V中的一个顶点,对于每一个u∈V,邻接表Adj[u]包含所有满足条件(u,v)∈E的顶点v,亦即,Adj[u]包含图G中所有和顶点u相邻的顶点.(或者他也可能指向这些顶点的指针),每个邻接表中的顶点一般

  • 图的邻接表存储表示示例讲解

    复制代码 代码如下: //---------图的邻接表存储表示------- #include<stdio.h>#include<stdlib.h> #define MAX_VERTEXT_NUM 20 typedef int InfoType;typedef char VertextType; typedef struct ArcNode{    int adjvex;    struct ArcNode *nextArc;    InfoType *info;}ArcNode;

  • C++实现图的邻接表存储和广度优先遍历实例分析

    本文实例讲述了C++实现图的邻接表存储和广度优先遍历方法.分享给大家供大家参考.具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 0 2 0 3 2 3 2 4 1 4 输入结束(此行不必输入) 注:0 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示       0 2表示该图的第0个顶点和第2个定点有边相连,如上图中的a->c所示       2 3表示该图的

  • python迭代器自定义类的具体方法

    1.说明 迭代器还具有迭代用户定制类别的能力.迭代对象需要支持两种方式:_iter__()和next(),前者返回迭代本身,后者返回下一个元素. 2.实例 class example(object): def __init__(self,num): self.num=num def __iter__(self): return self def __next__(self): if self.num <= 0: raise StopIteration tmp = self.num self.nu

  • C语言邻接表建立图详解

    目录 有向图 无向图 邻接表存图进行拓扑排序 总结 有向图 代码: #include<stdio.h> #include<stdlib.h> #include<string.h> #include<stack> using namespace std; #define maxn 200 int v, e; //表结点 typedef struct _Enode { int ivex; //该边所指向的节点位置 int value;//如果边有权值的话,就对其

  • C语言算法积累图的遍历邻接表简单路径

    目录 题目: 思路: 代码: 题目: 假设图用邻接表表示,设计一个算法,输出从顶点Vi到Vj的所有简单路径 关键字: 图,邻接表,简单路径 思路: Vi=u,Vj=v 本题采用基于递归的深度优先遍历算法,从结点u出发,递归深度优先遍历图中各个结点,若访问到结点v,则输出该搜索路径上的结点. 为此,设置:一个path数组来存放路径上的结点(初始为空),d表示路径长度(初始为-1). 查找从顶点u到v 的简单路径过程说明如下 (假设查找函数名为FindPath()): 1)FindPath(G,u,

  • Java用邻接表存储图的示例代码

    目录 一.点睛 1.无向图 2.无向图的链接表 3.说明 4.无向图 二.邻接表的数据结构 1.节点 2.邻接点 三.算法步骤 四.实现 五.测试 一.点睛 邻接表是图的一种链式存储方法,其数据结构包括两部分:节点和邻接点. 用邻接表可以表示无向图,有向图和网.在此用无向图进行说明. 1.无向图 2.无向图的链接表 3.说明 节点 a 的邻接点是节点 b.d,其邻接点的存储下标为1.3,按照头插法(逆序)将其放入节点 a 后面的单链表中. 节点 b 的邻接点是节点 a.c.d,其邻接点的存储下标

  • python进阶之自定义可迭代的类

    自定义可迭代的类 列表可以获取列表的长度,然后使用变量i对列表索引进行循环,也可以获取集合的所有元素,且容易理解.没错,使用列表的代码是容易理解,也很好操作,但这是要付出代价的.列表之所以可以用索引来快速定位其中的任何一个元素,是因为列表是一下子将所有的数据都装载在内存中,而且是一块连续的内存空间.当数据量比较小时,实现比较容易:当数据量非常大时,会非常消耗内存资源.而迭代就不同,迭代是读取多少元素,就将多少元素装载到内存中,不读取就不装载.这有点像处理XML的两种方式:DOM和SAX.DOM是

随机推荐