python的图结构graph

67 2025-01-09 19:52

在Python中，图结构是一种非常重要的数据结构，用于表示对象之间的关系。图由节点（顶点）和边组成，边可以是有向的也可以是无向的，还可以有权重。以下是几种常见的Python图结构实现方式：

一、使用字典实现无向图

Python复制

class Graph:
    def __init__(self):
        self.graph = {}

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, u, v):
        if u not in self.graph:
            self.add_vertex(u)
        if v not in self.graph:
            self.add_vertex(v)
        self.graph[u].append(v)
        self.graph[v].append(u)  # 无向图，所以要添加两次

    def print_graph(self):
        for vertex in self.graph:
            print(vertex, "->", self.graph[vertex])

# 示例
g = Graph()
g.add_vertex("A")
g.add_vertex("B")
g.add_edge("A", "B")
g.add_edge("A", "C")
g.print_graph()

输出：

复制

A -> ['B', 'C']
B -> ['A']
C -> ['A']

在这个例子中，我们用字典graph来存储图。字典的键是顶点，值是一个列表，列表中存储与该顶点相邻的顶点。通过add_vertex方法添加顶点，add_edge方法添加边。由于是无向图，所以在添加边时，需要在两个顶点的邻接列表中都添加对方。

二、使用字典实现有向图

Python复制

class DirectedGraph:
    def __init__(self):
        self.graph = {}

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, u, v):
        if u not in self.graph:
            self.add_vertex(u)
        if v not in self.graph:
            self.add_vertex(v)
        self.graph[u].append(v)  # 有向图，只需在起点的邻接列表中添加终点

    def print_graph(self):
        for vertex in self.graph:
            print(vertex, "->", self.graph[vertex])

# 示例
dg = DirectedGraph()
dg.add_vertex("A")
dg.add_vertex("B")
dg.add_edge("A", "B")
dg.add_edge("B", "C")
dg.print_graph()

输出：

复制

A -> ['B']
B -> ['C']
C -> []

这个有向图的实现方式与无向图类似，区别在于添加边时，只在起点的邻接列表中添加终点，不需要在终点的邻接列表中添加起点。

三、使用邻接矩阵实现图

Python复制

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]

    def add_edge(self, u, v):
        if u >= 0 and u < self.vertices and v >= 0 and v < self.vertices:
            self.graph[u][v] = 1
            self.graph[v][u] = 1  # 无向图

    def print_graph(self):
        for row in self.graph:
            print(row)

# 示例
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.print_graph()

输出：

复制

[0, 1, 1, 0]
[1, 0, 0, 0]
[1, 0, 0, 0]
[0, 0, 0, 0]

邻接矩阵是一个二维数组，大小为顶点数×顶点数。如果顶点i和顶点j之间有边，则graph[i][j]和graph[j][i]（对于无向图）为1，否则为0。这种方式适合顶点数相对固定且较少的图，因为矩阵可能会占用大量空间。

四、使用图库（如networkx）

Python复制

import networkx as nx
import matplotlib.pyplot as plt

# 创建无向图
G = nx.Graph()
G.add_node("A")
G.add_node("B")
G.add_edge("A", "B")
G.add_edge("A", "C")

# 绘制图
nx.draw(G, with_labels=True)
plt.show()

# 获取图的信息
print("节点：", G.nodes())
print("边：", G.edges())

输出：

复制

节点： ['A', 'B', 'C']
边： [('A', 'B'), ('A', 'C')]

networkx是一个功能强大的Python图库，可以方便地创建、操作和绘制图。它支持多种类型的图，包括无向图、有向图、加权图等，并且提供了丰富的图算法，如最短路径、最小生成树等。通过matplotlib库可以将图可视化显示出来。

在实际应用中，可以根据具体需求选择合适的图结构实现方式。如果图的规模较小且结构相对简单，使用字典或邻接矩阵可能更方便；如果需要处理复杂的图操作和分析，使用专业的图库如networkx会更加高效和便捷。

graph = { 'A': {'B': 2, 'D': 8}, 'B': {'A': 2, 'D': 5, 'E': 6}, 'C': {'E': 9, 'F': 3}, 'D': {'A': 8, 'B': 5, 'E': 3, 'F': 2}, 'E': {'B': 6, 'C': 9, 'D': 3, 'F': 1}, 'F': {'C': 3, 'D': 2, 'E': 1} }

这个graph字典表示的是一个加权无向图。图中的每个顶点（节点）都是一个键，而每个键对应的值是一个字典，表示与该顶点相邻的顶点以及它们之间的边的权重。

例如，'A': {'B': 2, 'D': 8}表示顶点A与顶点B之间有一条边，权重为2，与顶点D之间也有一条边，权重为8。由于这是一个无向图，所以如果A到B的权重是2，那么B到A的权重也是2，这在字典中也得到了体现（例如，'B': {'A': 2, ...}）。

解析图结构

顶点（节点）：图中的顶点有A、B、C、D、E、F。
边（连接）：图中的边以及它们的权重如下：
- A - B，权重为2
- A - D，权重为8
- B - D，权重为5
- B - E，权重为6
- C - E，权重为9
- C - F，权重为3
- D - E，权重为3
- D - F，权重为2
- E - F，权重为1

可视化图

如果想将这个图可视化，可以使用networkx库和matplotlib库来绘制：

Python复制

import networkx as nx
import matplotlib.pyplot as plt

# 创建一个无向图
G = nx.Graph()

# 添加边和权重
edges = [
    ('A', 'B', 2), ('A', 'D', 8), ('B', 'D', 5), ('B', 'E', 6),
    ('C', 'E', 9), ('C', 'F', 3), ('D', 'E', 3), ('D', 'F', 2),
    ('E', 'F', 1)
]
G.add_weighted_edges_from(edges)

# 绘制图
pos = nx.spring_layout(G)  # 为图设置布局
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=500, font_size=15)
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)

plt.show()

这段代码会创建一个无向图，并将图中的边和权重添加进去，然后使用spring_layout布局算法来排列图中的节点，最后绘制出图并显示权重标签。

应用场景

这种加权无向图可以用于各种实际问题，例如：

交通网络：顶点可以代表城市或路口，边可以代表道路，权重可以代表距离或行驶时间。
社交网络：顶点可以代表人，边可以代表朋友关系，权重可以代表关系的密切程度。
通信网络：顶点可以代表通信节点，边可以代表通信线路，权重可以代表线路的带宽或延迟。

在这些场景中，可以使用图算法来解决各种问题，例如最短路径问题（如Dijkstra算法）、最小生成树问题（如Kruskal算法或Prim算法）等。

博客

python的图结构graph

一、使用字典实现无向图

二、使用字典实现有向图

三、使用邻接矩阵实现图

四、使用图库（如networkx）

解析图结构

可视化图

应用场景

全部评论

分类

热门文章

Tags

关于