यह देखते हुए कि कार्य एक अप्रत्यक्ष ग्राफ में किनारों की संख्या की गणना करना है। एक अप्रत्यक्ष ग्राफ एक ग्राफ बनाने के लिए एक साथ जुड़े हुए शिखरों का एक समूह है, जिसके सभी किनारे द्विदिश हैं। अप्रत्यक्ष ग्राफ़ किसी भी दिशा में एक नोड से दूसरे कनेक्टेड नोड तक जा सकते हैं।
नीचे अप्रत्यक्ष ग्राफ का एक दृश्य प्रतिनिधित्व है।
अब, समस्या के अनुसार हमें अप्रत्यक्ष ग्राफ में किनारों की संख्या ज्ञात करनी होगी।
ग्राफ़ में किनारे वे रेखाएँ होती हैं जिनसे दो शीर्ष जुड़े होते हैं।
इनपुट -
insert(graph_list, 0, 1); insert(graph_list, 0, 2); insert(graph_list, 1, 2); insert(graph_list, 1, 4); insert(graph_list, 2, 4); insert(graph_list, 2, 3); insert(graph_list, 3, 4);
आउटपुट -
count of edges are: 7
दृष्टिकोण हम उपरोक्त समस्या को हल करने का विकल्प चुनेंगे -
-
ग्राफ़ की सूची के सभी शीर्षों को संग्रहीत करने के लिए एक सूची प्रारंभ करें और उसके अनुसार मान डालें।
-
फंक्शन count_edges में, एक वेरिएबल काउंट =0 घोषित करें जो कि किनारों की गिनती लौटाने के लिए है।
-
एक लूप का उपयोग करके सूची को तब तक पार करें जब तक हम अंतिम शिखर तक नहीं पहुंच जाते और ग्राफ_लिस्ट [i]। आकार () के साथ गिनती का मान जोड़ते हैं और इसे वापस गिनती चर में संग्रहीत करते हैं।
-
अंतिम शीर्ष पर पहुंचने के बाद, गिनती के मान को दो से विभाजित करें, और परिणाम प्रिंट करें।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
//function to insert vertices
void insert(list<int> graph_list[], int u, int v){
graph_list[u].push_back(v);
graph_list[v].push_back(u);
}
//function to count the total number of edges
void count_edges(list<int> graph_list[], int v){
int count=0;
//traverse the loop till the vertice is found
for (int i = 0 ; i < v ; i++){
count += graph_list[i].size();
}
count = count/2;
cout<<"count of edges are: "<<count;
}
int main(int argc, char* argv[]){
//creating 5 vertices in a graph
int vertices = 5;
//declare list to create a graph and pass the vertices
list<int> graph_list[vertices];
//call insert function passing the list variable, vertice, linked vertice
insert(graph_list, 0, 1);
insert(graph_list, 0, 2);
insert(graph_list, 1, 2);
insert(graph_list, 1, 4);
insert(graph_list, 2, 4);
insert(graph_list, 2, 3);
insert(graph_list, 3, 4);
//calling count function that will count the edges
count_edges(graph_list, vertices);
return 0 ;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो हमें निम्न आउटपुट मिलेगा -
count of edges are: 7