在无向图中寻找圆

Question

我写了一个小函数，它应该在给定的（无方向的）图中找到一个圆，returns如果找到圆则为真，否则为假。

def dfs(v,last):
    if vis[v] == True:
        return True
    vis[v] = True
    c = False
    for el in adj[v]:
         if el == last:
             adj[v].remove(el)
         else:
             c = c or dfs(el,v)
    return c

邻接表是一个字典，如下所示：adj ={1: [2], 2: [1,3], 3: [2]}。另一个字典是检查结是否被访问过。 vis = {1: False, 2: False, 3: False} 我遇到的问题是它似乎适用于示例中的给定列表但对于其他人它给了我一个错误的结果（例如：adj = {1: [2,4], 2: [1,5], 4: [1,5], 5:[2,4]} 你能帮我解决这个问题或者告诉我如何找到解决这个问题的更好方法吗？我不想导入任何其他模块。

Answer 1

问题出在删除语句中。尝试以下操作：

def dfs(v,last):
    if v in vis:
        return True
    vis.append(v)
    c = False
    current_adj_list = list(adj[v])
    for el in current_adj_list:
        if el == last:
            adj[el].remove(v)
        else:
            c = c or dfs(el,v)
    return c

adj = {1: [2,4], 2:[1,5,4], 4: [1,2], 5: [2]}
vis = []

print(dfs(1,None))

说明：您正在删除从当前访问节点到它的后继节点的边。因此，在循环中，您从同一个列表中一遍又一遍地删除同一个元素。但是，您确实想从后继者中删除边。因此，

adj[v].remove(el)

成为

adj[el].remove(v)

其次，我们需要用

复制邻接表

current_adj_list = list(adj[v])

因为我们在递归中更深入地编辑列表，更改元素的顺序，从而（可能）破坏更高递归级别的循环。

在无向图中寻找圆

Finding a circle in an undirected graph

geometry

graph

find

python-3.x