資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時裝研究
法律研究使用沃紹爾演算法構造傳遞閉包的 C++ 程式
如果給出有向圖，就要確定對於給定圖中所有頂點對 (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 make a for loop: for i = 97 to less than 97 + number of nodes for j = 97 to less than 97 + number of nodes 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 number of nodes c = 97 + i end loop. for i = 0 to number of nodes c = 97 + i; for j = 0 to n_nodes 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
更新於: 30-7 月-2019
778 次瀏覽
廣告