資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時裝研究
法律研究用鄰接矩陣表現圖的 C++ 程式
圖的鄰接矩陣是一個 V x V 大小的方陣。V 是圖 G 的頂點數。在這個矩陣中，在每一側都標記了 V 個頂點。如果圖中有一些從頂點 i 到頂點 j 的邊，那麼在鄰接矩陣中第 i 行和第 j 列將會是 1（或加權圖中的一些非零值），否則該位置將保持 0。
鄰接矩陣的表示複雜性
鄰接矩陣表示在計算過程中佔用 O(V2) 大小的空間。當圖具有最大邊數和最小邊數時，在這兩種情況下所需的控制元件都會相同。
輸入
輸出
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 1 | 0 | 0 |
| 3 | 1 | 0 | 1 | 0 | 0 | 1 |
| 4 | 1 | 1 | 0 | 0 | 0 | 1 |
| 5 | 0 | 1 | 1 | 1 | 1 | 0 |
演算法
add_edge(u, v)
輸入 − 邊 {u,v} 的 u 和 v
輸出 − 圖 G 的鄰接矩陣
Begin adj_matrix[u, v] := 1 adj_matrix[v, u] := 1 End
示例程式碼
線上演示
#include<iostream>
using namespace std;
int vertArr[20][20]; //the adjacency matrix initially 0
int count = 0;
void displayMatrix(int v) {
int i, j;
for(i = 0; i < v; i++) {
for(j = 0; j < v; j++) {
cout << vertArr[i][j] << " ";
}
cout << endl;
}
}
void add_edge(int u, int v) { //function to add edge into the matrix
vertArr[u][v] = 1;
vertArr[v][u] = 1;
}
main(int argc, char* argv[]) {
int v = 6; //there are 6 vertices in the graph
add_edge(0, 4);
add_edge(0, 3);
add_edge(1, 2);
add_edge(1, 4);
add_edge(1, 5);
add_edge(2, 3);
add_edge(2, 5);
add_edge(5, 3);
add_edge(5, 4);
displayMatrix(v);
}輸出
0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0
更新於: 2019 年 7 月 30 日
4K+ 檢視
廣告