Найти все ребра моста в неориентированном графе? (Код не работает) - PullRequest
Новая
       60

Найти все ребра моста в неориентированном графе? (Код не работает)

0 голосов
/ 24 февраля 2020

Я узнаю о мостах на графиках.

У меня есть следующий код C# (также доступен в скрипте - 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 я тоже не получаю никаких мостов.

Я явно что-то упускаю, но я не смог понять, что это может быть. Кто-нибудь видит, в чем проблема с моим кодом?

1 Ответ

1 голос
/ 24 февраля 2020

Похоже, проблема в том, что вы не реализовали фактический поиск в глубину, хотя, похоже, это ваше намерение с именем Dfs. Поиск в глубину начинается с некоторой вершины и следует за всеми ребрами из этой вершины в порядке глубины (следует за всеми ребрами от первого потомка, прежде чем смотреть на следующий потомок).

Однако ваш алгоритм выглядит на каждом узле и просто определяет родителя в качестве текущего узла, так что он на самом деле не ищет, он просто просматривает каждый узел в числовом порядке. Упрощенная версия вашего кода (в псевдокоде): 

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

Обратите внимание, что нет никакой связи между вершиной, называемой "текущей", и вершинами, проверенными на графике. Вместо этого алгоритм должен быть примерно таким: 

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)

Я оставлю это в качестве упражнения для вас, чтобы выяснить, как исправить ваш алгоритм для решения этой проблемы. Могут быть и другие проблемы. Я остановился, как только нашел первую проблему.

...