Python：优化的深度优先搜索算法？

Question

我刚在Python上实现了深度优先搜索（DFS），但是我觉得这段代码可能不是最优的，因为倒数第三行的for循环让我有点担心。我知道这个DFS是可以工作的，但它真的优化了吗？下面附上了图的链接和代码。

graphx=[[1, 1, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 1, 0], [0, 0, 1, 1, 0, 0, 0, 0], [0, 0, 1, 1, 1, 0, 1, 0], [0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 1, 1], [0, 1, 0, 1, 0, 1, 1, 0], [0, 0, 0, 0, 0, 1, 0, 1]]
visited=[False]*len(graphx[0])
stack=[]

def dfs(graphx, a):
    stack.append(a)
    while len(stack)!=0:
        v=stack.pop()
        if visited[v]==False:
            visited[v]=True
            print(v)
            for w in range(len(graphx[0])):
                if graphx[v][w]!=0:
                    stack.append(w)

图的链接： https://i.stack.imgur.com/UcHqo.png

有人说这个算法的时间复杂度是O(n^2)，这可不好。怎么才能优化呢？

编辑：这个广度优先搜索（BFS）是否正确，基于原来的DFS的答案？

def bfs(G, start):
    """Perform bfs on adjacency list of graph
    G: Adjacency list representation of graph.
    start: Index of start node.
    """
    visited = [False] * len(G)
    queue = []
    queue.append(start)
    while queue:
        v = queue.pop()
        if not visited[v]:
            visited[v] = True
            print(v)
            for neighbor in G[v]:
                queue.insert(0, neighbor)

Answer 1

你的问题有点模糊，不太明确。优化代码可以做到很多，比如换一种编程语言来实现，所以你需要更清楚地说明你想知道什么。建议你把整个代码重写成C语言，可能不是你想要的答案。

不过，既然你在使用邻接矩阵来表示图，那么找到邻居节点的时间复杂度是和节点数量成正比的。如果你用的是邻接表，那么找到邻居节点的时间复杂度就和边的数量成正比了。如果图的边很少，这个差别就很重要。

一些关于Python的特别提示：

• 为什么用0和1？难道不应该用True和False吗？
• 每次你写“i in range(len(s))”时，可以考虑用“e in s”或者“i, e in enumerate(s)”来替代。
• 不要用“x==False”或者“x==True”来比较，而是直接用“not x”或者“x”。

Answer 2

你算法的主要问题在于，你把图用邻接矩阵的方式表示。对于V个节点，这样会导致运行时间是O(V^2)，因为你需要访问矩阵中的所有V^2个条目。

用邻接表来表示图会更高效（无论是运行时间还是内存使用）。它的运行时间是O(E)，其中E是边的数量。

# Run time is O(E) and not O(V^2)
# It visits each node and edge exactly once.
def dfs(G, start):
    """Perform dfs on adjacency list of graph
    G: Adjacency list representation of graph.
    start: Index of start node.
    """
    visited = [False] * len(G)
    stack = []
    stack.append(start)
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            print(v)
            for neighbor in G[v]:
                stack.append(neighbor)

# This is your code. Takes O(V^2) because you are visiting every entry in
# the adjacency matrix, which has V^2 entries.
def dfs_adjacency_mat(G, start):
    visited=[False]*len(G[0])
    stack=[]
    stack.append(start)
    while len(stack)!=0:
        v=stack.pop()
        if visited[v]==False:
            visited[v]=True
            print(v)
            for w in range(len(G[0])):
                if G[v][w]!=0:
                    stack.append(w)

def main():
    # Represent graph as adjacency list, not adjacency matrix
    G = [[1],       # Node 0 (A) has node 1 (B) as neighbor
        [0, 6],    # Node 1 (B) has node 0 (A) and 6 (G) as neighbor
        [3],
        [2, 4, 6],
        [3, 5],
        [4, 6, 7],
        [1, 3, 5],
        [5]]
    print("Using adjacency list")
    dfs(G, 0)  # Start dfs at node 0 (i.e., node A)

    print('-' * 50)

    print("Using adjacency matrix")
    # Adjacency matrix
    graphx = [[1, 1, 0, 0, 0, 0, 0, 0],
              [1, 1, 0, 0, 0, 0, 1, 0],
              [0, 0, 1, 1, 0, 0, 0, 0],
              [0, 0, 1, 1, 1, 0, 1, 0],
              [0, 0, 0, 1, 1, 1, 0, 0],
              [0, 0, 0, 0, 1, 1, 1, 1],
              [0, 1, 0, 1, 0, 1, 1, 0],
              [0, 0, 0, 0, 0, 1, 0, 1]]
    dfs_adjacency_mat(graphx, 0)


if __name__ == '__main__':
    main()

输出:

Using adjacency list
0
1
6
5
7
4
3
2
--------------------------------------------------
Using adjacency matrix
0
1
6
5
7
4
3
2