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

下面是详细讲解“Python数据结构与算法之图的基本实现及迭代器实例详解”的完整攻略，包含两个示例说明。

图的基本实现

图是由节点和边组成的数据结构。在Python中，可以使用字典和集合来表示图。字典用于存储节点和它们的邻居，集合用于存储节点。

下面是一个简单的Python实现：

class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = {}

    def add_node(self, node):
        self.nodes.add(node)
        self.edges[node] = set()

    def add_edge(self, node1, node2):
        self.edges[node1].add(node2)
        self.edges[node2].add(node1)

    def neighbors(self, node):
        return self.edges[node]

Graph类有一个nodes属性，用于存储节点的集合，以及一个edges属性，用于存储节点和它们的邻居之间的边。

add_node方法用于向图中添加一个节点。它将节点添加到nodes集合中，并将其邻居集合添加到edges字典中。

add_edge方法用于向图中添加一条边。它将两个节点添加到彼此的邻居集合中。

neighbors方法用于获取一个节点的邻居集合。

迭代器实例详解

迭代器是一种用于遍历集合的对象。在Python中，可以使用iter函数和next方法来创建和使用迭代器。

下面是一个简单的Python迭代器实现：

class MyIterator:
    def __init__(self, data):
        self.data = data
        self.index = 0

    def __iter__(self):
        return self

    def __next__(self):
        if self.index >= len(self.data):
            raise StopIteration
        result = self.data[self.index]
        self.index += 1
        return result

MyIterator类有一个data属性，用于存储要遍历的数据，以及一个index属性，用于跟踪当前遍历的位置。

__iter__方法返回迭代器本身。

__next__方法返回下一个元素，并将index属性递增。如果已经遍历完所有元素，则抛出StopIteration异常。

下面是一个使用MyIterator类的示例：

my_list = [1, 2, 3, 4, 5]
my_iterator = MyIterator(my_list)
for item in my_iterator:
    print(item)

这将输出列表中的所有元素。

示例1：使用图实现深度优先搜索

让我们使用Graph类实现深度优先搜索算法：

def dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(graph.neighbors(node) - visited)
    return visited

dfs函数接受一个Graph对象和一个起始节点start，并返回从起始节点开始的深度优先遍历顺序。

该函数使用一个集合visited来存储已经访问过的节点，以及一个栈stack来存储待访问的节点。它从起始节点开始，将其添加到栈中，并循环直到栈为空。对于每个节点，它将其弹出栈，并将其添加到visited集合中。然后，它将该节点的未访问邻居添加到栈中。

下面是一个使用dfs函数的示例：

graph = Graph()
graph.add_node('A')
graph.add_node('B')
graph.add_node('C')
graph.add_node('D')
graph.add_edge('A', 'B')
graph.add_edge('B', 'C')
graph.add_edge('C', 'D')
graph.add_edge('D', 'A')

print(dfs(graph, 'A'))

这将输出从节点A开始的深度优先遍历顺序。

示例2：使用迭代器实现二叉树的中序遍历

让我们使用迭代器实现二叉树的中序遍历：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class InorderIterator:
    def __init__(self, root):
        self.stack = []
        self.current = root

    def __iter__(self):
        return self

    def __next__(self):
        while self.current or self.stack:
            if self.current:
                self.stack.append(self.current)
                self.current = self.current.left
            else:
                node = self.stack.pop()
                self.current = node.right
                return node.val
        raise StopIteration

root = TreeNode(1, TreeNode(2), TreeNode(3))
inorder_iterator = InorderIterator(root)
for val in inorder_iterator:
    print(val)

这将输出二叉树的中序遍历顺序。

希望这个攻略能够帮助你理解如何在Python中实现图和迭代器！