首页 > 编程语言 >python | 算法-图的宽度优先遍历

python | 算法-图的宽度优先遍历

时间:2022-10-17 21:00:52浏览次数:55  
标签:__ 遍历 weight python graph self 算法 edges nodes

数据结构

# 参考: https://github.com/algorithmzuo/algorithmbasic2020/tree/master/src/class16

# 点结构的描述
class Node:
    def __init__(self, value):
        self.value = value
        self.in_num = 0 # 入度
        self.out_num = 0 # 出度
        self.nexts = [] # 邻接点
        self.edges = [] # 邻接边

# 边结构的描述
class Edge:
    def __init__(self, weight, n_from, n_to):
        self.weight = weight # 权重
        self.n_from = n_from # 起点
        self.n_to = n_to # 终点

# 图结构的描述
class Graph:
    def __init__(self):
        self.nodes = {} # 点集, 保存 点上值-点 的映射
        self.edges = [] # 边集, 保存所有边信息

class GraphGenerator:
    """
    这相当于一个接口函数,将各种条件统一转化为上面的图的结构,根据具体情况改写此类即可。
    """
    # 下面是一个例子
    # matrix -> 所有的边
    # N*3的矩阵
    # [weight, from节点上的值, to节点上的值]
    #
    # [5, 0, 7]
    # [3, 0, 1]
    #
    def createGraph(self, matrix):
        graph = Graph()
        for i in range(len(matrix)):
            weight = matrix[i][0]
            n_from = matrix[i][1]
            n_to = matrix[i][2]

            if n_from not in graph.nodes.keys():
                graph.nodes[n_from] = Node(n_from)

            if n_to not in graph.nodes.keys():
                graph.nodes[n_to] = Node(n_to)

            fromNode = graph.nodes[n_from] # 起点
            toNode = graph.nodes[n_to] # 终点
            edge = Edge(weight, n_from, n_to) # 记录下该边的信息
            fromNode.nexts.append(toNode) # 记录节点的邻接点信息
            fromNode.out_num += 1 # 更新起点的出度
            toNode.in_num += 1 # 更新终点的入度
            fromNode.edges.append(edge) # 更新节点邻接边的信息
            graph.edges.append(edge) # 更新图的边信息

        return graph

# test
m = [[5, 0, 7], [3, 0, 1]]

g = GraphGenerator()
graph = g.createGraph(m)

print(str(graph.nodes.keys()))
for i in range(len(graph.edges)):
    print(str([graph.edges[i].weight, graph.edges[i].n_from, graph.edges[i].n_to]))

# 输出结果
# dict_keys([0, 7, 1])
# [5, 0, 7]
# [3, 0, 1]

宽度优先算法

# 宽度优先遍历

class BFS:
    def bfs(self, start):
        if start is None: return
        que = [start]
        set = [start]
        while len(que) >0:
            cur = que.pop(0)
            print(cur.value)
            for next in cur.nexts:
                if next not in set:
                    set.append(next)
                    que.append(next)
# test:
m = [[3, 0, 1],
     [2, 0, 2],
     [4, 1, 2],
     [2, 1, 3]]
gen = GraphGenerator()
graph = gen.createGraph(m)
search = BFS()
print("从0开始,宽度优先搜索:")
search.bfs(graph.nodes[0])
# 输出结果:
# 从0开始,宽度优先搜索:
# 0
# 1
# 2
# 3

标签:__,遍历,weight,python,graph,self,算法,edges,nodes
From: https://www.cnblogs.com/ljdsbfj/p/16800650.html

相关文章

  • python爬虫从0到1 -Requests库的基本使用(get/post请求)
    文章目录​​前言​​​​(一)requests的get请求​​​​1.导入requests库​​​​2.定义url地址以及请求头​​​​3.返回响应数据​​​​4.将数据打印​​​​总结(对比......
  • Python list列表修改元素
    Python 提供了两种修改列表(list)元素的方法,你可以每次修改单个元素,也可以每次修改一组元素(多个)。修改单个元素修改单个元素非常简单,直接对元素赋值即可。请看下面的例子:......
  • Python list列表查找元素
    Python 列表(list)提供了index()和count()方法,它们都可以用来查找元素。index()方法index()方法用来查找某个元素在列表中出现的位置(也就是索引),如果该元素不存在,则......
  • Python dict字典基本操作(包括添加、修改、删除键值对)
    由于字典属于可变序列,所以我们可以任意操作字典中的键值对(key-value)。Python 中,常见的字典操作有以下几种:向现有字典中添加新的键值对。修改现有字典中的键值对。从现......
  • Python dict字典详解
    Python 字典(dict)是一种无序的、可变的序列,它的元素以“键值对(key-value)”的形式存储。相对地,列表(list)和元组(tuple)都是有序的序列,它们的元素在底层是挨着存放的。字典类型......
  • Python set集合详解
    Python 中的集合,和数学中的集合概念一样,用来保存不重复的元素,即集合中的元素都是唯一的,互不相同。从形式上看,和字典类似,Python集合会将所有元素放在一对大括号{}中,相邻......
  • Python dict字典方法完全攻略(全)
    我们知道,Python 字典的数据类型为dict,我们可使用 dir(dict) 来查看该类型包含哪些方法,例如:>>>dir(dict)['clear','copy','fromkeys','get','items','keys','po......
  • Python类型转换,Python数据类型转换函数大全
    虽然 Python 是弱类型编程语言,不需要像 Java 或C语言那样还要在使用变量前声明变量的类型,但在一些特定场景中,仍然需要用到类型转换。比如说,我们想通过使用print()......
  • Python转义字符及用法
    在《Python字符串》一节中我们曾提到过转义字符,就是那些以反斜杠\开头的字符。ASCII编码为每个字符都分配了唯一的编号,称为编码值。在 Python 中,一个ASCII字符除了可......
  • Python算术运算符及用法详解
    算术运算符也即数学运算符,用来对数字进行数学运算,比如加减乘除。下表列出了 Python 支持所有基本算术运算符。表1Python常用算术运算符运算符说明实例结果+加1......