โปรแกรม C++ เพื่อใช้งาน Adjacency List

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

ความซับซ้อนของการแสดง Adjacency List

• การแสดงนี้ใช้ O(V+2E) สำหรับกราฟแบบไม่บอกทิศทาง และ O(V+E) สำหรับกราฟกำกับ หากจำนวนขอบเพิ่มขึ้น พื้นที่ที่ต้องการก็จะเพิ่มขึ้นด้วย

ป้อนข้อมูล :

ผลผลิต :

อัลกอริทึม

add_edge(adj_list, u, v)

ป้อนข้อมูล :u และ v ของ edge {u,v} และรายการ adjacency

ผลผลิต :รายการที่อยู่ติดกันของกราฟ 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