1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Aleks04 [339]
3 years ago
8

Using the Breadth-First Search Algorithm, determine the minimum number of edges that it would require to reach

Mathematics
1 answer:
jekas [21]3 years ago
8 0

Answer:

The algorithm is given below.

#include <iostream>

#include <vector>

#include <utility>

#include <algorithm>

using namespace std;

const int MAX = 1e4 + 5;

int id[MAX], nodes, edges;

pair <long long, pair<int, int> > p[MAX];

void initialize()

{

   for(int i = 0;i < MAX;++i)

       id[i] = i;

}

int root(int x)

{

   while(id[x] != x)

   {

       id[x] = id[id[x]];

       x = id[x];

   }

   return x;

}

void union1(int x, int y)

{

   int p = root(x);

   int q = root(y);

   id[p] = id[q];

}

long long kruskal(pair<long long, pair<int, int> > p[])

{

   int x, y;

   long long cost, minimumCost = 0;

   for(int i = 0;i < edges;++i)

   {

       // Selecting edges one by one in increasing order from the beginning

       x = p[i].second.first;

       y = p[i].second.second;

       cost = p[i].first;

       // Check if the selected edge is creating a cycle or not

       if(root(x) != root(y))

       {

           minimumCost += cost;

           union1(x, y);

       }    

   }

   return minimumCost;

}

int main()

{

   int x, y;

   long long weight, cost, minimumCost;

   initialize();

   cin >> nodes >> edges;

   for(int i = 0;i < edges;++i)

   {

       cin >> x >> y >> weight;

       p[i] = make_pair(weight, make_pair(x, y));

   }

   // Sort the edges in the ascending order

   sort(p, p + edges);

   minimumCost = kruskal(p);

   cout << minimumCost << endl;

   return 0;

}

You might be interested in
The value from the set {10, 11, 12, 13} that makes the equation 2(x − 5) = 12 true is <br>.​
Diano4ka-milaya [45]

Answer:

x = 11

Step-by-step explanation:

2(x - 5) = 12 ← divide both sides by 2

x - 5 = 6 ( add 5 to both sides )

x = 11

4 0
2 years ago
Read 2 more answers
while playing a game maria defeated 8 enemies with each enemy defeated earing her 7594 points if she traded in all her points fo
MAVERICK [17]
30,376 points per extra life
4 0
3 years ago
Read 2 more answers
Las coordenadas de su centro son (6,0) y pasa por el origen de<br> coordenadas.
Elza [17]

Answer:

U talk spanish dont know

Step-by-step explanation:

4 0
3 years ago
Maya, Josh, and Tom served a total of 126 orders Monday at the school cafeteria. Tom served 4 times as many orders as Maya. Josh
mart [117]

Answer:

Step-by-step explanation:

Std vhb th gfsxcfg hffhjhg

6 0
3 years ago
Read 2 more answers
48 POINTS! PLEASE HELP!<br> Show work please THANKS
CaHeK987 [17]

Answer:

C  multiply the first equation by 3

Step-by-step explanation:

3x-y =5

2x+3y = 10

We want to eliminate y

Since the first equation has a negative 1y  and the second equation has 3y

I would multiply the first equation by 3  and then the y's cancel

3(3x-y =5)

9x -3y = 15

2x+3y = 10

------------------

11x = 25

4 0
3 years ago
Read 2 more answers
Other questions:
  • jeff wants to buy a phone card for long distance calls. he can buy a 200-minute card for $10.00 or a 300-minute card for $12.00.
    13·2 answers
  • Please help as soon as possible I really need help rn I don’t get this at all
    5·1 answer
  • Which of the following is a typical cost associated with renting?
    9·1 answer
  • What is the simplified form of the quantity 9 x squared minus 25 over the quantity 3 x plus 5?
    6·2 answers
  • The ratio of the of a circle to its A}. Radius, Diameter, or Circumference to its B} Diameter, circumference, radius? approximat
    15·1 answer
  • A worker’s pay for one week was $312. She worked 39 hours. How much was she paid per hour?
    14·2 answers
  • I need help with this problem Geometry
    11·1 answer
  • Divide, using the polynomial long division algorithm. Fill in your work below
    6·1 answer
  • Sasha practices piano for 45 minutes, 6 days a week. How many minutes does Sasha practice in a week? Use an area model to solve.
    5·1 answer
  • On a Sunday , a football team give away souvenir footballs to each person entering the football stadium. one group received 42 f
    12·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!