在无向图中查找所有桥边？ （代码无效）

Question

我正在学习图表中的桥梁。

我有以下 C# 代码（在 fiddle - https://dotnetfiddle.net/XQEEdy 中也可用）：

using System;
using System.Collections.Generic;

public class Program
{
    public class Graph
    {
        private int[,] adjMatrix;

        public Graph(int vertices)
        {
            adjMatrix = new int[vertices, vertices];
        }

        public int[,] AdjMatrix
        {
            get
            {
                return adjMatrix;
            }
        }

        public void AddEdge(int source, int destination)
        {
            adjMatrix[source, destination] = 1;
            adjMatrix[destination, source] = 1;
        }
    }

    public static HashSet<Tuple<int, int>> Bridges(Graph graph)
    {
        var visited = new HashSet<int>();
        var bridges = new HashSet<Tuple<int, int>>();
        var ids = new Dictionary<int, int>();
        var lowLinkValues = new Dictionary<int, int>();
        var parent = -1;
        var id = 0;

        for (int i = 0; i < graph.AdjMatrix.GetLength(0); i++)
        {
            if (visited.Contains(i))
            {
                continue;
            }

            Dfs(i, parent, id, bridges, ids, lowLinkValues, visited, graph.AdjMatrix);
        }

        return bridges;
    }

    private static void Dfs(
        int vertex,
        int parent,
        int id,
        HashSet<Tuple<int, int>> bridges,
        Dictionary<int, int> ids,
        Dictionary<int, int> lowLinkValues,
        HashSet<int> visited,
        int[,] adjMatrix)
    {
        visited.Add(vertex);
        ids.Add(vertex, id);
        lowLinkValues.Add(vertex, id);
        id++;

        for (int i = 0; i < adjMatrix.GetLength(0); i++)
        {
            if (parent == i)
            {
                continue;
            }

            if (!visited.Contains(i))
            {
                parent = vertex;
                Dfs(i, parent, id, bridges, ids, lowLinkValues, visited, adjMatrix);

                if (ids[vertex] < lowLinkValues[i])
                {
                    bridges.Add(Tuple.Create(vertex, i));
                }
                else
                {
                    lowLinkValues[vertex] = Math.Min(lowLinkValues[vertex], lowLinkValues[i]);
                }
            }
            else
            {
                lowLinkValues[vertex] = Math.Min(lowLinkValues[vertex], ids[i]);
            }
        }
    }

    public static void Main()
    {
        // Adjacency Matrix:
        var g = new Graph(11);

        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(0, 3);
        g.AddEdge(0, 4);
        g.AddEdge(4, 2);
        g.AddEdge(3, 5);
        g.AddEdge(4, 6);
        g.AddEdge(6, 3);
        g.AddEdge(6, 7);
        g.AddEdge(6, 8);
        g.AddEdge(7, 9);
        g.AddEdge(9, 10);
        g.AddEdge(8, 10);

        // bridges should be: 0--1, 3--5
        // but bridges collection is empty
        var bridges = Bridges(g);

        foreach (var bridge in bridges)
        {
            Console.WriteLine(bridge.Item1);
            Console.WriteLine(bridge.Item2);
            Console.WriteLine("\n");
        }
    }
}

我比较了代码：https://github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/graphtheory/BridgesAdjacencyList.java

我没有看到任何真正的区别，但我仍然没有得到任何回报。绘制图形，看起来 edge(0,1) 和 edge(3,5) 应该是桥梁 - 因为删除边将意味着 1 和 5 将与图形断开连接。

同样，如果我使用 github link 中的相同测试用例，我也不会返回任何桥。

我显然遗漏了一些东西，但我无法找到它可能是什么。有人看到我的代码有什么问题吗？

Answer 1

问题似乎是您没有实施实际的 depth-first 搜索，尽管这似乎是您使用名称 Dfs 的意图。 depth-first 搜索从某个顶点开始，并以 depth-first 方式跟随该顶点的所有边（在查看下一个 child 之前跟随第一个 child 的所有边）。

然而，您的算法查看每个节点并简单地将 parent 定义为当前节点，因此它并不是真正的搜索，它只是按数字顺序查看每个节点。您的代码的简化版本（伪代码）：

Dfs(Vertex current):
  mark current as visited
  for each Vertex v in the graph:
    if v is not visited: 
      Dfs(v)

请注意，称为 "current" 的顶点与图中检查的顶点之间没有关系。相反，算法应该更像这样：

Dfs(Vertex current, Vertex parent):
  mark current as visited
  for each Vertex v in the graph:
    if v is not visited: 
      if v shares an edge with current:
        Dfs(v)

我将把它留作练习，供您弄清楚如何修补算法以解决此问题。可能还有其他问题。发现第一个问题后我就停止了。