โปรแกรม C++ เพื่อใช้เมทริกซ์ Adjacency

เมทริกซ์ที่อยู่ติดกันของกราฟคือเมทริกซ์กำลังสองที่มีขนาด V x V V คือจำนวนจุดยอดของกราฟ G ในเมทริกซ์นี้ในแต่ละด้าน V จุดยอดจะถูกทำเครื่องหมาย หากกราฟมีขอบบางจุดจากจุดยอด i ถึง j แสดงว่าในเมทริกซ์ส่วนต่อประสานที่ i ^th แถวและ j ^th คอลัมน์จะเป็น 1 (หรือค่าที่ไม่ใช่ศูนย์สำหรับกราฟแบบถ่วงน้ำหนัก) มิฉะนั้น ตำแหน่งนั้นจะเป็น 0

ความซับซ้อนของการแสดงเมทริกซ์ Adjacency:

• การแสดงเมทริกซ์ adjacency ใช้พื้นที่ O(V2) ในขณะที่คำนวณ เมื่อกราฟมีจำนวนขอบสูงสุดและจำนวนขอบต่ำสุด ในทั้งสองกรณี พื้นที่ที่ต้องการจะเท่ากัน

ป้อนข้อมูล:

ผลลัพธ์:

อัลกอริทึม

add_edge(u, v)

ป้อนข้อมูล :u และ v ของ edge {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