Рубрики

Кратчайший цикл в неориентированном невзвешенном графике

Дан неориентированный невзвешенный граф. Задача — найти длину кратчайшего цикла в данном графике. Если цикла не существует, выведите -1.

Примеры:

Input:
Output: 4
Cycle 6 -> 1 -> 5 -> 0 -> 6

Input:
Output: 3
Cycle 6 -> 1 -> 2 -> 6

Пререквизиты : Диджикстра

Подход: для каждой вершины мы проверяем, возможно ли получить кратчайший цикл, включающий эту вершину. Сначала для каждой вершины вставьте текущую вершину в очередь, а затем ее соседей, и если вершина, которая уже посещена, возвращается снова, то цикл присутствует.

Примените описанный выше процесс для каждой вершины и получите длину самого короткого цикла.

Ниже приведена реализация вышеуказанного подхода:

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

#define N 100200

  

vector<int> gr[N];

  
// Функция для добавления ребра

void Add_edge(int x, int y)

{

    gr[x].push_back(y);

    gr[y].push_back(x);

}

  
// Функция для определения длины
// самый короткий цикл в графе

int shortest_cycle(int n)

{

    // Хранить длину кратчайшего цикла

    int ans = INT_MAX;

  

    // Для всех вершин

    for (int i = 0; i < n; i++) {

  

        // Сделать максимальное расстояние

        vector<int> dist(n, (int)(1e9));

  

        // Взять воображаемого родителя

        vector<int> par(n, -1);

  

        // Расстояние от источника до источника равно 0

        dist[i] = 0;

        queue<int> q;

  

        // Вставить исходный элемент

        q.push(i);

  

        // Продолжаем, пока очередь не пуста

        while (!q.empty()) {

  

            // Взять первый элемент

            int x = q.front();

            q.pop();

  

            // Пройдите через все это потомки

            for (int child : gr[x]) {

  

                // Если он еще не посещен

                if (dist[child] == (int)(1e9)) {

  

                    // Увеличить расстояние на 1

                    dist[child] = 1 + dist[x];

  

                    // Изменить родителя

                    par[child] = x;

  

                    // Вставляем в очередь

                    q.push(child);

                }

  

                // Если он уже посещен

                else if (par[x] != child and par[child] != x)

                    ans = min(ans, dist[x] + dist[child] + 1);

            }

        }

    }

  

    // Если график не содержит цикла

    if (ans == INT_MAX)

        return -1;

  

    // Если граф содержит цикл

    else

        return ans;

}

  
// Код драйвера

int main()

{

    // Количество вершин

    int n = 7;

  

    // Добавить ребра

    Add_edge(0, 6);

    Add_edge(0, 5);

    Add_edge(5, 1);

    Add_edge(1, 6);

    Add_edge(2, 6);

    Add_edge(2, 3);

    Add_edge(3, 4);

    Add_edge(4, 1);

  

    // вызов функции

    cout << shortest_cycle(n);

  

    return 0;

}

Выход:

4

Рекомендуемые посты:

Кратчайший цикл в неориентированном невзвешенном графике

0.00 (0%) 0 votes