0

Добрый день. У меня возникла следующая задача: Задан граф матрицей смежности. Необходимо найти в нём любой цикл, который проходит через две вершины и два ребра.

Я пытался сделать так: запускаю поиск в глубину от одной из требуемых вершин цикла, проверяю их на смежность сперва с рёбрами, а затем со второй вершиной. Каждую найденную вершину. Однако у меня не получается правильно реализовать это.

Прошу подсказать, как можно исправить следующий код (Edge - структура для ребра):

public void FindCycle(int vFirst, int vSecond, Edge eFirst, Edge eSecond)
{
    nRez[i++] = vFirst;
    //смежно с началом 1 ребра
    if (nMatr[vFirst, eFirst.Begin] == 1 && !Edge1 && !nRez.Contains(eFirst.Begin))
    {
        nRez[i++] = eFirst.Begin;
        nRez[i++] = eFirst.End;
        Edge1 = true;
        FindCycle(eFirst.End, vSecond, eFirst, eSecond);
    }
    //смежн с концом 1 ребра
    else if (nMatr[vFirst, eFirst.End] == 1 && !Edge1 && !nRez.Contains(eFirst.End))
    {
        nRez[i++] = eFirst.End;
        Edge1 = true;
        FindCycle(eFirst.End, vSecond, eFirst, eSecond);
    }
    //смежно с началом 2 ребра
    else if (nMatr[vFirst, eSecond.Begin] == 1 && !Edge2 && !nRez.Contains(eSecond.Begin))
    {
        nRez[i++] = eSecond.Begin;
        //nRez[i++] = eSecond.End;
        Edge2 = true;
        FindCycle(eSecond.End, vSecond, eFirst, eSecond);
    }
    //смежно с концом 2 ребра
    else if (nMatr[vFirst, eSecond.End] == 1 && !Edge2 && !nRez.Contains(eSecond.End))
    {
        //   nRez[i++] = eSecond.End;
        Edge2 = true;
        FindCycle(eSecond.End, vSecond, eFirst, eSecond);
    }
    //смежно со второй вершиной
    else if (nMatr[vFirst, vSecond] == 1 && !Vertex2 && !nRez.Contains(vSecond))
    {
        // nRez[i++] = vSecond;
        Vertex2 = true;
        FindCycle(eFirst.End, vSecond, eFirst, eSecond);
    }
    //хотим замкнуть
    else if (nMatr[vFirst, nRez[0]] == 1 && Edge1 && Edge2 && Vertex2)
    {
        GraphCycleFoundException e = new GraphCycleFoundException();
        nRez[i++] = nRez[0];
        throw e;
    }
    //нет ничего из вышеперечисленного: пускаем в ближайшую смежную, отличную от начальной
    else
    {
        for (int j = 0; j < nDimension; j++)
            if (!nRez.Contains(j) && nMatr[vFirst, j] == 1)
                FindCycle(j, vSecond, eFirst, eSecond);
    }

1 ответ 1

1

Извините, не читал ваш код (его же много!). Я бы предложил следующий алгоритм:

  1. Найти путь из первой заданной вершины во вторую через первое заданное ребро; если такого пути нет, задача невыполнима.
  2. Найти путь из первой заданной вершины во вторую через второе заданное ребро; если такого пути нет, задача невыполнима.
  3. Обратить второй путь, соединить с первым, это и будет цикл

Для того, чтобы найти путь из первой заданной вершины во вторую через некоторое ребро, используем следующую подпрограмму:

  1. Найти какой-то путь из первой заданной вершины в первую вершину ребра и какой-то путь из второй вершины ребра во вторую заданную вершину; если пути нашлись, склеить их в результат и выйти
  2. Найти какой-то путь из первой заданной вершины во вторую вершину ребра и какой-то путь из первой вершины ребра во вторую заданную вершину; если пути нашлись, склеить их в результат и выйти
  3. Иначе, такого пути нет

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

Ваш ответ

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

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