图论算法代码

angetenar / 2023-08-24 / 原文

当参加数学建模竞赛时，图论算法是一个常用的解决方案之一。以下是一个使用Python实现的深度优先搜索（DFS）算法示例，用于遍历图的所有节点：

点击查看代码

class Graph:
    def __init__(self):
        self.adjacency_list = {}
    
    def add_edge(self, u, v):
        if u not in self.adjacency_list:
            self.adjacency_list[u] = []
        if v not in self.adjacency_list:
            self.adjacency_list[v] = []
        
        self.adjacency_list[u].append(v)
        self.adjacency_list[v].append(u)
    
    def dfs(self, start_vertex):
        visited = set()
        self._dfs_helper(start_vertex, visited)
    
    def _dfs_helper(self, vertex, visited):
        visited.add(vertex)
        print(vertex)
        
        neighbors = self.adjacency_list[vertex]
        for neighbor in neighbors:
            if neighbor not in visited:
                self._dfs_helper(neighbor, visited)

# 创建图对象
graph = Graph()

# 添加边
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('B', 'E')
graph.add_edge('C', 'F')
graph.add_edge('C', 'G')

# 从指定节点开始进行深度优先搜索
start_vertex = 'A'
graph.dfs(start_vertex)

在上述代码中，我们实现了一个Graph类，其中包括了添加边、深度优先搜索等方法。你可以根据具体问题的要求进行以下修改：

1.添加边：通过调用add_edge(u, v)方法添加图中的边，其中u和v是边的两个节点。

2.深度优先搜索：通过调用dfs(start_vertex)方法进行深度优先搜索，其中start_vertex是指定的起始节点。

3.在深度优先搜索算法中，我们使用了一个集合visited来记录已经访问过的节点，防止重复访问。在每次访问一个节点时，我们先将其标记为已访问，并输出节点的值。然后，遍历该节点的邻居节点，如果邻居节点没有被访问过，则递归调用_dfs_helper(neighbor, visited)方法继续访问邻居节点及其后续节点。

注意，以上代码仅为深度优先搜索算法的示例，实际问题可能需要更多的自定义代码和参数调整，请根据具体情况进行相应的修改。在图论算法中，还有其他许多常用的算法，如广度优先搜索、最短路径算法、最小生成树算法等，你可以根据具体需求选择适当的算法进行实现。