資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律從源節點到目標節點恰好經過 k 條邊的所有路徑
給定一個有向圖。還給定另外兩個頂點 u 和 v，u 是起始頂點，v 是結束頂點。我們的任務是找到從頂點 u 到頂點 v 恰好經過 k 條邊的路徑數量。演算法中也提供了 k 的值。
使用動態規劃，我們需要建立一個 3D 表格，其中行將指向 u 的值，列將指向 v 的值，深度將用於跟蹤從開始到結束的邊數。
輸入和輸出
Input: The adjacency matrix of the graph: The destination vertex is 3. K = 2 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 Output: There are 2 Possible Walks, from 0 to 3 with 2 edges.
演算法
numberOdWalks(u, v, k)
輸入：起始頂點 u，結束頂點 v，邊數 k。
輸出：恰好有 k 條邊的所有可能路徑的數量。
Begin define 3D array count of order (n x n x k+1) //n is number of vertices for edge in range 0 to k, do for i in range 0 to n-1, do for j in range 0 to n-1, do count[i, j, edge] := 0 if edge = 0 and i = j, then count[i, j, edge] := 1 if edge = 1 and (i, j) is connected, then count[i, j, edge] := 1 if edge > 1, then for a in range 0 to n, and adjacent with i do count[i, j, edge] := count[i, j, edge] + count[a, j, edge - 1] done done done done return count[u, v, k] End
示例
#include <iostream>
#define NODE 7
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
int numberOfWalks(int u, int v, int k) {
int count[NODE][NODE][k+1];
for (int edge = 0; edge <= k; edge++) { //for k edges (0..k)
for (int i = 0; i < NODE; i++) {
for (int j = 0; j < NODE; j++) {
count[i][j][edge] = 0; //initially all values are 0
if (edge == 0 && i == j) //when e is 0 and ith and jth node are same, only one path
count[i][j][edge] = 1;
if (edge == 1 && graph[i][j]) //when e is 0 and direct path from (i to j), one path
count[i][j][edge] = 1;
if (edge >1) { //for more than one edges
for (int a = 0; a < NODE; a++) // adjacent of source i
if (graph[i][a])
count[i][j][edge] += count[a][j][edge-1];
}
}
}
}
return count[u][v][k];
}
int main() {
int u = 0, v = 3, k = 2;
cout << "There are "<< numberOfWalks(u, v, k)<<" Possible Walks, from ";
cout <<u<<" to "<<v<<" with "<<k<<" edges.";
}輸出
There are 2 Possible Walks, from 0 to 3 with 2 edges.
更新於: 2020年6月17日
304 次瀏覽
廣告