引言

在数据结构的学习中，我们需要一定的基础和思维，在这里做一定的总结，并分享一下自己的经验

数组

数组的操作在数据结构中最为常见，也最需要理解和记忆

构建一个数组

1
2
3
4
# 一维数组
a = [0]*n 
# 二维数组
b = [[0]*n for _ in range(n)]

1
2
3
4
5
6
7
8
9
10
11
12
13

a = [1,2,3]
n = len(a)
ans = []
# 正序
for i in range(n): 
    for j in range(1,n-i+1):
        ans.append(a[i:i+j])
# 倒序
for i in range (n,0,-1):
     for j in range (n-i+1):
         ans.append(a[i-1:i+j])
return ans

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def permute(nums):  
    def backtrack(first=0):  
        # 所有数都填完了  
        if first == n:    
            output.append(nums[:])  
        for i in range(first, n):  
            # 动态维护数组  
            nums[first], nums[i] = nums[i], nums[first]  
            # 继续递归填下一个数  
            backtrack(first + 1)  
            # 撤销操作  
            nums[first], nums[i] = nums[i], nums[first]  
  
    n = len(nums)  
    output = []  
    backtrack()  
    return output

图

构建一个图

在数据结构中，图（Graph）是一种非常基础且强大的数据结构，用于表示节点（也称为顶点）之间的连接关系。图可以分为无向图和有向图，还可以进一步分为加权图和非加权图。在这里，我将提供一个基本的指南，介绍如何使用Python构建一个简单的无向图。

图的表示

图主要有两种表示方法：邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。

  1. 邻接矩阵：
    邻接矩阵是一个二维数组（或列表的列表），其中矩阵的大小等于图中顶点的数量。如果顶点i和顶点j之间存在边，则矩阵的[i][j]位置为1（或边的权重，如果是有权图的话）；如果不存在边，则为0。这种表示方法简单直观，但可能非常浪费空间，特别是在稀疏图中。

  2. 邻接表：
    邻接表是一个数组（或列表），其中每个元素都是一个列表，该列表包含所有与相应顶点直接相连的顶点。对于加权图，列表中的元素可以是包含顶点和权重的元组。这种方法在空间上通常比邻接矩阵更高效，特别是对于稀疏图。

Python 示例：使用邻接表构建无向图

下面是一个使用邻接表在Python中构建无向图的简单示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = {i: [] for i in range(num_vertices)}

    def add_edge(self, u, v):
        # 因为是无向图，所以要在两个方向上都添加边
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

    def remove_edge(self, u, v):
        # 注意：这个实现假设每条边只被添加一次
        self.adj_list[u].remove(v)
        self.adj_list[v].remove(u)

    def print_graph(self):
        for i in range(self.num_vertices):
            print(f"Vertex {i}: {self.adj_list[i]}")

# 示例使用
g = Graph(5)  # 创建一个包含5个顶点的图
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)

g.print_graph()

这个例子中，Graph 类使用一个字典 adj_list 来存储邻接表，其中键是顶点，值是与该顶点直接相连的顶点列表。add_edge 方法用于向图中添加边，注意无向图需要在两个方向上都添加边。remove_edge 方法用于移除边，但需要注意确保每条边只被添加了一次，否则移除时可能会引发错误。print_graph 方法用于打印图的邻接表表示。

希望这个示例能够帮助你理解如何在Python中使用邻接表构建无向图。类似地，你也可以根据需要修改这个类来支持有向图或加权图。

拓扑序列

在数据结构中，拓扑序列是针对有向无环图（Directed Acyclic Graph, DAG）的一种顶点线性排序，它满足对于图中的每一条有向边 (u, v)，顶点 u 都出现在顶点 v 的前面。这种排序只存在于有向无环图中，因为如果存在环，则无法找到一个满足上述条件的线性序列。

拓扑排序的算法

常见的拓扑排序算法有两种：

  1. Kahn算法：基于入度的排序算法。

    • 初始化所有顶点的入度（即有多少条边指向该顶点）。
    • 将所有入度为0的顶点放入一个队列中。
    • 当队列非空时，执行以下步骤：
      • 从队列中取出一个顶点，将其添加到拓扑排序的结果中。
      • 遍历该顶点的所有邻接点，将它们的入度减1。
      • 如果某个邻接点的入度减为0，则将其加入队列中。
    • 如果排序结果中的顶点数小于图中的顶点总数，则说明图中存在环，无法进行拓扑排序。

  2. DFS（深度优先搜索）算法：基于DFS的逆后序排序。

    • 对每个未访问的顶点进行DFS遍历。
    • 在完成DFS遍历一个顶点时（即回溯时），将该顶点添加到拓扑排序的结果序列的开头（或结尾，取决于具体实现，但通常是开头以模拟逆后序）。
    • 由于DFS的特性，它会在访问完一个顶点的所有邻接点之后才回溯到该顶点，因此保证了拓扑排序的正确性。

Python 示例（Kahn算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from collections import deque, defaultdict

def topological_sort_kahn(graph):
    # graph 是邻接表表示的图
    in_degree = defaultdict(int)
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    queue = deque()
    for node in graph:
        if in_degree[node] == 0:
            queue.append(node)
    
    top_order = []
    while queue:
        u = queue.popleft()
        top_order.append(u)
        for neighbor in graph[u]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    if len(top_order) == len(graph):
        return top_order
    else:
        return None  # 存在环，无法进行拓扑排序

# 示例图
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

print(topological_sort_kahn(graph))  # 输出 ['A', 'B', 'C', 'D'] 或 ['A', 'C', 'B', 'D'] 等有效拓扑排序

这个例子中，我们使用了一个字典 in_degree 来记录每个顶点的入度，并用一个队列 queue 来存放所有入度为0的顶点。然后，我们不断从队列中取出顶点，并将其添加到拓扑排序的结果中，同时更新其邻接点的入度。如果最终拓扑排序的结果中的顶点数与图中的顶点总数相同，则说明图中不存在环，排序成功；否则，说明图中存在环，无法进行拓扑排序。