C++ প্রোগ্রাম: ইনসিডেন্স ম্যাট্রিক্স ব্যবহার করে গ্রাফ রিপ্রেজেন্টেশন

একটি গ্রাফের ইনসিডেন্স ম্যাট্রিক্স হলো গ্রাফকে মেমোরিতে স্টোর করার আরেকটি রিপ্রেজেন্টেশন। এই ম্যাট্রিক্সটি স্কোয়ার ম্যাট্রিক্স নয়। ইনসিডেন্স ম্যাট্রিক্সর অর্ডার V x E। এখানে V হলো ভার্টেক্সের সংখ্যা এবং E হলো গ্রাফে এজের সংখ্যা।

এই ম্যাট্রিক্সর প্রতিটি সারিতে আমরা ভার্টেক্স রাখি, এবং প্রতিটি কলামে এজ রাখি। এই রিপ্রেজেন্টেশনে একটি এজ e {u, v} এর জন্য, কলাম e-র u এবং v প্লেসে ১ দিয়ে মার্ক করা হয়।

অ্যাডজেসেন্সি ম্যাট্রিক্স রিপ্রেজেন্টেশনের কমপ্লেক্সিটি

• ইনসিডেন্স ম্যাট্রিক্স রিপ্রেজেন্টেশন O(V x E) স্পেস নেয়। কমপ্লিট গ্রাফের জন্য এজের সংখ্যা হবে V(V-1)/2। তাই ইনসিডেন্স ম্যাট্রিক্স মেমোরিতে বড় স্পেস নেয়।

ইনপুট

আউটপুট

অ্যালগরিদম

add_edge(u, v)

ইনপুট - একটি এজ {u,v}-এর u এবং v

আউটপুট - গ্রাফ G-এর ইনসিডেন্স ম্যাট্রিক্স

প্রথমে, ইনসিডেন্স ম্যাট্রিক্সের জন্য এজ কাউন্ট ed_cnt ০।

শুরু
ed_cnt := ed_cnt + 1
inc_matrix[u, ed_cnt] := 1
inc_matrix[v, ed_cnt] := 1
শেষ

উদাহরণ কোড (C++)

#include<iostream>
using namespace std;

int inc_arr[20][20]; // ইনসিডেন্স ম্যাট্রিক্স ধারণ করার জন্য ইনিশিয়াল অ্যারে
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; // গ্রাফে ৬টি ভার্টেক্স
    int e = 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