数据结构
网络
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 的边，那么在邻接矩阵的第 ith 行和第 jth 列将是 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
更新于： 30-Jul-2019
超过 14,000 次浏览
Advertisements