Python 中的图数据结构

Manav Narula 2023年1月30日 2022年5月17日
  1. 在 Python 中使用邻接表实现图
  2. 在 Python 中使用邻接矩阵实现图
Python 中的图数据结构

在编程中,图数据结构表示一组相互关联的对象。每个对象都称为顶点,链接称为边。

图示例

上图中,{A, B, C, D, E} 是顶点,集合用 V 符号表示。边的集合用 E 表示,在上面的例子中它是 {ad,ac,ab,cd,bd,be,de}

我们可以根据不同的标准对图表进行分类。首先,我们有基于方向的图。

这些是无向图和有向图。在无向图中,边没有方向。

这意味着边 abba 相同。对于每条边都有方向或方向的有向图则相反。

基于权重,我们有加权图和非加权图。加权图有一些与边相关的值。

还有一些特殊的图,如树、有向无环图等。由于它们的非线性特性,图在现实世界中有很多应用。

谷歌地图在他们的交通系统中使用图表,甚至 Facebook 也使用图表来可视化用户及其朋友列表。

在本教程中,我们将讨论用 Python 表示一个简单的图形。

在 Python 中使用邻接表实现图

邻接列表存储每个顶点及其相邻顶点以可视化图形。这可以使用字典来表示。

每个顶点都将是字典的键,键的对应值将包含列表中的相邻顶点。

adjacency_lst = {}
mylst = []

def graph_node(node):
  if node not in mylst:
    mylst.append(node)
  else:
    print("The given node exists")
 
def graph_edge(node1, node2):
  temp = []
  if node1 in mylst and node2 in mylst:
    if node1 not in adjacency_lst:
      temp.append(node2)
      adjacency_lst[node1] = temp
   
    elif node1 in adjacency_lst:
      temp.extend(adjacency_lst[node1])
      temp.append(node2)
      adjacency_lst[node1] = temp
       
  else:
    print("The given node does not exist")
 
def disp_graph():
  for node in adjacency_lst:
    print(node, " -> ", [i for i in adjacency_lst[node]])
 
graph_node('a')
graph_node('b')
graph_node('c')
graph_node('d')
graph_edge('a','b')
graph_edge('b','c')
graph_edge('c','d')
graph_edge('d','a')
disp_graph()
print(adjacency_lst)

输出:

a  ->  ['b']
b  ->  ['c']
c  ->  ['d']
d  ->  ['a']
{'a': ['b'], 'b': ['c'], 'c': ['d'], 'd': ['a']}

我们使用上面例子中的邻接表来实现一个简单的图。一开始,定义了 adjacency_lst 字典来存储节点和边。

graph_node() 函数将一个顶点添加到该字典并检查一个节点是否已经存在。我们使用 graph_edge() 函数添加边。

disp_graph() 函数通过显示节点的边缘来显示此图。

在 Python 中使用邻接矩阵实现图

我们可以使用矩阵来表示图。矩阵是二维数组。

在邻接矩阵中,特定行和列的值表示是否存在边。

如果 A[i][j] 为 0,则 ij 之间没有边。值为 1 表示边缘存在。

def graph_node(v):
    global graph
    global nodes_no
    global nodes
    if v in nodes:
        print("Node already exists")
    else:
        nodes_no = nodes_no + 1
    nodes.append(v)
    if nodes_no > 1:
        for vertex in graph:
            vertex.append(0)
    temp = []
    for i in range(nodes_no):
        temp.append(0)
    graph.append(temp)

def graph_edge(v1, v2, e):
    global graph
    global nodes_no
    global nodes
    if v1 not in nodes:
        print("Node ", v1, " does not exist.")
    elif v2 not in nodes:
        print("Node ", v2, " does not exist.")
    else:
        index1 = nodes.index(v1)
        index2 = nodes.index(v2)
        graph[index1][index2] = e

def disp_graph():
    global graph
    global nodes_no
    for i in range(nodes_no):
        for j in range(nodes_no):
            if graph[i][j] != 0:
                print(nodes[i], " -> ", nodes[j], "Weight for the edge: ", graph[i][j])

nodes = []
nodes_no = 0
graph = []
graph_node(1)
graph_node(2)
graph_node(3)
graph_node(4)
graph_edge(1, 2, 1)
graph_edge(1, 3, 1)
graph_edge(2, 3, 0)
graph_edge(3, 1, 2)
disp_graph()
print("Matrix Representation: ", graph)

输出:

1  ->  2 Weight for the edge:  1
1  ->  3 Weight for the edge:  1
3  ->  1 Weight for the edge:  2
Matrix Representation:  [[0, 1, 1, 0], [0, 0, 0, 0], [2, 0, 0, 0], [0, 0, 0, 0]]

在上面的例子中,我们使用邻接矩阵实现了一个图。我们维护图是一个名为 graph 的列表列表。

graph_node() 函数向图中添加一个顶点,并添加顶点之间的边。

使用 graph_edge() 函数。disp_graph() 显示矩阵中节点和边的表示。

Author: Manav Narula
Manav Narula avatar Manav Narula avatar

Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.

LinkedIn

相关文章 - Python Graph