โปรแกรม C++ แสดงกราฟด้วย 2D Arrays

นี่คือโปรแกรม C++ แสดงกราฟโดยใช้ 2D arrays

Time complexity ของอัลกอริทึมนี้คือ O(v*v)

อัลกอริทึม

เริ่มต้น
  รับจำนวน vertex 'v' และ edges 'e'
  จัดสรรหน่วยความจำให้ graph[][] matrix
  รับ 'e' คู่ของ vertex ของกราฟที่กำหนดใน graph[][]
  สำหรับแต่ละคู่ของ vertex ที่เชื่อมต่อ (v1, v2) เก็บ 1 ใน graph[][] ที่ดัชนี (v1, v2) และ (v2, v1)
  พิมพ์เมทริกซ์โดยใช้ PrintMatrix()
สิ้นสุด

โค้ดตัวอย่าง

#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 << "Enter the number of vertexes of the graph: ";
    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 << "\nEnter the number of edges of the graph: ";
    cin >> e;
    for(i = 0; i < e; i++) {
        cout << "\nEnter the vertex pair for edge " << 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);
}

ผลลัพธ์ตัวอย่าง

Enter the number of vertexes of the graph: 5
Enter the number of edges of the graph: 4
Enter the vertex pair for edge 1
V(1): 2
V(2): 1
Enter the vertex pair for edge 2
V(1): 3
V(2): 2
Enter the vertex pair for edge 3
V(1): 1
V(2): 1
Enter the vertex pair for edge 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