นับจำนวนขอบในกราฟที่ไม่มีทิศทางใน C++

เนื่องจากภารกิจคือการนับจำนวนขอบในกราฟที่ไม่มีทิศทาง กราฟแบบไม่บอกทิศทางคือชุดของจุดยอดที่เชื่อมต่อเข้าด้วยกันเพื่อสร้างกราฟ ซึ่งขอบทั้งหมดเป็นแบบสองทิศทาง กราฟแบบไม่มีทิศทางสามารถเคลื่อนที่ไปในทิศทางใดก็ได้จากโหนดหนึ่งไปยังโหนดอื่นที่เชื่อมต่ออยู่

ด้านล่างนี้คือการแสดงภาพของกราฟที่ไม่มีทิศทาง

จากโจทย์ เราต้องหาจำนวนขอบในกราฟแบบไม่บอกทิศทาง

ขอบในกราฟคือเส้นที่เชื่อมจุดยอดสองจุดเข้าด้วยกัน

ป้อนข้อมูล −

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 ให้ประกาศตัวแปร count=0 ซึ่งจะคืนค่าจำนวนขอบ

• สำรวจรายการโดยใช้การวนซ้ำจนกว่าเราจะถึงจุดยอดสุดท้ายและเพิ่มค่าของ count ด้วย graph_list[i].size() และเก็บกลับไปที่ตัวแปรการนับ

• หลังจากที่เราไปถึงจุดยอดสุดท้ายแล้ว ให้หารค่าการนับด้วยสองแล้วพิมพ์ผลลัพธ์ออกมา

ตัวอย่าง

#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