গ্রাফ সংরক্ষণের জন্য ডেটা কাঠামো: বিদ্যমানগুলির একটি পর্যালোচনা এবং দুটি "প্রায় নতুন"

হাই সবাই

এই নোটে, আমি কম্পিউটার বিজ্ঞানে গ্রাফ সঞ্চয় করার জন্য ব্যবহৃত প্রধান ডেটা স্ট্রাকচারগুলি তালিকাভুক্ত করার সিদ্ধান্ত নিয়েছি, এবং আমি এমন আরও কয়েকটি কাঠামোর কথা বলব যেগুলি আমার জন্য একরকম "ক্রিস্টালাইজড"।

তো, শুরু করা যাক। তবে প্রথম থেকেই নয় - আমি মনে করি আমরা সবাই ইতিমধ্যেই জানি যে একটি গ্রাফ কী এবং সেগুলি কী (নির্দেশিত, অনির্দেশিত, ওজনযুক্ত, ওজনহীন, একাধিক প্রান্ত এবং লুপ সহ বা ছাড়া)।

তাহলে এবার চল. "গ্রাফ স্টোরেজ" এর জন্য ডেটা স্ট্রাকচারের জন্য আমাদের কী বিকল্প আছে?

1. ম্যাট্রিক্স ডেটা স্ট্রাকচার

1.1 অন্তিক ম্যাট্রিক্স. সংলগ্ন ম্যাট্রিক্স এমন একটি ম্যাট্রিক্স যেখানে সারি এবং কলামের শিরোনামগুলি গ্রাফের শীর্ষবিন্দুগুলির সংখ্যার সাথে মিলে যায় এবং এর প্রতিটি উপাদান a(i,j) এর মান শীর্ষবিন্দুগুলির মধ্যে প্রান্তের উপস্থিতি বা অনুপস্থিতি দ্বারা নির্ধারিত হয় i এবং j (এটা স্পষ্ট যে একটি অনির্দেশিত গ্রাফের জন্য এই ধরনের একটি ম্যাট্রিক্স প্রতিসম হবে, অথবা আমরা একমত হতে পারি যে আমরা সমস্ত মান শুধুমাত্র প্রধান তির্যকের উপরে সংরক্ষণ করি)। ওজনহীন গ্রাফের জন্য, a(i,j) কে i থেকে j পর্যন্ত প্রান্তের সংখ্যা দ্বারা সেট করা যেতে পারে (যদি এমন কোন প্রান্ত না থাকে, তাহলে a(i,j)= 0), এবং ওজনযুক্ত গ্রাফের জন্যও ওজন দ্বারা উল্লিখিত প্রান্তগুলির (মোট ওজন)।

1.2 ইনসিডেন্স ম্যাট্রিক্স। এই ক্ষেত্রে, আমাদের গ্রাফটি একটি সারণিতেও সংরক্ষিত থাকে যেখানে, একটি নিয়ম হিসাবে, সারি সংখ্যাগুলি এর শীর্ষবিন্দুগুলির সংখ্যাগুলির সাথে মিলিত হয় এবং কলাম সংখ্যাগুলি প্রাক-সংখ্যাযুক্ত প্রান্তগুলির সাথে মিলে যায়৷ যদি একটি শীর্ষবিন্দু এবং একটি প্রান্ত একে অপরের সাথে ঘটনা হয়, তাহলে সংশ্লিষ্ট কক্ষে একটি অ-শূন্য মান লেখা হয় (অনির্দেশিত গ্রাফের জন্য, 1 লেখা হয় যদি শীর্ষবিন্দু এবং প্রান্ত ঘটনা হয়, ওরিয়েন্টেড গ্রাফের জন্য - "1" যদি প্রান্ত শীর্ষবিন্দু থেকে "প্রস্থান" এবং "-1" যদি এটি "অন্তর্ভুক্ত" হয় (এটি মনে রাখা যথেষ্ট সহজ, কারণ "বিয়োগ" চিহ্নটি "-1" সংখ্যাটিতে "অন্তর্ভুক্ত" বলে মনে হয়)। ওজনযুক্ত গ্রাফের জন্য, আবার, 1 এবং -1 এর পরিবর্তে, আপনি প্রান্তের মোট ওজন নির্দিষ্ট করতে পারেন।

2. গণনা ডেটা স্ট্রাকচার

2.1 সংলগ্ন তালিকা। ভাল, এখানে সবকিছু সহজ বলে মনে হচ্ছে। গ্রাফের প্রতিটি শীর্ষবিন্দু, সাধারণভাবে, যেকোন গণনা কাঠামোর সাথে যুক্ত হতে পারে (তালিকা, ভেক্টর, অ্যারে, ...), যা প্রদত্ত একটির সংলগ্ন সমস্ত শীর্ষবিন্দুর সংখ্যা সংরক্ষণ করবে। নির্দেশিত গ্রাফগুলির জন্য, আমরা এই ধরনের তালিকায় শুধুমাত্র সেই শীর্ষবিন্দুগুলি যোগ করব যেখানে একটি বৈশিষ্ট্য শীর্ষবিন্দু থেকে একটি "নির্দেশিত" প্রান্ত রয়েছে। ওজনযুক্ত গ্রাফের জন্য বাস্তবায়ন আরও জটিল হবে।

2.2 পাঁজরের তালিকা। বেশ জনপ্রিয় ডাটা স্ট্রাকচার। প্রান্তের তালিকা, যেমন ক্যাপ্টেন স্পষ্টতা আমাদের বলে, আসলে গ্রাফের প্রান্তগুলির একটি তালিকা, যার প্রত্যেকটি প্রারম্ভিক শীর্ষবিন্দু, শেষ শীর্ষবিন্দু দ্বারা নির্দিষ্ট করা হয় (অনির্দেশিত গ্রাফগুলির জন্য এখানে ক্রম গুরুত্বপূর্ণ নয়, যদিও আপনি একীকরণের জন্য করতে পারেন বিভিন্ন নিয়ম ব্যবহার করুন, উদাহরণস্বরূপ, শীর্ষবিন্দুগুলিকে ক্রমবর্ধমান করার জন্য নির্দিষ্ট করা) এবং ওজন (শুধুমাত্র ওজনযুক্ত গ্রাফের জন্য)।

আপনি উপরে তালিকাভুক্ত ম্যাট্রিক্স তালিকাগুলি আরও বিশদে দেখতে পারেন (এবং চিত্র সহ), উদাহরণস্বরূপ, এখানে.

2.3 সংলগ্ন অ্যারে। সবচেয়ে সাধারণ কাঠামো নয়। এর মূল অংশে, এটি একটি গণনা কাঠামোর মধ্যে "প্যাকিং" সংলগ্ন তালিকার একটি রূপ (অ্যারে, ভেক্টর)। এই ধরনের অ্যারের প্রথম n (গ্রাফের শীর্ষবিন্দুর সংখ্যা অনুসারে) উপাদানগুলিতে একই অ্যারের প্রারম্ভিক সূচক থাকে, যেখান থেকে প্রদত্তটির সংলগ্ন সমস্ত শীর্ষবিন্দু একটি সারিতে লেখা হয়।

এখানে আমি সবচেয়ে বোধগম্য (নিজের জন্য) ব্যাখ্যা পেয়েছি: ejuo.livejournal.com/4518.html

3. অ্যাডজাসেন্সি ভেক্টর এবং অ্যাসোসিয়েটিভ অ্যাডজাসেন্সি অ্যারে

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

3.1 সংলগ্ন ভেক্টর

কেস (a1): ওজনহীন গ্রাফ

ওজনহীন গ্রাফের জন্য আমরা একটি সংলগ্ন ভেক্টরকে বলব একটি জোড় সংখ্যার পূর্ণসংখ্যা (a[2i], a[2i+1],..., যেখানে i সংখ্যা করা হয়েছে c 0), যার প্রতিটি জোড়া সংখ্যা a[2i], a[2i+1] যথাক্রমে a[2i] এবং a[2i+1] শীর্ষবিন্দুর মধ্যে একটি গ্রাফ প্রান্ত নির্দিষ্ট করে।
এই রেকর্ডিং বিন্যাসে গ্রাফ নির্দেশিত কিনা সে সম্পর্কে তথ্য নেই (উভয় বিকল্পই সম্ভব)। ডিগ্রাফ বিন্যাস ব্যবহার করার সময়, প্রান্তটিকে a[2i] থেকে a[2i+1] তে নির্দেশিত বলে মনে করা হয়। এখানে এবং নীচে: অনির্দেশিত গ্রাফগুলির জন্য, যদি প্রয়োজন হয়, রেকর্ডিং শীর্ষবিন্দুর ক্রমগুলির জন্য প্রয়োজনীয়তাগুলি প্রয়োগ করা যেতে পারে (উদাহরণস্বরূপ, এটিতে নির্ধারিত সংখ্যার নিম্ন মান সহ শীর্ষবিন্দুটি প্রথমে আসে)।

C++ এ, std::vector ব্যবহার করে একটি সংলগ্ন ভেক্টর নির্দিষ্ট করার পরামর্শ দেওয়া হয়, তাই এই ডেটা স্ট্রাকচারের নাম।

কেস (a2): ওজনহীন গ্রাফ, প্রান্তের ওজন পূর্ণসংখ্যা

কেস (a1) এর সাথে সাদৃশ্য অনুসারে, আমরা পূর্ণসংখ্যার প্রান্তের ওজন সহ একটি ভারযুক্ত গ্রাফের জন্য সংলগ্ন ভেক্টরকে সংখ্যার একটি অর্ডারযুক্ত সেট (ডাইনামিক অ্যারে) বলি (a[3i], a[3i+1], a[3i+2], ..., যেখানে i সংখ্যা করা হয় c 0), যেখানে সংখ্যার প্রতিটি "ট্রিপলেট" a[3i], a[3i+1], a[3i+2] a[3i] নম্বরযুক্ত শীর্ষবিন্দুগুলির মধ্যে গ্রাফের একটি প্রান্ত নির্দিষ্ট করে এবং a[3i+1], যথাক্রমে, এবং a [3i+2] মান হল এই প্রান্তের ওজন। যেমন একটি গ্রাফ এছাড়াও নির্দেশিত বা না হতে পারে.

কেস (বি): ওজনহীন গ্রাফ, অ-পূর্ণসংখ্যা প্রান্তের ওজন

যেহেতু একটি অ্যারেতে (ভেক্টর) ভিন্ন ভিন্ন উপাদান সংরক্ষণ করা অসম্ভব, উদাহরণস্বরূপ, নিম্নলিখিত বাস্তবায়ন সম্ভব। গ্রাফটি একজোড়া ভেক্টরে সংরক্ষিত থাকে, যেখানে প্রথম ভেক্টরটি গ্রাফের সংলগ্ন ভেক্টর হয় ওজন নির্দিষ্ট না করেই, এবং দ্বিতীয় ভেক্টরে সংশ্লিষ্ট ওজন থাকে (C++: std::pair-এর জন্য সম্ভাব্য বাস্তবায়ন ) এইভাবে, প্রথম ভেক্টরের সূচী 2i, 2i+1 এর অধীনে এক জোড়া শীর্ষবিন্দু দ্বারা সংজ্ঞায়িত একটি প্রান্তের জন্য, ওজন দ্বিতীয় ভেক্টরের সূচক i এর অধীনে উপাদানের সমান হবে।

আচ্ছা, কেন এই প্রয়োজন?

ঠিক আছে, এই লাইনগুলির লেখক এটি বেশ কয়েকটি সমস্যা সমাধানের জন্য বেশ কার্যকর বলে মনে করেছেন। ঠিক আছে, একটি আনুষ্ঠানিক দৃষ্টিকোণ থেকে, নিম্নলিখিত সুবিধাগুলি থাকবে:

• সংলগ্ন ভেক্টর, অন্য যেকোনো "গণনামূলক" কাঠামোর মতো, বেশ কম্প্যাক্ট, সংলগ্ন ম্যাট্রিক্সের (স্পার্স গ্রাফের জন্য) তুলনায় কম মেমরি নেয় এবং এটি বাস্তবায়ন করা তুলনামূলকভাবে সহজ।
• গ্রাফের শীর্ষবিন্দুগুলি, নীতিগতভাবে, নেতিবাচক সংখ্যা দিয়েও চিহ্নিত করা যেতে পারে। যদি এই ধরনের একটি "বিকৃতি" প্রয়োজন হয়?
• গ্রাফগুলিতে বিভিন্ন ওজন (ধনাত্মক, ঋণাত্মক, এমনকি শূন্য) সহ একাধিক প্রান্ত এবং একাধিক লুপ থাকতে পারে। এখানে কোন বিধিনিষেধ নেই।
• আপনি প্রান্তগুলিতে বিভিন্ন বৈশিষ্ট্যও বরাদ্দ করতে পারেন - তবে সে সম্পর্কে আরও জানতে, বিভাগ 4 দেখুন।

যাইহোক, এটা অবশ্যই স্বীকার করতে হবে যে এই "তালিকা" প্রান্তে দ্রুত অ্যাক্সেস বোঝায় না। এবং এখানে অ্যাসোসিয়েটিভ অ্যাডজাসেন্সি অ্যারে উদ্ধারে আসে, যা নীচে আলোচনা করা হয়েছে।

3.2 সহযোগী সংলগ্ন অ্যারে

সুতরাং, যদি একটি নির্দিষ্ট প্রান্তে অ্যাক্সেস, এর ওজন এবং অন্যান্য বৈশিষ্ট্যগুলি আমাদের জন্য গুরুত্বপূর্ণ হয়, এবং মেমরির প্রয়োজনীয়তাগুলি আমাদের সংলগ্ন ম্যাট্রিক্স ব্যবহার করার অনুমতি দেয় না, তাহলে আসুন আমরা এই সমস্যাটি সমাধান করার জন্য কীভাবে সংলগ্ন ভেক্টর পরিবর্তন করতে পারি সে সম্পর্কে চিন্তা করি। সুতরাং, কীটি গ্রাফের একটি প্রান্ত, যাকে পূর্ণসংখ্যার একটি ক্রমযুক্ত জোড়া হিসাবে নির্দিষ্ট করা যেতে পারে। এটা দেখতে কেমন? এটি একটি সহযোগী অ্যারে একটি কী না? এবং, যদি তাই হয়, কেন আমরা এটি বাস্তবায়ন করি না? আমাদের একটি সহযোগী অ্যারে আছে যেখানে প্রতিটি কী - পূর্ণসংখ্যার একটি ক্রমযুক্ত জোড়া - একটি মানের সাথে যুক্ত হবে - একটি পূর্ণসংখ্যা বা একটি বাস্তব সংখ্যা যা প্রান্তের ওজন নির্দিষ্ট করে। C++ এ, std::map ধারক (std::map) এর উপর ভিত্তি করে এই কাঠামোটি বাস্তবায়ন করার পরামর্শ দেওয়া হয় , int> বা std::map , double>), অথবা std::multimap যদি একাধিক প্রান্ত প্রত্যাশিত হয়। ঠিক আছে, আমাদের কাছে গ্রাফ সংরক্ষণের জন্য একটি কাঠামো রয়েছে যা "ম্যাট্রিক্স" কাঠামোর চেয়ে কম মেমরি নেয়, একাধিক লুপ এবং প্রান্ত সহ গ্রাফগুলিকে সংজ্ঞায়িত করতে পারে এবং এমনকি শীর্ষবিন্দু সংখ্যাগুলির অ-নেতিবাচকতার জন্য কঠোর প্রয়োজনীয়তাও নেই (আমি জানি না কার এটি প্রয়োজন, কিন্তু এখনও)।

4. ডেটা স্ট্রাকচার পূর্ণ, কিন্তু কিছু অনুপস্থিত

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

সুতরাং, আমাদের একটি ওজনহীন গ্রাফ আছে, যার প্রতিটি প্রান্তের জন্য এটি সংরক্ষণ করা প্রয়োজন, উদাহরণস্বরূপ, পূর্ণসংখ্যা দ্বারা নির্দিষ্ট 2টি অতিরিক্ত বৈশিষ্ট্য। এই ক্ষেত্রে, এটির সংলগ্ন ভেক্টরকে "জোড়া" নয়, পূর্ণসংখ্যার (a[2i], a[2i+1], a[2i+2], a (a[2i], a[3i+2], a" জোড়ার "চতুর্থাংশ" ক্রমানুসারে সংজ্ঞায়িত করা সম্ভব। [2i+2]…), যেখানে a[3i+2] এবং a[3i+2] সংশ্লিষ্ট প্রান্তের বৈশিষ্ট্য নির্ধারণ করবে। প্রান্তের পূর্ণসংখ্যা ওজন সহ একটি গ্রাফের জন্য, ক্রমটি সাধারণত একই রকম হয় (শুধু পার্থক্য হল যে বৈশিষ্ট্যগুলি প্রান্তের ওজন অনুসরণ করবে এবং a[4i+4] এবং a[5i+XNUMX] উপাদান দ্বারা নির্দিষ্ট করা হবে , এবং প্রান্তটি নিজেই XNUMX নয়, XNUMXটি আদেশকৃত সংখ্যা নির্দিষ্ট করা হবে)। এবং অ-পূর্ণসংখ্যা প্রান্ত ওজন সহ একটি গ্রাফের জন্য, বৈশিষ্ট্যগুলি তার ওজনহীন উপাদানে লেখা যেতে পারে।

পূর্ণসংখ্যার প্রান্তের ওজন সহ গ্রাফগুলির জন্য একটি সহযোগী সংলগ্ন অ্যারে ব্যবহার করার সময়, এটি একটি মান হিসাবে নির্দিষ্ট করা সম্ভব একটি একক সংখ্যা নয়, তবে সংখ্যাগুলির একটি অ্যারে (ভেক্টর) যা নির্দিষ্ট করে, একটি প্রান্তের ওজন ছাড়াও, এর অন্যান্য সমস্ত প্রয়োজনীয়। বৈশিষ্ট্য একই সময়ে, অ-পূর্ণসংখ্যা ওজনের ক্ষেত্রে একটি অসুবিধার জন্য একটি ফ্লোটিং পয়েন্ট নম্বর সহ একটি চিহ্ন নির্দিষ্ট করার প্রয়োজন হবে (হ্যাঁ, এটি একটি অসুবিধা, তবে যদি এমন অনেকগুলি লক্ষণ না থাকে এবং আপনি যদি না করেন তবে সেগুলিকে খুব "কঠিন" ডাবল সেট করবেন না, তাহলে এটি কিছুই হতে পারে)। এর মানে হল যে C++ বর্ধিত অ্যাসোসিয়েটিভ অ্যাডজাসেন্সি অ্যারেগুলিকে নিম্নরূপ সংজ্ঞায়িত করা যেতে পারে: std::map , std::vector> অথবা std::map , std::vector, যেখানে "কী-মান-ভেক্টর"-এর প্রথম মান হবে প্রান্তের ওজন, এবং তারপরে এর বৈশিষ্ট্যগুলির সংখ্যাসূচক উপাধিগুলি অবস্থিত।

তথ্যসূত্র:

সাধারণভাবে গ্রাফ এবং অ্যালগরিদম সম্পর্কে:

1. কোরমেন, টমাস এইচ., লিজারসন, চার্লস আই., রিভেস্ট, রোনাল্ড এল., স্টেইন, ক্লিফোর্ড। অ্যালগরিদম: নির্মাণ এবং বিশ্লেষণ, ২য় সংস্করণ: অনুবাদ। ইংরেজী থেকে – এম.: উইলিয়ামস পাবলিশিং হাউস, 2।
2. হারারি ফ্রাঙ্ক। গ্রাফ তত্ত্ব। এম.: মীর, 1973।
এই একই ভেক্টর এবং সংলগ্নদের সহযোগী অ্যারে সম্পর্কে লেখকের প্রতিবেদন:
3. চেরনোখভ এস.এ. গ্রাফ প্রতিনিধিত্ব এবং সঞ্চয় করার উপায় হিসাবে অ্যাডজাসেন্সি ভেক্টর এবং অ্যাসোসিয়েটিভ অ্যাডজাসেন্সি অ্যারে / SA Chernouhov। একটি গ্রাফ প্রতিনিধিত্ব করার জন্য ডেটা স্ট্রাকচার হিসাবে সংলগ্ন ভেক্টর এবং সংলগ্ন মানচিত্র // আন্তর্জাতিক বৈজ্ঞানিক ও ব্যবহারিক সম্মেলনের নিবন্ধগুলির সংগ্রহ "উদ্ভাবনী উন্নয়নের ফলাফলগুলি বাস্তবায়নের সমস্যা এবং সেগুলি সমাধানের উপায়" (সারতোভ, সেপ্টেম্বর 14.09.2019, 2019)। – Sterlitamak: AMI, 65, p. 69-XNUMX
এই বিষয়ে দরকারী অনলাইন উত্স:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

উত্স: www.habr.com