Python: DFS优化算法

Question

我刚刚在Python上实现了DFS;然而，我不认为这是最优化的代码可能由于第三至最后一行的for循环。我知道这个DFS是有效的;然而，它是优化的吗?图URL附在下面，以及代码。

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)时间，这很糟糕。如何优化?

编辑:基于对原始DFS的回答，这个BFS正确吗?

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

你的算法的关键问题是你用邻接矩阵来表示你的图。对于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

Answer 2

你的问题相当模糊和开放式。优化代码可以用不同的语言实现，因此您必须更精确地了解您实际想要知道的内容。建议你用C重写整个东西可能不是你想要的答案。

无论如何，由于您使用的是邻接矩阵，因此定位邻居在节点数量上是线性的。如果你有一个邻接表，你就可以在边的数量上实现线性。如果图是稀疏的，这是一个重要的区别。

一些python特有的注释:

• 为什么是0和1 ?这不应该是真和假吗?
• 当你执行"i in range(len(s))"时，请考虑"e in s"或"i, e in enumerate(s)"。
• 不要比较"x==False"或"x==True"，而只需使用"not x"或"x"。