Рубрики

Найти, есть ли путь между двумя вершинами в ориентированном графе

Учитывая направленный граф и две вершины в нем, проверьте, существует ли путь от первой данной вершины до второй. Например, на следующем графике есть путь от вершины 1 до 3. В качестве другого примера, нет пути от 3 до 0.

Мы можем использовать поиск по ширине (BFS) или поиск по глубине (DFS), чтобы найти путь между двумя вершинами. Возьмите первую вершину в качестве источника в BFS (или DFS), следуйте стандартному BFS (или DFS). Если мы увидим вторую вершину в нашем обходе, вернем true. Остальное вернуть ложь.

Ниже приведены коды C ++, Java и Python, которые используют BFS для нахождения достижимости второй вершины из первой вершины.

C ++

// C ++ программа для проверки существования пути между двумя вершинами
// графика.
#include<iostream>
#include <list>

using namespace std;

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

class Graph

{

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

    list<int> *adj;    // Указатель на массив, содержащий списки смежности

public:

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

    void addEdge(int v, int w); // функция для добавления ребра на график

    bool isReachable(int s, int d);  

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  

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

{

    adj[v].push_back(w); // Добавить w в список v.

}

  
// Функция на основе BFS, чтобы проверить, достижим ли d из s.

bool Graph::isReachable(int s, int d)

{

    // Базовый вариант

    if (s == d)

      return true;

  

    // Пометить все вершины как не посещенные

    bool *visited = new bool[V];

    for (int i = 0; i < V; i++)

        visited[i] = false;

  

    // Создать очередь для BFS

    list<int> queue;

  

    // Помечаем текущий узел как посещенный и ставим его в очередь

    visited[s] = true;

    queue.push_back(s);

  

    // будет использоваться для получения всех смежных вершин вершины

    list<int>::iterator i;

  

    while (!queue.empty())

    {

        // Удаление вершины из очереди и печать ее

        s = queue.front();

        queue.pop_front();

  

        // Получаем все смежные вершины удаленной вершины s

        // Если соседний объект не был посещен, отметьте его как посещенный

        // и поставить в очередь

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

        {

            // Если этот соседний узел является узлом назначения, то

            // вернуть true

            if (*i == d)

                return true;

  

            // Остальное, продолжать делать BFS

            if (!visited[*i])

            {

                visited[*i] = true;

                queue.push_back(*i);

            }

        }

    }

      

    // Если BFS завершена без посещения d

    return false;

}

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

int main()

{

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

    Graph g(4);

    g.addEdge(0, 1);

    g.addEdge(0, 2);

    g.addEdge(1, 2);

    g.addEdge(2, 0);

    g.addEdge(2, 3);

    g.addEdge(3, 3);

  

    int u = 1, v = 3;

    if(g.isReachable(u, v))

        cout<< "\n There is a path from " << u << " to " << v;

    else

        cout<< "\n There is no path from " << u << " to " << v;

  

    u = 3, v = 1;

    if(g.isReachable(u, v))

        cout<< "\n There is a path from " << u << " to " << v;

    else

        cout<< "\n There is no path from " << u << " to " << v;

  

    return 0;

}

Джава

// Java-программа для проверки существования пути между двумя вершинами
// графика.

import java.io.*;

import java.util.*;

import java.util.LinkedList;

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

class Graph

{

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

    private LinkedList<Integer> adj[]; // Список смежности

  

    //Конструктор

    Graph(int v)

    {

        V = v;

        adj = new LinkedList[v];

        for (int i=0; i<v; ++i)

            adj[i] = new LinkedList();

    }

  

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

    void addEdge(int v,int w)  {   adj[v].add(w);   }

  

    // печатает прохождение BFS из заданного источника

    Boolean isReachable(int s, int d)

    {

        LinkedList<Integer>temp;

  

        // Пометить все вершины как не посещенные (по умолчанию установлено

        // как ложь)

        boolean visited[] = new boolean[V];

  

        // Создать очередь для BFS

        LinkedList<Integer> queue = new LinkedList<Integer>();

  

        // Помечаем текущий узел как посещенный и ставим его в очередь

        visited[s]=true;

        queue.add(s);

  

        // 'i' будет использоваться для получения всех смежных вершин вершины

        Iterator<Integer> i;

        while (queue.size()!=0)

        {

            // Удаление вершины из очереди и печать ее

            s = queue.poll();

  

            int n;

            i = adj[s].listIterator();

  

            // Получаем все смежные вершины удаленной вершины s

            // Если соседний объект не был посещен, отметьте его

            // посетили и поставили в очередь

            while (i.hasNext())

            {

                n = i.next();

  

                // Если этот соседний узел является узлом назначения,

                // затем возвращаем true

                if (n==d)

                    return true;

  

                // Остальное, продолжать делать BFS

                if (!visited[n])

                {

                    visited[n] = true;

                    queue.add(n);

                }

            }

        }

  

        // Если BFS завершена без посещения d

        return false;

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

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

        Graph g = new Graph(4);

        g.addEdge(0, 1);

        g.addEdge(0, 2);

        g.addEdge(1, 2);

        g.addEdge(2, 0);

        g.addEdge(2, 3);

        g.addEdge(3, 3);

  

        int u = 1;

        int v = 3;

        if (g.isReachable(u, v))

            System.out.println("There is a path from " + u +" to " + v);

        else

            System.out.println("There is no path from " + u +" to " + v);;

  

        u = 3;

        v = 1;

        if (g.isReachable(u, v))

            System.out.println("There is a path from " + u +" to " + v);

        else

            System.out.println("There is no path from " + u +" to " + v);;

    }

}
// Этот код предоставлен Aakash Hasija

питон

# программа для проверки существования пути между двумя вершинами
№ графика

  

from collections import defaultdict

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

class Graph:

   

    def __init__(self,vertices):

        self.V= vertices #No. вершин

        self.graph = defaultdict(list) # словарь по умолчанию для хранения графика

   

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

    def addEdge(self,u,v):

        self.graph[u].append(v)

       

     # Используйте BFS, чтобы проверить путь между s и d

    def isReachable(self, s, d):

        # Отметить все вершины как не посещенные

        visited =[False]*(self.V)

   

        # Создать очередь для BFS

        queue=[]

   

        # Отметить исходный узел как посещенный и поставить его в очередь

        queue.append(s)

        visited[s] = True

   

        while queue:

  

            # Удалить вершину из очереди

            n = queue.pop(0)

              

            # Если этот соседний узел является узлом назначения,

            # затем верните true

             if n == d:

                 return True

  

            # Остальное, продолжать делать BFS

            for i in self.graph[n]:

                if visited[i] == False:

                    queue.append(i)

                    visited[i] = True

         # Если BFS завершена без посещения d

         return False

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

g = Graph(4)

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

  

u =1; v = 3

  

if g.isReachable(u, v):

    print("There is a path from %d to %d" % (u,v))

else :

    print("There is no path from %d to %d" % (u,v))

  

u = 3; v = 1

if g.isReachable(u, v) :

    print("There is a path from %d to %d" % (u,v))

else :

    print("There is no path from %d to %d" % (u,v))

  
# Этот код предоставлен Ниламом Ядавом


Выход:

 There is a path from 1 to 3
 There is no path from 3 to 1

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

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

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

Найти, есть ли путь между двумя вершинами в ориентированном графе

0.00 (0%) 0 votes