Python数据结构与算法之图的基本实现及迭代器实例详解

图是一种非常重要的数据结构，它可以用于表示各种实际问题，如社交网络、路线规划等。本文将详细讲解Python中图的基本实现及迭代器实例，包括图的表示、遍历、最短路径等操作。

图的表示

图可以用邻接矩阵或邻接表来表示。邻接矩阵是一个二维数组，其中每个元素表示两个顶点之间是否有边。邻接表是一个字典，其中每个键表示一个顶点，对应的值是一个列表，表示与该顶点相邻的顶点。

以下是使用邻接表表示图的示例代码：

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

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

    def add_edge(self, vertex1, vertex2):
        if vertex1 in self.vertices and vertex2 in self.vertices:
            self.vertices[vertex1].append(vertex2)
            self.vertices[vertex2].append(vertex1)

    def remove_vertex(self, vertex):
        if vertex in self.vertices:
            del self.vertices[vertex]
            for v in self.vertices:
                if vertex in self.vertices[v]:
                    self.vertices[v].remove(vertex)

    def remove_edge(self, vertex1, vertex2):
        if vertex1 in self.vertices and vertex2 in self.vertices:
            if vertex2 in self.vertices[vertex1]:
                self.vertices[vertex1].remove(vertex2)
            if vertex1 in self.vertices[vertex2]:
                self.vertices[vertex2].remove(vertex1)

上述代码中，定义了一个Graph类，包含添加顶点、添加边、删除顶点、删除边等方法。使用字典vertices来表示图，其中每个键表示一个顶点，对应的值是一个列表，表示与该顶点相邻的顶点。

图的遍历

图的遍历有两种方式：深度优先遍历和广度优先遍历。深度优先遍历是从一个顶点开始，沿着一条路径访问到底，然后回溯到上一个顶点，再访问另一条路径，直到遍历完整个图。广度优先遍历是从一个顶点开始，先访问它的所有邻居，然后再访问邻居的邻居，直到遍历完整个图。

以下是使用深度优先遍历和广度优先遍历遍历图的示例代码：

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

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

    def add_edge(self, vertex1, vertex2):
        if vertex1 in self.vertices and vertex2 in self.vertices:
            self.vertices[vertex1].append(vertex2)
            self.vertices[vertex2].append(vertex1)

    def remove_vertex(self, vertex):
        if vertex in self.vertices:
            del self.vertices[vertex]
            for v in self.vertices:
                if vertex in self.vertices[v]:
                    self.vertices[v].remove(vertex)

    def remove_edge(self, vertex1, vertex2):
        if vertex1 in self.vertices and vertex2 in self.vertices:
            if vertex2 in self.vertices[vertex1]:
                self.vertices[vertex1].remove(vertex2)
            if vertex1 in self.vertices[vertex2]:
                self.vertices[vertex2].remove(vertex1)

    def dfs(self, start):
        visited = set()
        stack = [start]
        while stack:
            vertex = stack.pop()
            if vertex not in visited:
                visited.add(vertex)
                stack.extend(self.vertices[vertex] - visited)
        return visited

    def bfs(self, start):
        visited = set()
        queue = [start]
        while queue:
            vertex = queue.pop(0)
            if vertex not in visited:
                visited.add(vertex)
                queue.extend(self.vertices[vertex] - visited)
        return visited

上述代码中，定义了一个Graph类，包含深度优先遍历和广度优先遍历方法。使用集合visited来记录已经访问过的顶点，使用列表stack或队列queue来记录待访问的顶点。在深度优先遍历中，使用栈来实现，先访问一个顶点，然后将其邻居入栈，直到栈为空。在广度优先遍历中，使用队列来实现，先访问一个顶点，然后将其邻居入队，直到队列为空。

最短路径

最短路径是指两个顶点之间的最短路径，可以使用Dijkstra算法或Bellman-Ford算法来求解。Dijkstra算法是一种贪心算法，从起点开始，每次选择距离最近的顶点进行扩展，直到扩展到终点。Bellman-Ford算法是一种动态规划算法，通过多次松弛操作，逐步缩小起点到终点的距离。

以下是使用Dijkstra算法求解最短路径的示例代码：

import heapq

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

    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = {}

    def add_edge(self, vertex1, vertex2, weight):
        if vertex1 in self.vertices and vertex2 in self.vertices:
            self.vertices[vertex1][vertex2] = weight
            self.vertices[vertex2][vertex1] = weight

    def remove_vertex(self, vertex):
        if vertex in self.vertices:
            del self.vertices[vertex]
            for v in self.vertices:
                if vertex in self.vertices[v]:
                    del self.vertices[v][vertex]

    def remove_edge(self, vertex1, vertex2):
        if vertex1 in self.vertices and vertex2 in self.vertices:
            if vertex2 in self.vertices[vertex1]:
                del self.vertices[vertex1][vertex2]
            if vertex1 in self.vertices[vertex2]:
                del self.vertices[vertex2][vertex1]

    def dijkstra(self, start, end):
        distances = {vertex: float('inf') for vertex in self.vertices}
        distances[start] = 0
        pq = [(0, start)]
        while pq:
            current_distance, current_vertex = heapq.heappop(pq)
            if current_distance > distances[current_vertex]:
                continue
            for neighbor, weight in self.vertices[current_vertex].items():
                distance = current_distance + weight
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    heapq.heappush(pq, (distance, neighbor))
        return distances[end]

上述代码中，定义了一个Graph类，包含添加顶点、添加边、删除顶点、删除边和Dijkstra算法等方法。使用字典vertices来表示图，其中每个键表示一个顶点，对应的值是一个字典，表示与该顶点相邻的顶点和边的权重。在Dijkstra算法中，使用堆优化的方式来实现，先将起点入堆，然后每次取出距离最近的顶点进行扩展，直到扩展到终点。

迭代器实例

Python中的迭代器是一种访问集合元素的方式，可以用于遍历图中的顶点。以下是使用迭代器遍历图的示例代码：

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

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

    def add_edge(self, vertex1, vertex2):
        if vertex1 in self.vertices and vertex2 in self.vertices:
            self.vertices[vertex1].append(vertex2)
            self.vertices[vertex2].append(vertex1)

    def remove_vertex(self, vertex):
        if vertex in self.vertices:
            del self.vertices[vertex]
            for v in self.vertices:
                if vertex in self.vertices[v]:
                    self.vertices[v].remove(vertex)

    def remove_edge(self, vertex1, vertex2):
        if vertex1 in self.vertices and vertex2 in self.vertices:
            if vertex2 in self.vertices[vertex1]:
                self.vertices[vertex1].remove(vertex2)
            if vertex1 in self.vertices[vertex2]:
                self.vertices[vertex2].remove(vertex1)

    def __iter__(self):
        return iter(self.vertices)

上述代码中，定义了一个Graph类，包含添加顶点、添加边、删除顶点、删除边和迭代器等方法。在迭代器中，使用Python内置的iter函数和next函数来实现，先返回字典vertices的迭代器，然后每次调用next函数返回下一个顶点。

总结

本文详细讲解了Python中图的基本实现及迭代器实例，包括图的表示、遍历、最短路径等操作。图是一种非常重要的数据结构，可以用于表示各种实际问题，如社交网络、路线规划等。Python中，可以使用字典或列表等数据结构来表示图，实现程上述所示。通过示例看到图在实际应用中的灵活性和实用性。