Рубрики

Распечатать все пути от данного источника до места назначения

Для заданного графа, исходной вершины 's' и конечной вершины 'd' выведите все пути от заданного 's' до 'd'.

Рассмотрим следующий ориентированный граф. Пусть s будет 2, а d будет 3. Существует 4 различных пути от 2 до 3.

Идея состоит в том, чтобы сделать Глубину Первого Обхода данного ориентированного графа. Начните обход от источника. Продолжайте хранить посещенные вершины в массиве, скажем 'path []'. Если мы достигнем вершины назначения, выведите содержимое пути []. Важно пометить текущие вершины в пути [] как посещенные, чтобы обход не проходил в цикле.

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

C / C ++

// C ++ программа для печати всех путей от источника до места назначения.
#include<iostream>
#include <list>

using namespace std;

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

class Graph

{

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

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

  

    // Рекурсивная функция, используемая printAllPaths ()

    void printAllPathsUtil(int , int , bool [], int [], int &);

  

public:

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

    void addEdge(int u, int v);

    void printAllPaths(int s, int d);

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  

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

{

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

}

  
// Печатает все пути от 's' до 'd'

void Graph::printAllPaths(int s, int d)

{

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

    bool *visited = new bool[V];

  

    // Создать массив для хранения путей

    int *path = new int[V];

    int path_index = 0; // Инициализируем path [] как пустой

  

    // Инициализируем все вершины как не посещенные

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

        visited[i] = false;

  

    // Вызываем рекурсивную вспомогательную функцию для печати всех путей

    printAllPathsUtil(s, d, visited, path, path_index);

}

  
// Рекурсивная функция для печати всех путей от 'u' до 'd'.
// visit [] отслеживает вершины в текущем пути.
// path [] хранит актуальные вершины, а path_index является текущим
// индекс в пути []

void Graph::printAllPathsUtil(int u, int d, bool visited[],

                            int path[], int &path_index)

{

    // Отметить текущий узел и сохранить его в path []

    visited[u] = true;

    path[path_index] = u;

    path_index++;

  

    // Если текущая вершина совпадает с пунктом назначения, то вывести

    // текущий путь []

    if (u == d)

    {

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

            cout << path[i] << " ";

        cout << endl;

          

    }

    else // Если текущая вершина не является пунктом назначения

    {

        // Повторение для всех вершин, смежных с текущей вершиной

        list<int>::iterator i;

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

            if (!visited[*i])

                printAllPathsUtil(*i, d, visited, path, path_index);

    }

  

    // Удалить текущую вершину из path [] и пометить ее как непосещенную

    path_index--;

    visited[u] = false;

}

  
// Драйвер программы

int main()

{

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

    Graph g(4);

    g.addEdge(0, 1);

    g.addEdge(0, 2);

    g.addEdge(0, 3);

    g.addEdge(2, 0);

    g.addEdge(2, 1);

    g.addEdge(1, 3);

  

    int s = 2, d = 3;

    cout << "Following are all different paths from " << s

        << " to " << d << endl;

    g.printAllPaths(s, d);

  

    return 0;

}

Джава

// JAVA программа для печати всех
// пути от источника к
// место назначения.

import java.util.ArrayList;

import java.util.List;

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

public class Graph {

  

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

    private int v; 

      

    // список смежности

    private ArrayList<Integer>[] adjList; 

      

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

    public Graph(int vertices){

          

        // инициализировать количество вершин

        this.v = vertices;

          

        // инициализировать список смежности

        initAdjList(); 

    }

      

    // служебный метод для инициализации

    // список смежности

    @SuppressWarnings("unchecked")

    private void initAdjList()

    {

        adjList = new ArrayList[v];

          

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

        {

            adjList[i] = new ArrayList<>();

        }

    }

      

    // добавить ребро от u до v

    public void addEdge(int u, int v)

    {

        // Добавить v в список u.

        adjList[u].add(v); 

    }

      

    // Печатает все пути из

    // 's' to 'd'

    public void printAllPaths(int s, int d) 

    {

        boolean[] isVisited = new boolean[v];

        ArrayList<Integer> pathList = new ArrayList<>();

          

        // добавить источник в путь []

        pathList.add(s);

          

        // Вызов рекурсивной утилиты

        printAllPathsUtil(s, d, isVisited, pathList);

    }

  

    // Рекурсивная функция для печати

    // все пути от 'u' до 'd'.

    // isVisited [] отслеживает

    // вершины в текущем пути.

    // localPathList <> хранит актуальный

    // вершины в текущем пути

    private void printAllPathsUtil(Integer u, Integer d,

                                    boolean[] isVisited,

                            List<Integer> localPathList) {

          

        // Отметить текущий узел

        isVisited[u] = true;

          

        if (u.equals(d)) 

        {

            System.out.println(localPathList);

            // если совпадение найдено, нет необходимости проходить больше до глубины

            isVisited[u]= false;

            return ;

        }

          

        // повторить для всех вершин

        // рядом с текущей вершиной

        for (Integer i : adjList[u]) 

        {

            if (!isVisited[i])

            {

                // сохранить текущий узел

                // в пути []

                localPathList.add(i);

                printAllPathsUtil(i, d, isVisited, localPathList);

                  

                // удалить текущий узел

                // в пути []

                localPathList.remove(i);

            }

        }

          

        // Отметить текущий узел

        isVisited[u] = false;

    }

  

    // Драйвер программы

    public static void main(String[] args) 

    {

        // Создать образец графика

        Graph g = new Graph(4);

        g.addEdge(0,1);

        g.addEdge(0,2);

        g.addEdge(0,3);

        g.addEdge(2,0);

        g.addEdge(2,1);

        g.addEdge(1,3);

      

        // произвольный источник

        int s = 2;

      

        // произвольный пункт назначения

        int d = 3;

      

        System.out.println("Following are all different paths from "+s+" to "+d);

        g.printAllPaths(s, d);

  

    }

}

  
// Этот код предоставлен Химаншу Шехар.

питон

# Программа Python для печати всех путей от источника до места назначения.

   

from collections import defaultdict

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

class Graph:

   

    def __init__(self,vertices):

        #No. вершин

        self.V= vertices 

          

        # словарь по умолчанию для хранения графика

        self.graph = defaultdict(list

   

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

    def addEdge(self,u,v):

        self.graph[u].append(v)

   

    '' 'Рекурсивная функция для печати всех путей от' u 'до' d '.

    visit [] отслеживает вершины в текущем пути.

    path [] хранит актуальные вершины, а path_index является текущим

    индекс в пути [] '' '

    def printAllPathsUtil(self, u, d, visited, path):

  

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

        visited[u]= True

        path.append(u)

  

        # Если текущая вершина совпадает с пунктом назначения, выведите

        # текущий путь []

        if u ==d:

            print path

        else:

            # Если текущая вершина не является пунктом назначения

            # Повторить для всех вершин, смежных с этой вершиной

            for i in self.graph[u]:

                if visited[i]==False:

                    self.printAllPathsUtil(i, d, visited, path)

                      

        # Удалить текущую вершину из пути [] и пометить ее как непосещенную

        path.pop()

        visited[u]= False

   

   

    # Печатает все пути от 's' до 'd'

    def printAllPaths(self,s, d):

  

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

        visited =[False]*(self.V)

  

        # Создать массив для хранения путей

        path = []

  

        # Вызовите рекурсивную вспомогательную функцию для печати всех путей

        self.printAllPathsUtil(s, d,visited, path)

   

   

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

g = Graph(4)

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(0, 3)

g.addEdge(2, 0)

g.addEdge(2, 1)

g.addEdge(1, 3)

   

s = 2 ; d = 3

print ("Following are all different paths from %d to %d :" %(s, d))

g.printAllPaths(s, d)
# Этот код предоставлен Ниламом Ядавом

C #

// C # программа для печати всех
// пути от источника к
// место назначения.

using System;

using System.Collections.Generic;

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

public class Graph 

  

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

    private int v; 

      

    // список смежности

    private List<int>[] adjList; 

      

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

    public Graph(int vertices)

    

          

        // инициализировать количество вершин

        this.v = vertices; 

          

        // инициализировать список смежности

        initAdjList(); 

    

      

    // служебный метод для инициализации

    // список смежности

    private void initAdjList() 

    

        adjList = new List<int>[v]; 

          

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

        

            adjList[i] = new List<int>(); 

        

    

      

    // добавить ребро от u до v

    public void addEdge(int u, int v) 

    

        // Добавить v в список u.

        adjList[u].Add(v); 

    

      

    // Печатает все пути из

    // 's' to 'd'

    public void printAllPaths(int s, int d) 

    

        bool[] isVisited = new bool[v]; 

        List<int> pathList = new List<int>(); 

          

        // добавить источник в путь []

        pathList.Add(s); 

          

        // Вызов рекурсивной утилиты

        printAllPathsUtil(s, d, isVisited, pathList); 

    

  

    // Рекурсивная функция для печати

    // все пути от 'u' до 'd'.

    // isVisited [] отслеживает

    // вершины в текущем пути.

    // localPathList <> хранит актуальный

    // вершины в текущем пути

    private void printAllPathsUtil(int u, int d, 

                                    bool[] isVisited, 

                            List<int> localPathList) 

    

          

        // Отметить текущий узел

        isVisited[u] = true

          

        if (u.Equals(d)) 

        

            Console.WriteLine(string.Join(" ", localPathList)); 

              

            // если совпадение найдено, то нет необходимости

            // пройти больше до глубины

            isVisited[u] = false

            return

        

          

        // повторить для всех вершин

        // рядом с текущей вершиной

        foreach (int i in adjList[u]) 

        

            if (!isVisited[i]) 

            

                // сохранить текущий узел

                // в пути []

                localPathList.Add(i); 

                printAllPathsUtil(i, d, isVisited, 

                                    localPathList); 

                  

                // удалить текущий узел

                // в пути []

                localPathList.Remove(i); 

            

        

          

        // Отметить текущий узел

        isVisited[u] = false

    

  

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

    public static void Main(String[] args) 

    

        // Создать образец графика

        Graph g = new Graph(4); 

        g.addEdge(0,1); 

        g.addEdge(0,2); 

        g.addEdge(0,3); 

        g.addEdge(2,0); 

        g.addEdge(2,1); 

        g.addEdge(1,3); 

      

        // произвольный источник

        int s = 2; 

      

        // произвольный пункт назначения

        int d = 3; 

      

        Console.WriteLine("Following are all different"

                            " paths from " + s + " to " + d); 

        g.printAllPaths(s, d); 

    

  
// Этот код предоставлен Rajput-Ji


Выход:

Following are all different paths from 2 to 3
2 0 1 3
2 0 3
2 1 3 

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

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

Распечатать все пути от данного источника до места назначения

0.00 (0%) 0 votes