โปรแกรม C++ เพื่อแสดงกราฟโดยใช้รายการที่เชื่อมโยง

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

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

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

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

ป้อนข้อมูล:

ผลลัพธ์:

อัลกอริทึม

add_edge(adj_list, u, v)

ป้อนข้อมูล − u และ v ของ edge {u,v} และรายการที่อยู่ติดกัน

ผลผลิต − รายการที่อยู่ติดกันของกราฟ G

Begin
   Append v into the list at index u
   Append u into the list at index v
End

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

#include<iostream>
#include<list>
#include<iterator>
using namespace std;
void displayAdjList(list<int> adj_list[], int v) {
   for(int i = 0; i<v; i++) {
      cout << i << "--->";
      list<int> :: iterator it;
      for(it = adj_list[i].begin(); it != adj_list[i].end(); ++it) {
         cout << *it << " ";
      }
      cout << endl;
   }
}
void add_edge(list<int> adj_list[], int u, int v) {    //add v into the list u, and u into list v
   adj_list[u].push_back(v);
   adj_list[v].push_back(u);
}
main(int argc, char* argv[]) {
   int v = 6; //there are 6 vertices in the graph
   //create an array of lists whose size is 6
   list<int> adj_list[v];
   add_edge(adj_list, 0, 4);
   add_edge(adj_list, 0, 3);
   add_edge(adj_list, 1, 2);
   add_edge(adj_list, 1, 4);
   add_edge(adj_list, 1, 5);
   add_edge(adj_list, 2, 3);
   add_edge(adj_list, 2, 5);
   add_edge(adj_list, 5, 3);
   add_edge(adj_list, 5, 4);
   displayAdjList(adj_list, v);
}

ผลลัพธ์

0--->4 3
1--->2 4 5
2--->1 3 5
3--->0 2 5
4--->0 1 5
5--->1 2 3 4