Рубрики

Подсчитайте все возможные прогулки от источника до места назначения с ровно k ребрами

Для заданного ориентированного графа и двух вершин «u» и «v» в нем подсчитать все возможные переходы от «u» к «v» с ровно k ребрами на шаге.

Граф представлен как матричное представление смежности, где значение графа [i] [j], равное 1, указывает, что существует ребро от вершины i до вершины j, а значение 0 не указывает ребра от i до j.

Например, рассмотрим следующий график. Пусть источник 'u' будет вершиной 0, пункт назначения 'v' будет 3, а k будет 2. На выходе должно быть 2, поскольку есть два обхода от 0 до 3 с ровно 2 ребрами. Прогулки: {0, 2, 3} и {0, 1, 3}

Простое решение состоит в том, чтобы начать с u, перейти ко всем смежным вершинам и повторить для смежных вершин с k как k-1, источником как смежная вершина и пунктом назначения как v. Далее следует реализация этого простого решения.

C ++

// C ++ программа для подсчета шагов от u до v с ровно k ребрами
#include <iostream>

using namespace std;

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

  
// Наивная рекурсивная функция для подсчета шагов от u до v с k ребрами

int countwalks(int graph[][V], int u, int v, int k)

{

   // Базовые случаи

   if (k == 0 && u == v)      return 1;

   if (k == 1 && graph[u][v]) return 1;

   if (k <= 0)                return 0;

  

   // Инициализировать результат

   int count = 0;

  

   // Перейти ко всем смежным объектам и повторить

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

       if (graph[u][i] == 1)  // Проверить, смежно ли с тобой

           count += countwalks(graph, i, v, k-1);

  

   return count;

}

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

int main()

{

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

     int graph[V][V] = { {0, 1, 1, 1},

                        {0, 0, 0, 1},

                        {0, 0, 0, 1},

                        {0, 0, 0, 0}

                      };

    int u = 0, v = 3, k = 2;

    cout << countwalks(graph, u, v, k);

    return 0;

}

Джава

// Java-программа для подсчета шагов от u до v с ровно k ребрами

import java.util.*;

import java.lang.*;

import java.io.*;

  

class KPaths

{

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

  

    // Наивная рекурсивная функция для подсчета прогулок от тебя

    // к v с k ребрами

    int countwalks(int graph[][], int u, int v, int k)

    {

        // Базовые случаи

        if (k == 0 && u == v)           return 1;

        if (k == 1 && graph[u][v] == 1) return 1;

        if (k <= 0)                     return 0;

  

        // Инициализировать результат

        int count = 0;

  

        // Перейти ко всем смежным объектам и повторить

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

            if (graph[u][i] == 1// Проверить, смежно ли с тобой

                count += countwalks(graph, i, v, k-1);

  

        return count;

    }

  

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

    public static void main (String[] args) throws java.lang.Exception

    {

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

        int graph[][] =new int[][] { {0, 1, 1, 1},

            {0, 0, 0, 1},

            {0, 0, 0, 1},

            {0, 0, 0, 0}

        };

        int u = 0, v = 3, k = 2;

        KPaths p = new KPaths();

        System.out.println(p.countwalks(graph, u, v, k));

    }

}// Аакаш Хасия

python3

# Python3 программа для подсчета прогулок
# u к v с ровно k ребрами

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

V = 4

  
# Наивная рекурсивная функция для подсчета
# идет от u к v с k ребрами

def countwalks(graph, u, v, k):

  

    # Базовые случаи

    if (k == 0 and u == v):

        return 1

    if (k == 1 and graph[u][v]):

        return 1

    if (k <= 0):

        return 0

      

    # Инициализировать результат

    count = 0

      

    # Перейти ко всем окрестностям и повторить

    for i in range(0, V):

          

        # Проверьте, если рядом с вами

        if (graph[u][i] == 1): 

            count += countwalks(graph, i, v, k-1)

      

    return count

  
Код водителя

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

graph = [[0, 1, 1, 1,],

         [0, 0, 0, 1,],

         [0, 0, 0, 1,],

         [0, 0, 0, 0] ]

  

u = 0; v = 3; k = 2

print(countwalks(graph, u, v, k))

  
# Этот код предоставлен Смитой Динеш Семвал.

C #

// C # программа для подсчета прогулок от вас до
// v с ровно k ребрами

using System;

  

class GFG {

      

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

    static int V = 4;

  

    // Наивная рекурсивная функция для

    // считать ходы от U до V с

    // k ребер

    static int countwalks(int [,]graph, int u,

                                 int v, int k)

    {

          

        // Базовые случаи

        if (k == 0 && u == v)

            return 1;

        if (k == 1 && graph[u,v] == 1)

            return 1;

        if (k <= 0)                    

            return 0;

  

        // Инициализировать результат

        int count = 0;

  

        // Перейти ко всем смежным объектам и повторить

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

          

            // Проверить, смежно ли с тобой

            if (graph[u,i] == 1) 

                count += 

                countwalks(graph, i, v, k-1);

  

        return count;

    }

  

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

    public static void Main () 

    {

          

        / * Давайте создадим показанный график

        на диаграмме выше * /

        int [,]graph =

           new int[,] { {0, 1, 1, 1},

                        {0, 0, 0, 1},

                        {0, 0, 0, 1},

                        {0, 0, 0, 0} };

                          

        int u = 0, v = 3, k = 2;

          

        Console.Write(

             countwalks(graph, u, v, k));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для подсчета прогулок от вас
// к v с ровно k ребрами

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

$V = 4;

  
// Наивная рекурсивная функция для подсчета
// идет от u к v с k ребрами

function countwalks( $graph, $u, $v, $k)

{

    global $V;

  

    // Базовые случаи

    if ($k == 0 and $u == $v

        return 1;

    if ($k == 1 and $graph[$u][$v])

        return 1;

    if ($k <= 0)         

        return 0;

      

    // Инициализировать результат

    $count = 0;

      

    // Перейти ко всем смежным объектам и повторить

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

      

        // Проверить, смежно ли с тобой

        if ($graph[$u][$i] == 1) 

            $count += countwalks($graph, $i

                                $v, $k - 1);

      

    return $count;

}

  

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

    / * Давайте создадим график

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

    $graph = array(array(0, 1, 1, 1),

                   array(0, 0, 0, 1),

                   array(0, 0, 0, 1),

                   array(0, 0, 0, 0));

    $u = 0; $v = 3; $k = 2;

    echo countwalks($graph, $u, $v, $k);

  
// Этот код предоставлен anuj_67.
?>


Выход:

2

Наихудшая временная сложность вышеуказанной функции — O (V k ), где V — количество вершин в данном графе. Мы можем просто проанализировать сложность времени, нарисовав дерево рекурсии. Худшее происходит для полного графика. В худшем случае каждый внутренний узел дерева рекурсии будет иметь ровно n дочерних элементов.
Мы можем оптимизировать вышеуказанное решение с помощью динамического программирования . Идея состоит в том, чтобы создать трехмерную таблицу, в которой первое измерение является источником, второе измерение является назначением, третье измерение — это количество ребер от источника до назначения, а значение — это число прогулок. Как и другие проблемы с динамическим программированием , мы заполняем трехмерную таблицу снизу вверх.

C ++

// C ++ программа для подсчета шагов от u до v с ровно k ребрами
#include <iostream>

using namespace std;

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

  
// Функция на основе динамического программирования для подсчета прогулок от вас
// к v с k ребрами

int countwalks(int graph[][V], int u, int v, int k)

{

    // Таблица заполняется с помощью DP. Значение счетчика [i] [j] [e] будет

    // храним количество возможных прогулок от i до j с ровно k ребрами

    int count[V][V][k+1];

  

    // Цикл для количества ребер от 0 до k

    for (int e = 0; e <= k; e++)

    {

        for (int i = 0; i < V; i++)  // для источника

        {

            for (int j = 0; j < V; j++) // для пункта назначения

            {

                // инициализируем значение

                count[i][j][e] = 0;

  

                // из базовых случаев

                if (e == 0 && i == j)

                    count[i][j][e] = 1;

                if (e == 1 && graph[i][j])

                    count[i][j][e] = 1;

  

                // перейти к соседнему, только когда число ребер больше 1

                if (e > 1)

                {

                    for (int a = 0; a < V; a++) // рядом с источником i

                        if (graph[i][a])

                            count[i][j][e] += count[a][j][e-1];

                }

           }

        }

    }

    return count[u][v][k];

}

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

int main()

{

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

     int graph[V][V] = { {0, 1, 1, 1},

                        {0, 0, 0, 1},

                        {0, 0, 0, 1},

                        {0, 0, 0, 0}

                      };

    int u = 0, v = 3, k = 2;

    cout << countwalks(graph, u, v, k);

    return 0;

}

Джава

// Java-программа для подсчета шагов от u до v с ровно k ребрами

import java.util.*;

import java.lang.*;

import java.io.*;

  

class KPaths

{

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

  

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

    // к v с k ребрами

    int countwalks(int graph[][], int u, int v, int k)

    {

        // Таблица заполняется с помощью DP. Значение счетчика [i] [j] [e]

        // будет / хранить количество возможных прогулок от i до j с

        // ровно k ребер

        int count[][][] = new int[V][V][k+1];

  

        // Цикл для количества ребер от 0 до k

        for (int e = 0; e <= k; e++)

        {

            for (int i = 0; i < V; i++)  // для источника

            {

                for (int j = 0; j < V; j++) // для пункта назначения

                {

                    // инициализируем значение

                    count[i][j][e] = 0;

  

                    // из базовых случаев

                    if (e == 0 && i == j)

                        count[i][j][e] = 1;

                    if (e == 1 && graph[i][j]!=0)

                        count[i][j][e] = 1;

  

                    // перейти к соседнему, только когда число ребер

                    // больше 1

                    if (e > 1)

                    {

                        for (int a = 0; a < V; a++) // рядом с i

                            if (graph[i][a]!=0)

                                count[i][j][e] += count[a][j][e-1];

                    }

               }

            }

        }

        return count[u][v][k];

    }

  

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

    public static void main (String[] args) throws java.lang.Exception

    {

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

        int graph[][] =new int[][] { {0, 1, 1, 1},

                                     {0, 0, 0, 1},

                                     {0, 0, 0, 1},

                                     {0, 0, 0, 0}

                                    };

        int u = 0, v = 3, k = 2;

        KPaths p = new KPaths();

        System.out.println(p.countwalks(graph, u, v, k));

    }

}// Аакаш Хасия

C #

// C # программа для подсчета прогулок от u до v
// с ровно k ребрами

using System;

  

class GFG {

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

  

    // Функция на основе динамического программирования

    // считать ходы от u до v с k ребрами

    static int countwalks(int [,]graph, int u,

                                 int v, int k)

    {

        // Таблица заполняется с помощью DP.

        // значение count [i] [j] [e] будет / хранить

        // количество возможных прогулок от i до

        // j с ровно k ребрами

        int [, ,]count = new int[V,V,k+1];

  

        // Цикл для количества ребер от 0 до k

        for (int e = 0; e <= k; e++)

        {

              

            // для источника

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

            {

                  

                // для пункта назначения

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

                {

                    // инициализируем значение

                    count[i,j,e] = 0;

  

                    // из базовых случаев

                    if (e == 0 && i == j)

                        count[i,j,e] = 1;

                    if (e == 1 && graph[i,j] != 0)

                        count[i,j,e] = 1;

  

                    // перейти к соседнему только когда

                    // количество ребер

                    // больше 1

                    if (e > 1)

                    {

                        // рядом с i

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

                            if (graph[i,a]!=0)

                                count[i,j,e] +=

                                     count[a,j,e-1];

                    }

                }

            }

        }

          

        return count[u,v,k];

    }

  

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

    public static void Main () 

    {

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

        приведенная выше диаграмма * /

        int [,]graph = { {0, 1, 1, 1},

                         {0, 0, 0, 1},

                         {0, 0, 0, 1},

                         {0, 0, 0, 0} };

        int u = 0, v = 3, k = 2;

          

        Console.WriteLine(

              countwalks(graph, u, v, k));

    }

}

  
// Это код, предоставленный anuj_67.


Выход:

2

Временная сложность вышеупомянутого решения на основе DP составляет O (V 3 K), что намного лучше, чем простое решение.

Мы также можем использовать Divide and Conquer для решения вышеуказанной проблемы за время O (V 3 Logk). Количество шагов длины k от u до v является [u] [v] ой записью в (graph [V] [V]) k . Мы можем рассчитать мощность, выполнив умножение O (Logk), используя метод « разделяй и властвуй» для вычисления мощности . Умножение между двумя матрицами размера V x V занимает O (V 3 ) времени. Поэтому общая временная сложность этого метода составляет O (V 3 Logk).

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

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

Подсчитайте все возможные прогулки от источника до места назначения с ровно k ребрами

0.00 (0%) 0 votes