Python 算法基础篇：图的基本概念和表示方法

小蓝枣

发布于 2023-07-25 15:53:39

7400

发布于 2023-07-25 15:53:39

Python 算法基础篇：图的基本概念和表示方法

引言

图是计算机科学中的一种重要数据结构，它是由节点和边组成的集合，用于表示物体之间的关系。本篇博客将重点介绍图的基本概念和表示方法，包括有向图、无向图、带权图的概念，以及邻接矩阵和邻接表两种常用的图表示方法，并通过实例代码演示图的创建和基本操作，每行代码都配有详细的注释。

😃😄 ❤️ ❤️ ❤️

1. 图的基本概念

在计算机科学中，图是由节点（顶点）和边组成的集合，用于表示物体之间的关系。节点表示物体，边表示物体之间的连接关系。

图可以分为有向图和无向图，有权图和无权图：

有向图：图中的边有方向，从一个节点指向另一个节点。如 A -> B 表示从 A 到 B 的有向边。
无向图：图中的边没有方向，表示节点之间的双向关系。如 A-B 表示 A 和 B 之间的无向边。
有权图：图中的边有权值，表示节点之间的距离或者代价。如 A -> B ( 5 )表示从 A 到 B 的边权为 5 。
无权图：图中的边没有权值，表示节点之间的关系没有数值上的区别。

图是解决许多实际问题的有效工具，例如社交网络中的好友关系、路网中的交通流量、任务调度中的依赖关系等。

2. 图的表示方法

在计算机中，图可以通过两种主要的方式进行表示：邻接矩阵和邻接表。

2.1 邻接矩阵表示法

邻接矩阵是一个二维数组，用来表示图中节点之间的连接关系。对于无向图来说，邻接矩阵是对称的，因为 A 与 B 相连等价于 B 与 A 相连。对于有向图，邻接矩阵不一定是对称的。

下面是一个示例图和其对应的邻接矩阵表示：

示例图：
   A---B
   |  /
   | /
   C

邻接矩阵表示：
   A B C
A  0 1 1
B  1 0 1
C  1 1 0

在邻接矩阵中，矩阵的行和列分别代表图中的节点，矩阵元素 matrix[i][j] 表示节点 i 和节点 j 之间是否有边连接。如果有边连接，那么矩阵元素的值通常为 1 ，否则为 0 。

2.2 邻接表表示法

邻接表是一种更加节省空间的图表示方法，它使用一个字典或者数组来存储每个节点及其相邻节点的列表。

下面是一个示例图和其对应的邻接表表示：

示例图：
   A---B
   |  /
   | /
   C

邻接表表示：
{
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B']
}

在邻接表中，字典的键代表图中的节点，对应的值为一个列表，包含了与该节点相邻的节点。

3. 图的创建和基本操作

在 Python 中，我们可以使用字典来表示邻接表，使用嵌套列表来表示邻接矩阵。下面我们通过示例代码来演示图的创建和基本操作。

首先，我们定义一个图类 Graph ，包含两个私有属性： _graph_dict 用于表示邻接表， _directed 用于表示是否为有向图。

class Graph:
    def __init__(self, directed=False):
        self._graph_dict = {}
        self._directed = directed

然后，我们实现添加节点和边的方法。对于无向图，当添加节点时，我们只需在邻接表中添加一个键为节点，值为空列表的项。当添加边时，我们需要同时在两个节点的值中添加对方。对于有向图，只需在起始节点的值中添加终止节点。

    def add_node(self, node):
        if node not in self._graph_dict:
            self._graph_dict[node] = []

    def add_edge(self, from_node, to_node):
        self.add_node(from_node)
        self.add_node(to_node)
        self._graph_dict[from_node].append(to_node)
        if not self._directed:
            self._graph_dict[to_node].append(from_node)

接下来，我们实现获取图中所有节点和边的方法。

    def nodes(self):
        return list(self._graph_dict.keys())

    def edges(self):
        edges = []
        for node in self._graph_dict:
            for neighbor in self._graph_dict[node]:
                edges.append((node, neighbor))
        return edges

最后，我们实现打印图的方法。

    def __str__(self):
        result = "Graph:\n"
        for node in self._graph_dict:
            result += f"{node}: {self._graph_dict[node]}\n"
        return result

4. 示例和应用

现在我们来创建一个示例图，并进行基本操作。

# 创建一个无向图
graph = Graph()
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'C')
graph.add_edge('C', 'D')

# 打印图
print(graph)

# 获取所有节点和边
print("所有节点：", graph.nodes())
print("所有边：", graph.edges())

运行上述代码，输出结果如下：

Graph:
A: ['B', 'C']
B: ['A', 'C']
C: ['A', 'B', 'D']
D: ['C']
所有节点： ['A', 'B', 'C', 'D']
所有边： [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'D'), ('D', 'C')]