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

একটি গ্রাফের ইনসিডেন্স ম্যাট্রিক্স হল মেমরিতে সংরক্ষণ করার জন্য একটি গ্রাফের আরেকটি উপস্থাপনা৷ এই ম্যাট্রিক্স একটি বর্গ ম্যাট্রিক্স নয়। ইনসিডেন্স ম্যাট্রিক্সের ক্রম হল V x E। যেখানে V হল শীর্ষবিন্দুর সংখ্যা এবং E হল গ্রাফের প্রান্তের সংখ্যা।

এই ম্যাট্রিক্সের প্রতিটি সারিতে আমরা শীর্ষবিন্দু স্থাপন করছি, এবং প্রতিটি কলামে প্রান্তগুলি স্থাপন করা হয়েছে। একটি প্রান্ত e {u, v}-এর জন্য এই উপস্থাপনায়, এটি কলাম e-এর u এবং v স্থানের জন্য 1 দ্বারা চিহ্নিত করা হবে।

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

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

ইনপুট:

আউটপুট:

অ্যালগরিদম

add_edge(adj_list, u, v)

ইনপুট − একটি প্রান্তের u এবং v {u,v}, এবং সংলগ্ন তালিকা

আউটপুট − গ্রাফ G

সূচীতে v যুক্ত করা শুরু করুন 
উদাহরণ কোড
 
#include#include#include namespace ব্যবহার করে std;void displayAdjList(list adj_list[], int v) { for(int i =0; i"; তালিকা ::পুনরাবৃত্তিকারী এটি; for(it =adj_list[i].begin(); it !=adj_list[i].end(); ++it) { cout <<*it <<""; } cout < adj_list[], int u, int v) { // তালিকা uতে v যোগ করুন, এবং u তালিকা v adj_list[u].push_back(v); adj_list[v].push_back(u);} main(int argc, char* argv[]) { int v =6; //গ্রাফে 6 টি শীর্ষবিন্দু আছে // তালিকার একটি অ্যারে তৈরি করুন যার আকার 6 তালিকা 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 31--->2 4 52--->1 3 53--->0 2 54--->0 1 55--->1 2 3 4