資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 程式找到給定圖 G 的傳遞閉包
如果給定有向圖，則確定對於給定圖中的所有頂點對 (i, j)，頂點 j 是否可以從另一個頂點 i 到達。可達意為從頂點 i 到 j 有路徑。這種可達性矩陣稱為圖的傳遞閉包。沃肖爾演算法通常用於查詢給定圖 G 的傳遞閉包。這裡有一個 C++ 程式來實現此演算法。
演算法
Begin 1. Take maximum number of nodes as input. 2. For Label the nodes as a, b, c….. 3. To check if there any edge present between the nodes construct a for loop: // ASCII code of a is 97 for i = 97 to (97 + n_nodes)-1 for j = 97 to (97 + n_nodes)-1 If edge is present do, adj[i - 97][j - 97] = 1 else adj[i - 97][j - 97] = 0 End loop End loop. 4. To print the transitive closure of graph: for i = 0 to n_ nodes-1 c = 97 + i End loop. for i = 0 to n_nodes-1 c = 97 + i for j = 0 to n_nodes-1 Print adj[I][j] End loop End loop End
示例
#include<iostream>
using namespace std;
const int n_nodes = 20;
int main() {
int n_nodes, k, n;
char i, j, res, c;
int adj[10][10], path[10][10];
cout << "\n\tMaximum number of nodes in the graph :";
cin >> n;
n_nodes = n;
cout << "\nEnter 'y'for 'YES' and 'n' for 'NO' \n";
for (i = 97; i < 97 + n_nodes; i++)
for (j = 97; j < 97 + n_nodes; j++) {
cout << "\n\tIs there an edge from " << i << " to " << j << " ? ";
cin >> res;
if (res == 'y')
adj[i - 97][j - 97] = 1;
else
adj[i - 97][j - 97] = 0;
}
cout << "\nTransitive Closure of the Graph:\n";
cout << "\n\t\t\t ";
for (i = 0; i < n_nodes; i++) {
c = 97 + i;
cout << c << " ";
}
cout << "\n\n";
for (int i = 0; i < n_nodes; i++) {
c = 97 + i;
cout << "\t\t\t" << c << " ";
for (int j = 0; j < n_nodes; j++)
cout << adj[i][j] << " ";
cout << "\n";
}
return 0;
}輸出
Maximum number of nodes in the graph :4 Enter 'y'for 'YES' and 'n' for 'NO' Is there an edge from a to a ? y Is there an edge from a to b ?y Is there an edge from a to c ? n Is there an edge from a to d ? n Is there an edge from b to a ? y Is there an edge from b to b ? n Is there an edge from b to c ? y Is there an edge from b to d ? n Is there an edge from c to a ? y Is there an edge from c to b ? n Is there an edge from c to c ? n Is there an edge from c to d ? n Is there an edge from d to a ? y Is there an edge from d to b ? n Is there an edge from d to c ? y Is there an edge from d to d ? n Transitive Closure of the Graph: a b c d a 1 1 0 0 b 1 0 1 0 c 1 0 0 0 d 1 0 1 0
更新於：2019 年 7 月 30 日
197 個瀏覽量
廣告