โปรแกรม C++ แสดงกราฟด้วย Linked List

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

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

ความซับซ้อนของการแสดงผลด้วย Adjacency Matrix

• การแสดงผลด้วย incidence matrix ใช้พื้นที่ O(V x E) ขณะคำนวณ สำหรับ complete graph จำนวนเส้นเชื่อมจะเป็น V(V-1)/2 ดังนั้น incidence matrix ใช้พื้นที่มากกว่าในหน่วยความจำ

Input:

Output:

อัลกอริทึม

add_edge(adj_list, u, v)

Input: จุดยอด u และ v ของเส้นเชื่อม {u,v} และ adjacency list

Output: Adjacency List ของกราฟ G

Begin
    Append v ลงในลิสต์ที่ index u
    Append u ลงในลิสต์ที่ 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) {
    // เพิ่ม v ลงในลิสต์ u และ u ลงในลิสต์ v
    adj_list[u].push_back(v);
    adj_list[v].push_back(u);
}

main(int argc, char* argv[]) {
    int v = 6; // มี 6 จุดยอดในกราฟ
    // สร้างอาร์เรย์ของลิสต์ขนาด 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