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

01.01.2020Графы, Динамическое программирование, Разделяй и властвуй

Для заданного ориентированного графа и двух вершин «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, 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, 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, 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, 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, 0));

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

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

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

Выход:

Наихудшая временная сложность вышеуказанной функции — 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, 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, 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, 0} };

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

Console.WriteLine(

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

}

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

Выход:

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

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

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

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

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

0.00 (0%) 0 votes