home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

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

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

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

Output


 E0
 E1
 E2
 E3
 E4
 E5
 E6
 E7
 E8
0
 1
 1
 0
 0
 0
 0
 0
 0
 0
1
 0
 0
 1
 1
 1
 0
 0
 0
 0
2
 0
 0
 1
 0
 0
 1
 1
 0
 0
3
 0
 1
 0
 0
 0
 1
 0
 1
 0
4
 1
 0
 0
 1
 0
 0
 0
 0
 1
5
 0
 0
 0
 0
 1
 0
 1
 1
 1

อัลกอริทึม

add_edge(u, v)

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

Output: Incidence matrix ของกราฟ G

ในตอนแรก จำนวนเส้นเชื่อม ed_cnt คือ 0 สำหรับ incidence matrix

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]; // อาร์เรย์เริ่มต้นเก็บ 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) {
    // ฟังก์ชันเพิ่มเส้นเชื่อมในเมทริกซ์พร้อมหมายเลขเส้นเชื่อม
    inc_arr[u][ed_no] = 1;
    inc_arr[v][ed_no] = 1;
    ed_no++; // เพิ่มหมายเลขเส้นเชื่อม
}

main(int argc, char* argv[]) {
    int v = 6; // มี 6 จุดยอดในกราฟ
    int e = 9; // มี 9 เส้นเชื่อมในกราฟ
    
    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