Как проверить связность графа между двумя вершинами

Question

Я пытаюсь реализовать генетический алгоритм, чтобы найти набор ребер, удаление которых приведет к отключению графа. Чтобы быть более конкретным, я использую ориентированный ациклический граф, состоящий из вершин и ребер. Каждое ребро имеет стоимость или вес. Генетический алгоритм генерирует множество множеств C (то есть выбирает некоторые ребра между двумя вершинами). Теперь моя проблема состоит в том, чтобы проверить, представляет ли этот набор ребер набор вырезов или отключить график. Затем генетический алгоритм ищет возможную минимальную сумму затрат на ребра, включенную в набор сокращений.

Итак, я использовал этот метод, называемый «Тестирование связанного графа», взятый из книги «Java-библиотека алгоритмов и оптимизации графов», для проверки связности. Это не работает для меня, потому что это сканирует только для соседа вершин.

public static boolean isConnected(Individual ind)
{
    int n= Settings.numOfNodes;
    int m= Settings.numOfEdges-ind.cutSet.size();
    int nodei[]= new int[m+1];
    int nodej[]= new int[m+1];

    int tempi[]= new int[m];
    int tempj[]= new int[m];

    int[] temp= (int[])Settings.nodei.clone();

    for(int edg:ind.cutSet)
        temp[edg]= -1;

        int count=0;
        for(int i=0; i<Settings.numOfEdges; i++)
    {
       if(temp[i]!=-1)
      {
        tempi[count]=Settings.nodei[i];
        tempj[count]=Settings.nodej[i];            
        count++;
      }
   }
    nodei[0]=0;
    nodej[0]=0;
    for(int i=0; i<tempi.length;i++)
       {
          nodei[i+1]=tempi[i];
          nodej[i+1]=tempj[i]; 
       }



    int i,j,k,r,connect;
    int neighbor[] = new int[m + m + 1];
    int degree[] = new int[n + 1];
    int index[] = new int[n + 2];
    int aux1[] = new int[n + 1];
    int aux2[] = new int[n + 1];
    for (i=1; i<=n; i++)
    degree[i] = 0;
    for (j=1; j<=m; j++) {
         degree[nodei[j]]++;
         degree[nodej[j]]++;
    }
    index[1] = 1;
    for (i=1; i<=n; i++) {
        index[i+1] = index[i] + degree[i];
        degree[i] = 0;
    }
    for (j=1; j<=m; j++) {
        neighbor[index[nodei[j]] + degree[nodei[j]]] = nodej[j];
        degree[nodei[j]]++;
        neighbor[index[nodej[j]] + degree[nodej[j]]] = nodei[j];
        degree[nodej[j]]++;
    }
    for (i=2; i<=n; i++)
         aux1[i] = 1;
         aux1[1] = 0;
         connect = 1;
         aux2[1] = 1;
         k = 1;
         while (true) {
              i = aux2[k];
              k--;
              for (j=index[i]; j<=index[i+1]-1; j++) {
                    r = neighbor[j];
                    if (aux1[r] != 0) {
                       connect++;
                    if (connect == n) {
                       connect /= n;
                    if (connect == 1) return true;
                       return false;
                    }
                    aux1[r] = 0;
                    k++;
               aux2[k] = r;
         }
    }
        if (k == 0) {

    connect /= n;
    if (connect == 1) return true;
    return false;
    }
    }
  }   

С учетом следующего ориентированного ациклического графа:

number of vertices = 4
number of edges = 5
1->2
1->3
1->4
2->4
3->4

Если убрать следующие ребра:

1->2
1->3
2->4

Затем метод возвращает, что этот граф отключен, пока существует путь между:

1->4

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

Пример допустимого набора, который при удалении графика НЕ ​​подключен:

1->2
1->3
1->4

или

2->4
1->4
3->4

Пожалуйста, я открыт для любых мыслей или идей по решению этой проблемы.

Спасибо

Answer 1

Проверка подключения:

Ваш график направлен ациклично, поэтому вы можете предварительно обработать и найти Paths = { (u,v) | there is a path from u to v }.

После удаления / добавления каждого ребра (u,v) все, что вынужно сделать это сброс Paths соответственно.Обратите внимание, что для каждого v', (u,v') находится в Paths тогда и только тогда, когда существует u', такое, что (u,u') все еще является ребром в вашем графике, а (u',v') находится в Paths.
Не забудьте рекурсивно вызывать модификацию Paths для каждого из родителей u.
Хотя это решение не лучше, чем BFS в худшем случае, оно должно быть лучше в среднем случае - поскольку вам не нужно исследовать весь график после каждого изменения.

Редактировать:пример
Например, на вашем графике Path={(1,2),(1,3),(1,4),(2,4),(3,4)} - есть путь ко всем вершинам ко всем "прямым" вершинам, кроме от 2 до 3.
Теперь, если вы удалите ребро (1,4), выget Path={(1,2),(1,3),(1,4),(2,4),(3,4)} Обратите внимание, что (1,4) все еще там, потому что есть ребро (1,2) и (2,4) в Path.
Теперь удалите (2,4), это приведет к: Path={(1,2),(1,3),(1,4),(3,4)}.Опять же, (1,4) по-прежнему в, потому что (1,3) по-прежнему край, а (3,4) в Path.
Теперь удалите (3,4).От 3 до 4 не осталось пути, поэтому вы удалите (3,4).Теперь рекурсивно измените всех родителей 3.Поскольку 1 является родителем 3, вызовите его для него, и вы обнаружите, что больше нет ребер (1,u), так что (u,4) все еще находится в пути, поэтому мы удаляем его из Path, в результате чегоPath={(1,2),(1,3)}.

Поиск набора ребер для удаления:

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