Đây là chương trình C++ biểu diễn đồ thị bằng mảng 2 chiều.
Độ phức tạp thời gian của thuật toán này là O(v*v).
Thuật toán
Bắt đầu
Nhập số đỉnh 'v' và số cạnh 'e'.
Cấp phát bộ nhớ cho ma trận graph[][].
Nhập 'e' cặp đỉnh của đồ thị cho trước vào graph[][].
Với mỗi cặp đỉnh kết nối (v1, v2), lưu 1 vào graph[][] tại chỉ số (v1, v2) và (v2, v1).
In ma trận bằng PrintMatrix().
Kết thúc
Mã ví dụ
#include <iostream>
#include <iomanip>
using namespace std;
void PrintMatrix(int **matrix, int n) {
int i, j;
cout << "\n\n" << setw(4) << "";
for(i = 0; i < n; i++)
cout << setw(3) << "(" << i+1 << ")";
cout << "\n\n";
for(i = 0; i < n; i++) {
cout << setw(3) << "(" << i+1 << ")";
for(j = 0; j < n; j++) {
cout << setw(4) << matrix[i][j];
}
cout << "\n\n";
}
}
int main() {
int i, v, e, j, v1, v2;
cout << "Nhập số đỉnh của đồ thị: ";
cin >> v;
int **graph;
graph = new int*[v];
for(i = 0; i < v; i++) {
graph[i] = new int[v];
for(j = 0; j < v; j++)
graph[i][j] = 0;
}
cout << "\nNhập số cạnh của đồ thị: ";
cin >> e;
for(i = 0; i < e; i++) {
cout << "\nNhập cặp đỉnh cho cạnh " << i+1;
cout << "\nV(1): ";
cin >> v1;
cout << "V(2): ";
cin >> v2;
graph[v1-1][v2-1] = 1;
graph[v2-1][v1-1] = 1;
}
PrintMatrix(graph, v);
}
Kết quả đầu ra
Nhập số đỉnh của đồ thị: 5 Nhập số cạnh của đồ thị: 4 Nhập cặp đỉnh cho cạnh 1 V(1): 2 V(2): 1 Nhập cặp đỉnh cho cạnh 2 V(1): 3 V(2): 2 Nhập cặp đỉnh cho cạnh 3 V(1): 1 V(2): 1 Nhập cặp đỉnh cho cạnh 4 V(1): 3 V(2): 1 (1) (2) (3) (4) (5) (1) 1 1 1 0 0 (2) 1 0 1 0 0 (3) 1 1 0 0 0 (4) 0 0 0 0 0 (5) 0 0 0 0 0