Рубрики

Найти, если есть путь более чем k длины от источника

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



Example:
Input  : Source s = 0, k = 58
Output : True
There exists a simple path 0 -> 7 -> 1
-> 2 -> 8 -> 6 -> 5 -> 3 -> 4
Which has a total distance of 60 km which
is more than 58.

Input  : Source s = 0, k = 62
Output : False

In the above graph, the longest simple
path has distance 61 (0 -> 7 -> 1-> 2
 -> 3 -> 4 -> 5-> 6 -> 8, so output 
should be false for any input greater 
than 61.

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Важно отметить, что простое выполнение BFS или DFS и выбор самого длинного края на каждом шаге не сработает. Причина в том, что более короткая кромка может дать более длинный путь из-за соединенных через нее кромок с большим весом.

Идея состоит в том, чтобы использовать Backtracking. Мы начинаем с данного источника, исследуем все пути из текущей вершины. Мы отслеживаем текущее расстояние от источника. Если расстояние становится больше, чем k, мы возвращаем true. Если путь не дает больше, чем расстояние k, мы возвращаемся.

Как мы можем быть уверены, что путь прост и мы не зацикливаемся в цикле? Идея состоит в том, чтобы отслеживать текущие вершины пути в массиве. Всякий раз, когда мы добавляем вершину к пути, мы проверяем, существует ли она уже или нет в текущем пути. Если он существует, мы игнорируем край.

Ниже приведена реализация вышеуказанной идеи.

C ++

// Программа для поиска простого пути с
// вес больше чем к
#include<bits/stdc++.h>

using namespace std;

  
// iPair ==> Целочисленная пара

typedef pair<int, int> iPair;

  
// Этот класс представляет двунаправленный граф, используя
// представление списка смежности

class Graph

{

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

  

    // В взвешенном графе нам нужно хранить вершину

    // и весовая пара для каждого ребра

    list< pair<int, int> > *adj;

    bool pathMoreThanKUtil(int src, int k, vector<bool> &path);

  

public:

    Graph(int V);  // Конструктор

  

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

    void addEdge(int u, int v, int w);

    bool pathMoreThanK(int src, int k);

};

  
// Возвращает true, если у графа путь больше длины k

bool Graph::pathMoreThanK(int src, int k)

{

    // Создаем массив пути без включенного

    // в пути

    vector<bool> path(V, false);

  

    // Добавить исходную вершину в путь

    path[src] = 1;

  

    return pathMoreThanKUtil(src, k, path);

}

  
// Печатает кратчайшие пути из src во все остальные вершины

bool Graph::pathMoreThanKUtil(int src, int k, vector<bool> &path)

{

    // Если k равно 0 или отрицательно, return true;

    if (k <= 0)

        return true;

  

    // Получить все смежные вершины исходной вершины src и

    // рекурсивно исследовать все пути из src.

    list<iPair>::iterator i;

    for (i = adj[src].begin(); i != adj[src].end(); ++i)

    {

        // Получить смежную вершину и вес ребра

        int v = (*i).first;

        int w = (*i).second;

  

        // Если вершина v уже существует в пути, то

        // есть цикл (мы игнорируем это ребро)

        if (path[v] == true)

            continue;

  

        // Если вес больше чем k, вернуть true

        if (w >= k)

            return true;

  

        // Остальное добавить эту вершину в путь

        path[v] = true;

  

        // Если этот соседний может предоставить путь дольше

        // чем k, вернуть true.

        if (pathMoreThanKUtil(v, k-w, path))

            return true;

  

        // Возврат

        path[v] = false;

    }

  

    // Если ни один соседний объект не может создать более длинный путь

    // ложный

    return false;

}

  
// Распределяет память для списка смежности

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<iPair> [V];

}

  
// Функция полезности для ребра (u, v) веса w

void Graph::addEdge(int u, int v, int w)

{

    adj[u].push_back(make_pair(v, w));

    adj[v].push_back(make_pair(u, w));

}

  
// Программа драйвера для тестирования методов класса графа

int main()

{

    // создаем график, приведенный выше

    int V = 9;

    Graph g(V);

  

    // делаем выше показанный график

    g.addEdge(0, 1, 4);

    g.addEdge(0, 7, 8);

    g.addEdge(1, 2, 8);

    g.addEdge(1, 7, 11);

    g.addEdge(2, 3, 7);

    g.addEdge(2, 8, 2);

    g.addEdge(2, 5, 4);

    g.addEdge(3, 4, 9);

    g.addEdge(3, 5, 14);

    g.addEdge(4, 5, 10);

    g.addEdge(5, 6, 2);

    g.addEdge(6, 7, 1);

    g.addEdge(6, 8, 6);

    g.addEdge(7, 8, 7);

  

    int src = 0;

    int k = 62;

    g.pathMoreThanK(src, k)? cout << "Yes\n" :

                             cout << "No\n";

  

    k = 60;

    g.pathMoreThanK(src, k)? cout << "Yes\n" :

                             cout << "No\n";

  

    return 0;

}

python3

# Программа для поиска простого пути с
# вес больше чем к

    
# Этот класс представляет двунаправленный граф, используя
# представление списка смежности

class Graph:

    # Распределяет память для списка смежности

    def __init__(self, V):

        self.V =

        self.adj = [[] for i in range(V)]

    

    # Возвращает true, если у графа путь больше длины k

    def pathMoreThanK(self,src, k):

        # Создайте массив пути без включенного

        # в пути

        path = [False]*self.V 

        

        # Добавить исходную вершину в путь

        path[src] = 1 

        

        return self.pathMoreThanKUtil(src, k, path)

        

    # Печатает кратчайшие пути из src во все остальные вершины

    def pathMoreThanKUtil(self,src, k, path):

        # Если k равно 0 или отрицательно, вернуть true

        if (k <= 0): 

            return True 

        

        # Получить все смежные вершины исходной вершины src и

        # рекурсивно исследовать все пути из src.

        i = 0

        while i != len(self.adj[src]):

            # Получить смежные вершины и вес ребра

            v = self.adj[src][i][0]

            w = self.adj[src][i][1]

            i += 1

        

            # Если вершина v уже существует в пути, то

            # есть цикл (мы игнорируем это ребро)

            if (path[v] == True): 

                continue 

        

            # Если вес больше чем k, вернуть true

            if (w >= k):

                return True 

        

            # Еще добавить эту вершину в путь

            path[v] = True 

        

            # Если этот соседний может предоставить путь дольше

            # чем K, верните истину.

            if (self.pathMoreThanKUtil(v, k-w, path)): 

                return True 

        

            # Возврат

            path[v] = False

        

        # Если ни один соседний объект не может создать более длинный путь

        # ложный

        return False 

       

    # Функция полезности для ребра (u, v) веса w

    def addEdge(self,u, v, w):

        self.adj[u].append([v, w]) 

        self.adj[v].append([u, w])

    
# Драйверная программа для тестирования методов графа класса

if __name__ == '__main__':

   

    # создать график, приведенный выше

    V = 9 

    g = Graph(V) 

    

    # создание выше показанного графика

    g.addEdge(0, 1, 4

    g.addEdge(0, 7, 8

    g.addEdge(1, 2, 8

    g.addEdge(1, 7, 11

    g.addEdge(2, 3, 7

    g.addEdge(2, 8, 2

    g.addEdge(2, 5, 4

    g.addEdge(3, 4, 9

    g.addEdge(3, 5, 14

    g.addEdge(4, 5, 10

    g.addEdge(5, 6, 2

    g.addEdge(6, 7, 1

    g.addEdge(6, 8, 6

    g.addEdge(7, 8, 7

    

    src = 0 

    k = 62 

    if g.pathMoreThanK(src, k):

        print("Yes")

    else:

        print("No"

    

    k = 60 

    if g.pathMoreThanK(src, k):

        print("Yes"

    else:

        print("No")

Выход:

No
Yes

Упражнение:
Измените вышеуказанное решение, чтобы найти вес самого длинного пути из заданного источника.

Сложность времени: O (n!)
Объяснение:
Из исходного узла мы по одному посещаем все пути и проверяем, больше ли общий вес, чем k, для каждого пути. Таким образом, наихудший случай будет, когда число возможных путей максимально. Это тот случай, когда каждый узел связан с каждым другим узлом.
Начиная с исходного узла, мы имеем n-1 смежных узлов. Время, необходимое пути для соединения любых двух узлов, равно 2. Одно для соединения источника и следующей смежной вершины. Один для разрыва связи между источником и старой смежной вершиной.
После выбора узла из n-1 смежных узлов у нас остается n-2 смежных узла (поскольку исходный узел уже включен в путь) и так далее на каждом этапе выбора узла наша проблема уменьшается на 1 узел.

Мы можем записать это в виде рекуррентного отношения как: F (n) = n * (2 + F (n-1))
Это расширяется до: 2n + 2n * (n-1) + 2n * (n-1) * (n-2) + ……. + 2n (n-1) (n-2) (n-3)… ..1
Так как n раз 2n (n-1) (n-2) (n-3)… .1 больше, чем данное выражение, мы можем смело сказать, что временная сложность равна: n * 2 * n!
Здесь в вопросе определяется первый узел, поэтому сложность времени становится
F (n-1) = 2 (n-1) * (n-1)! = 2 * n * (n-1)! — 2 * 1 * (n-1)! = 2 * n! -2 * (n-1)! = O (n!)

Эта статья пополняемые Шивов Гупт. Объяснение сложности времени дает Пранав Намбьяр . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Найти, если есть путь более чем k длины от источника

0.00 (0%) 0 votes