0

введите сюда описание изображенияПомогите, пожалуйста, сделать алгоритм поиска всех путей между двумя вершинами (вершины не должны повторяться в путях), желательно на языке c#. Пример графа на картинке, каждое ребро имеет вес (w1-w4). Нужно, например, из 0-ой(самая левая) найти пути во 2-ую (самая правая). Для данного графа результатом должны быть две строки w1w2 и w3w2 (весы ребер).

В программе граф представляю в виде списка смежности.

Сделал класс, который хранит конечную вершину и длину пути в нее.

Данный граф у меня в программе описан так:

var graph = new List<List<Edge>>();
    var w1 = new Edge( 1, "W1");
    var w3 = new Edge( 1, "W3");

    var w2 = new Edge( 2, "W2");
    var w4 = new Edge( 1, "-W4");

    var w5 = new Edge(0, "-1");

    //0-ой элемент - нулевая вершина. Имеет путь в 1ую вершину длиной w1 (вершина w1) и в 1-ую вершину длиной w3 - вершина w3 и тд



 graph.Add(new List<Edge>() { w1, w3 } ); 
    graph.Add(new List<Edge>() { w2 });
    graph.Add(new List<Edge>() { w4, w5 });

Пытался сделать такую функцию для поиска путей, для данного графа работает, но если добавить вершины, то нет, на больше ума не хватило.

static List<string> ways = new List<string>();
    static string func = null;
    //<summary>
    // Ищет прямые пути X -> Y
    //</summary>
    static string FindDirectWays(List<List<Edge>> graph, int X, int Y)
    {
        //Х - номер начальной вершины
        // У - номер конечной вершины

        foreach(var vertex in graph[X])
        {

            if (vertex.Vertex == Y)
            {
                func += vertex.Value;
                ways.Add(func);
                return func;
            }



            else
            {
                func = vertex.Value;
                func += FindDirectWays(graph, vertex.Vertex, Y);

            }

        }

        return func;
    }
5
  • а какие есть ограничения на размер графа или его структуру? Вы понимаете, что количество путей растёт экспоненциально от размера графа?
    – pavel
    14 ноя 2019 в 20:41
  • я представляю схемы в виде графов, поэтому там будет мало вершин и мало таких путей) 14 ноя 2019 в 21:05
  • Алгоритм Дейкстры
    – Grundy
    14 ноя 2019 в 21:27
  • @Grundy , Дейкстра не поможет, человеку нужны ВСЕ маршруты, а не только кратчайшие.
    – Zealint
    15 ноя 2019 в 4:37
  • @Zealint, ага, я помнил формулировку про "все пути", а что там "все кратчайшие пути" пропустил :)
    – Grundy
    15 ноя 2019 в 7:43

1 ответ 1

1

Проще всего такие задачи (если вершин и правда не много) решать рекурсивно. Более того, если рёбер тоже не много, то сделать простенький "бутафорский" список смежности. Например, так: выделить матрицу А[n+1][m+1], где n - число вершин и m - число рёбер. В этом списке перечисляются КОНЦЫ рёбер следующим образом: в массиве A[i] лежат концы рёбер, выходящих из вершины i, а число 0 в списке будет обозначать конец списка (отсчёт вершин ведём от 1). В вашем случае матрица будет такой (нумерую вершины слева направо от 1):

A[1]={2, 2, 0};
A[2]={3, 0};
A[3]={1, 0};

Аналогично заводим матрицу W, где на соответствующих местах будут находиться веса рёбер, но только нули на конце уже не нужны:

W[1]={w1, w3};
W[2]={w2};
W[3]={w4};

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

function GO (int i) {
  Положить i в стэк S.
  if (i == конечная вершина) {
   вывести содержание стека S как вам нужно // Вывели очередной путь до конечной вершины.
   вытолкнуть из S верхнюю вершину
   return;
  }
  for (int k=0; A[i][k] != 0; ++k) {
    int j = A[i][k];  // Это вершина j, в которую мы можем перейти из i    
    GO (j);
  }
  вытолкнуть из S верхнюю вершину
  return;
}

Воспользоваться этой функцией очень просто. В коде главной функции пишем что-то вроде такого:

Сделать стэк S пустым;
int i = начальная вершина, с которой хотим вести обход;
GO(i);

Это классическая идея обхода графа всеми возможными способами, её можно легко модифицировать под любой ваш запрос. Но это вам предлагаю сделать уже самостоятельно. Подскажу только, что нужно. В цикле for МЕЖДУ строками int ... и GO ... нужно вставить ещё одну строку, которая добавляет вес W[i][k] в какой-нибудь другой стэк T, а после вызова GO(j) добавить строку, которая выталкивает из T верхний элемент.

5
  • в GO стоит и конечную вершину передавать, для более общего решения :)
    – Grundy
    15 ноя 2019 в 7:45
  • Да тут много ещё чего можно сделать. Например, я нигде не проверяю зацикливание, если будет петля на пути. Думаю, автор вопроса догадается сам как можно это проверить.
    – Zealint
    15 ноя 2019 в 8:49
  • спасибо) ну функция, которую я сам написал в вопросе по-сути та же самая, что и у вас, и я там как раз не знаю, как правильно со стуком работать. И она у меня работает для этого графа, но, если добавить еще одна вершину, то все ломается. А петель у меня точно не будет) 15 ноя 2019 в 16:33
  • Так вот я вам и предлагаю всё-таки найти разницу: почему у вас ломается, а у меня - нет?
    – Zealint
    15 ноя 2019 в 17:56
  • да, проверил, доработаю и, думаю, все будет отлично) спасибо 15 ноя 2019 в 19:52

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.