লেখচিত্র উপস্থাপন

লেখচিত্র প্রকাশ করার জন্য অনেকগুলো পদ্ধতি রয়েছে এবং প্রতিটি পদ্ধতির কিছু সুবিধা ও অসুবিধা রয়েছে। কিছু কিছু পরিস্থিতি অথবা অ্যালগোরিদমে আমরা লেখচিত্র ইনপুট হিসেবে নিয়ে রান করাতে চাই যেটাকে একধরনের উপস্থাপন বলা যেতে পারে এবং বাকি যেগুলো থাকে সেগুলোকে অন্য রকমভাবে উপস্থাপন বলা যেতে পারে। আমরা লেখচিত্র উপস্থাপনের তিনটি পদ্ধতি এখানে দেখব।

তিনটি পদ্ধতি আমরা এখানে দেখব। একটি পদ্ধতি হল প্রতিটি লেখচিত্র উপস্থাপন করার জন্য আমাদের কতটুকু স্মৃতিশক্তি বা স্থান প্রয়োজন হবে। আমরা এই কাজটি করার জন্য এ্যাসিম্প্টোটিক নোটেশান ব্যবহার করব। হ্যাঁ, রান করার সময়কাল প্রকাশ করার কাজটি করা ছাড়াও এই উদ্দেশ্যেও এ্যাসিম্প্টোটিক নোটেশান আমরা ব্যবহার করতে পারি! ফাংশনকে বৈশিষ্ট্য দান করার জন্য এটা খুবই ভাল একটি পদ্ধতি এবং একটি ফাংশন রান করার সময়কাল বর্ণনা করতে পারে, কতটুকু স্থান এর জন্য লাগবে, অথবা অন্য কোন বৈশিষ্ট্য। অন্য যে পদ্ধতি আমরা এখানে ব্যবহার করব সেই দুইটি সময় ব্যবহার করে কাজ করে থাকে। একটি পদ্ধতি হল লেখচিত্রে প্রান্তবিন্দু আছে কিনা তা খুঁজে বের করতে কত সময় প্রয়োজন হয়। অন্য পদ্ধতিটি হল, দিয়ে দেওয়া একটি শীর্ষবিন্দুর চারপাশে থাকা বিন্দুগুলো খুঁজে বের করতে এর কত সময় প্রয়োজন হয়।

সাধারণভাবে আমরা শীর্ষবিন্দু একটি সংখ্যা দিয়ে চিহ্নিত করে থাকি নাম দিয়ে নয় (যেমন "অড্রে," "বোস্টন," অথবা "সোয়েটার")। আমরা মূলত, এইভাবেই $|V|$‍ শীর্ষবিন্দুগুলো 0 থেকে $|V|-1$‍ পর্যন্ত চিহ্নিত করে থাকি। সামাজিক যোগাযোগ মাধ্যমের একটি লেখচিত্র এখানে দেওয়া হল যেখানে 10 টি শীর্ষবিন্দুকে নাম ব্যবহার করে উপস্থাপন করার পরিবর্তে সংখ্যা ব্যবহার করে উপস্থাপন করা হয়েছে:

লেখচিত্র উপস্থাপন করার সবচেয়ে সহজ উপায় হল একটি তালিকা অথবা প্রান্তবিন্দু $|E|$‍ এর অ্যারের মাধ্যমে লেখচিত্র উপস্থাপন করা, যেটিকে সাধারণভাবে আমরা একটি এজ লিস্ট বা প্রান্তবিন্দুর তালিকা বলে থাকি। একটি প্রান্তবিন্দু প্রকাশ করার জন্য, আমাদের কাছে দুইটি শীর্ষবিন্দুর সংখ্যার একটু অ্যারে আছে অথবা অবজেক্টের একটি অ্যারে এখানে দেওয়া আছে যেখানে শীর্ষবিন্দুর সংখ্যা দেওয়া আছে। প্রান্তবিন্দুর মান যদি এখানে দেওয়া থাকে, তাহলে হয় তোমাকে অ্যারেতে তৃতীয় একটি উপাদান যুক্ত করতে হবে অথবা অবজেক্ট সম্পর্কিত আরও তথ্য এখানে যুক্ত করতে হবে, প্রান্তবিন্দুর একটি মান প্রদান করার মাধ্যমে। যেহেতু প্রতিটি প্রান্তবিন্দু শুধুমাত্র দুইটি অথবা তিনটি সংখ্যা নিয়ে তৈরি হয়, একটি প্রান্তবিন্দুর তালিকাতে মোট স্থানের পরিমাণ হল $\mathrm{\Theta }(E)$‍। উদাহরণস্বরূপ, সামাজিক যোগাযোগ মাধ্যমের লেখচিত্র কীভাবে জাভাস্ক্রিপ্টে প্রান্তবিন্দুর তালিকা হিসেবে আমরা প্রকাশ করব তা এখানে দেখানো হল:

প্রান্তবিন্দু বেশ সরল একটি বিষয়, কিন্তু আমরা যদি জানতে চাই যে লেখচিত্রে নির্দিষ্ট একটি প্রান্তবিন্দু খুঁজে বের করতে চাই তাহলে আমাদের প্রান্তবিন্দুর তালিকাটি সম্পূর্ণ খুঁজে বের করতে হবে। যদি প্রান্তবিন্দুর তালিকাতে, প্রান্তবিন্দুগুলো নির্দিষ্ট কোন ক্রম অনুসরণ করে না আসে, তাহলে সেটি হবে $|E|$‍ প্রান্তবিন্দুর মাধ্যমে লিনিয়ার সার্চ। এখানে যে প্রশ্নটি নিয়ে চিন্তা করা দরকার সেটা হল: কীভাবে তুমি একটি প্রান্তবিন্দুর তালিকা তৈরি করবে যেটা যেটা নির্দিষ্ট একটি প্রান্তবিন্দু খুঁজে বের করতে $O(\lg E)$‍ সময় নিবে? উত্তরটি একটু জটিল।

For a graph with $|V|$‍ vertices, an adjacency matrix is a $|V|\times |V|$‍ matrix of 0s and 1s, where the entry in row $i$‍ and column $j$‍ is 1 if and only if the edge $(i,j)$‍ is in the graph. If you want to indicate an edge weight, put it in the row $i$‍, column $j$‍ entry, and reserve a special value (perhaps null) to indicate an absent edge. Here's the adjacency matrix for the social network graph:

জাভাস্ক্রিপ্টে, আমরা এই ম্যাট্রিক্সটি নিচের মত করে উপস্থাপন করব:

একটি অ্যাডজাসেন্সি ম্যাট্রিক্স ব্যবহার করার মাধ্যমে, আমরা খুঁজে বের করতে পারব যে ধ্রুবক একটি সময়ে একটি প্রান্তবিন্দু উপস্থিত আছে কিনা তা আমরা সংশ্লিষ্ট ম্যাট্রিক্সের এন্ট্রি দেখার মাধ্যমে বের করতে পারব। উদাহরণস্বরূপ, যদি অ্যাডজাসেন্সি ম্যাট্রিক্স লেখচিত্রের নামে সংরক্ষিত হয়, তাহলে আমরা এখানে অনুসন্ধান করতে পারব যে $(i,j)$‍ প্রান্তবিন্দু দুইটি লেখচিত্রে আছে কিনা তা আমরা লেখচিত্রে অনুসন্ধান করার মাধ্যমে দেখব যে graph[i][j] আছে কিনা। তাহলে অ্যাডজাসেন্সি ম্যাট্রিক্সের অসুবিধা কি? আসলে দুইটি জিনিস। প্রথমে, এটি $\mathrm{\Theta }(V^2)$‍ স্থান দখল করে, এমন কি লেখচিত্রটি বিক্ষিপ্ত হলেও: অল্প কিছু প্রান্তবিন্দু নিয়ে। অন্য কথায় বলতে গেলে বলা যায়, একটি বিক্ষিপ্ত লেখচিত্রের জন্য অ্যাডজাসেন্সি ম্যাট্রিক্স এর মান বেশির ভাগ সময় 0 হয় এবং আমরা অনেক বেশি স্থান এখানে ব্যবহার করছি অল্প কিছু প্রান্তবিন্দু এখানে প্রদর্শন করার জন্য। দ্বিতীয়ত, তুমি যদি খুঁজে বের করতে চাও যে শীর্ষবিন্দু $i$‍ সংলগ্ন কোন শীর্ষবিন্দুগুলো এখানে রয়েছে, তোমাকে তাহলে সারি $i$‍ তে থাকা সবগুলো $|V|$‍ এন্ট্রি খুঁজে দেখতে হবে, এমনকি যদি অল্প সংখ্যক শীর্ষবিন্দুও যদি $i$‍ শীর্ষবিন্দুর সংলগ্ন থাকে।

একটি অদিকনির্দেশক লেখচিত্রের জন্য, অ্যাডজাসেন্সি ম্যাট্রিক্সটি প্রতিসম হবে: সারি $i$‍, কলাম $j$‍ এন্ট্রি 1 হবে যদি এবং শুধুমাত্র যদি সারি $j$‍, কলাম $i$‍ এর এন্ট্রি 1 হয়। একটি দিকনির্দেশক লেখচিত্রের জন্য অ্যাডজাসেন্সি ম্যাট্রিক্সটি প্রতিসম হবার কোন প্রয়োজন নেই।

অ্যাডজেসেন্সি লিস্ট ব্যবহার করে একটি লেখচিত্র প্রকাশ করার জন্য অ্যাডজেসেন্সি ম্যাট্রিক্স এবং প্রান্তবিন্দুর তালিকা একসাথে নিয়ে কাজ করতে হয়। প্রতিটি শীর্ষবিন্দু $i$‍ এর জন্য, এই শীর্ষবিন্দুর কাছাকাছি থাকা বিন্দুতে একটি অ্যারে সংরক্ষণ করা যাক। আমাদের কাছে মূলত $|V|$‍ অ্যাডজেসেন্সি লিস্টের একটি অ্যারে আছে, যেখানে প্রতিটি শীর্ষবিন্দুর জন্য একটি করে অ্যাডজেসেন্সি লিস্ট থাকবে। সামাজিক যোগাযোগ মাধ্যমের জন্য অ্যাডজেসেন্সি লিস্টের আকারে লেখচিত্রের উপস্থাপন এখানে দেখানো হল:

জাভাস্ক্রিপ্টে, আমরা এই অ্যাডজেসেন্সি লিস্টটি নিচের মত করে উপস্থাপন করব:

অ্যাডজেসেন্সি লিস্টে, শীর্ষবিন্দুর সংখ্যা নির্দিষ্ট কোন ক্রম অনুসরণ করে প্রকাশ করার কোন দরকার নেই, যদিও কোন কোন সময় এটিকে ছোট থেকে বড় ক্রম অনুসরণ করে সাজানোর প্রয়োজন পড়ে, এই উদাহরণে যেরকম করা হয়েছে।

প্রতিটি শীর্ষবিন্দুর অ্যাডজেসেন্সি লিস্টে আমরা ধ্রুবক একটি সময়ে পৌঁছাতে পারব, কারণ একটি অ্যারের মধ্যে আমাদের শুধু ইনডেক্স করতে হবে। লেখচিত্রে একটি প্রান্তবিন্দু $(i,j)$‍ উপস্থিত আছে কিনা তা খুঁজে বের করার জন্য, আমরা $i$‍ এর অ্যাডজেসেন্সি লিস্টে ধ্রুবক একটি সময়ে আমরা যাব এবং তারপরে $i$‍এর অ্যাডজেসেন্সি লিস্টের ভিতরে $j$‍ খুঁজে দেখব। সবচেয়ে খারাপ ক্ষেত্রে এটা তাহলে কত সময় নিতে পারে? উত্তরটি হল $\mathrm{\Theta }(d)$‍, যেখানে $d$‍ হল শীর্ষবিন্দু $i$‍ এর ডিগ্রী, কারণ $i$‍ এর অ্যাডজেসেন্সি লিস্টটি এই পরিমাণ লম্বা। শীর্ষবিন্দু $i$‍ এর ডিগ্রি $|V|-1$‍ মত বড় হতে পারে (যদি $i$‍ অন্যান্য $|V|-1$‍ শীর্ষবিন্দুর সংলগ্ন হয়) অথবা 0 এর মানের মত ছোট হয় ($i$‍ যদি বিচ্ছিন্ন হয়, যে প্রান্তবিন্দুতে কোন ঘটনা থাকবে না)। একটি অদিকনির্দেশক লেখচিত্রে, শীর্ষবিন্দু $j$‍ বিন্দুটি, শীর্ষবিন্দু $i$‍ এর অ্যাডজেসেন্সি লিস্ট এর মধ্যে থাকবে যদি এবং শুধুমাত্র যদি $i$‍ বিন্দুটি $j$‍ এর অ্যাডজেসেন্সি লিস্টের ভিতরে অবস্থান করে। যদি লেখচিত্রে মান দেওয়া থাকে তাহলে, তাহলে প্রতিটি অ্যাডজেসেন্সি লিস্টে থাকা প্রতিটি জিনিস হয় দুইটি-জিনিস সম্বলিত একটি অ্যারে হবে অথবা একটি অবজেক্ট হবে, যেটি শীর্ষবিন্দুর একটি সংখ্যা দিবে এবং প্রান্তবিন্দুর মান প্রকাশ করবে।

অ্যাডজেসেন্সি লিস্টের শীর্ষবিন্দুর পুনরাবৃত্তির মধ্য দিয়ে যাবার জন্য তুমি একটি for-লুপ এখানে ব্যবহার করতে পার। উদাহরণস্বরূপ, মনে করা যাক তোমার কাছে একটি অ্যাডজেসেন্সি লিস্ট আছে যেটা চলক লেখচিত্র হিসেবে প্রকাশ করবে, যাতে graph[i] এর ভিতরে একটি অ্যারে থাকতে পারে যার মধ্যে সংলগ্ন শীর্ষবিন্দু $i$‍ থাকবে। তারপরে, শীর্ষবিন্দু $i$‍ এর সংলগ্ন প্রতিটি শীর্ষবিন্দুর জন্য doStuff নামে একটি ফাংশন কল করতে হবে, তুমি নিচের জাভাস্ক্রিপ্ট কোডটি এখানে ব্যবহার করতে পার:

যদি ডাবল-সাবস্ক্রিপ্ট নোটেশন তোমাকে বিভ্রান্ত করে, তুমি এটাকে এভাবেও চিন্তা করতে পার:

অ্যাডজেসেন্সি লিস্ট কতটুকু স্থান দখল করে থাকে? আমাদের কাছে $|V|$‍ আছে এবং যদিও প্রতিটি তালিকার $|V|-1$‍ সংখ্যক শীর্ষবিন্দু থাকতে পারে, তাহলে একটি অদিকনির্দেশক লেখচিত্রের অ্যাডজেসেন্সি লিস্টের জন্য মোট $2|E|$‍ সংখ্যক উপাদান এখানে থাকবে। কেন $2|E|$‍? প্রতিটি প্রান্তবিন্দু $(i,j)$‍ অ্যাডজেসেন্সি লিস্টের দ্বিগুণ হিসেবে দেখা যাচ্ছে, $i$‍ এর লিস্টে একবার এবং $j$‍ এর লিস্টে একবার এবং $|E|$‍ সংখ্যক প্রান্তবিন্দু রয়েছে। একটি দিকনির্দেশক লেখচিত্রের জন্য, অ্যাডজেসেন্সি লিস্টে মোট $|E|$‍ সংখ্যক উপাদান আছে, প্রতিটি দিক নির্দেশক প্রান্তবিন্দুতে একটি করে উপাদান।

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।