โปรแกรม C++ เพื่อแสดงกราฟโดยใช้เมทริกซ์อุบัติการณ์

เมทริกซ์อุบัติการณ์ของกราฟเป็นอีกหนึ่งการแสดงกราฟเพื่อเก็บไว้ในหน่วยความจำ เมทริกซ์นี้ไม่ใช่เมทริกซ์กำลังสอง ลำดับของเมทริกซ์อุบัติการณ์คือ V x E โดยที่ V คือจำนวนจุดยอด และ E คือจำนวนขอบในกราฟ

ในแต่ละแถวของเมทริกซ์นี้ เรากำลังวางจุดยอด และวางขอบในแต่ละคอลัมน์ ในการแทนค่านี้สำหรับ edge e {u, v} มันจะถูกทำเครื่องหมายด้วย 1 สำหรับตำแหน่ง u และ v ของคอลัมน์ e

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

• การแสดงเมทริกซ์อุบัติการณ์ใช้พื้นที่จำนวน O (Vx E) ในขณะที่คำนวณ สำหรับกราฟที่สมบูรณ์ จำนวนขอบจะเป็น V(V-1)/2 ดังนั้นเมทริกซ์อุบัติการณ์จึงใช้พื้นที่ในหน่วยความจำมากขึ้น

ป้อนข้อมูล

ผลผลิต

อัลกอริทึม

add_edge(u, v)

ป้อนข้อมูล − u และ v ของ edge {u,v}

ผลผลิต − เมทริกซ์อุบัติการณ์ของกราฟ G

ในตอนแรก มีการนับขอบ ed_cnt เป็น 0 สำหรับเมทริกซ์อุบัติการณ์

Begin
   ed_cnt := ed_cnt + 1
   inc_matrix[u, ed_cnt] := 1
   inc_matrix[v, ed_cnt] := 1
End

โค้ดตัวอย่าง (C++)

#include<iostream>
using namespace std;
int inc_arr[20][20]; //initial array to hold incidence matrix
int ed_no = 0;
void displayMatrix(int v, int e) {
   int i, j;
   for(i = 0; i < v; i++) {
      for(j = 0; j < e; j++) {
         cout << inc_arr[i][j] << " ";
      }
      cout << endl;
   }
}
void add_edge(int u, int v) { //function to add edge into the matrix with edge number
   inc_arr[u][ed_no] = 1;
   inc_arr[v][ed_no] = 1;
   ed_no++; //increase the edge number
}
main(int argc, char* argv[]) {
   int v = 6; //there are 6 vertices in the graph
   int e = 9; //there are 9 edges 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, e);
}

ผลลัพธ์

1 1 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0
0 0 1 0 0 1 1 0 0
0 1 0 0 0 1 0 1 0
1 0 0 1 0 0 0 0 1
0 0 0 0 1 0 1 1 1