Python 图系列之基于邻接矩阵实现广度、深度优先路径搜索算法

在计算机科学中，图是一种数据结构，用于表示对象及其之间的关系。邻接矩阵是表示图的一种常用方法，其中矩阵的行和列表示图中的节点，矩阵中的值表示节点之间的关系。广度优先搜索（BFS）和深度优先搜索（DFS）是两种常用的图搜索算法，用于在图中查找路径或遍历图。
一、广度优先搜索（BFS）
广度优先搜索是一种按照层次顺序搜索图的算法。它从图的根节点开始，探索所有相邻节点，然后继续探索下一层的节点。BFS使用队列数据结构来实现。下面是一个基于邻接矩阵实现BFS的Python代码示例：

# 定义邻接矩阵
graph = [[0, 1, 1, 0, 0],
          [1, 0, 0, 1, 0],
          [1, 0, 0, 1, 1],
          [0, 1, 1, 0, 1],
          [0, 0, 1, 1, 0]]
# BFS函数
def bfs(graph, start):
    visited = [False] * len(graph)
    queue = [start]
    visited[start] = True
    while queue:
        vertex = queue.pop(0)
        print(vertex, end=' ')
        for i in range(len(graph[vertex])):
            if graph[vertex][i] == 1 and not visited[i]:
                visited[i] = True
                queue.append(i)