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
Does y vary directly as x in this function? y= -3x+4
Harman [31]
Y = kx - <span>y varies directly as x in this function
</span> - y varies inversely as x in this function

For  y varies directly as x
For  y varies inversely as x
8 0
2 years ago
Read 2 more answers
Using the Pythagorean Theorem, find the length of a leg of a right triangle if the other leg is 8 ft long and the hypotenuse is
tatyana61 [14]
A^2+8^2=10^2
a^2+64=100
a^2=36
a=6

B.6FT
4 0
2 years ago
Please help
mina [271]

Answer: n3 when

Step-by-step explanation: just say he fell in the water

8 0
2 years ago
Estime 652 divied by 8
stich3 [128]
81.5 should be your answer. round to the nearest 10th and you get 82. hope this helps lol
8 0
3 years ago
Read 2 more answers
Triangle EFG, with vertices E(-9,2), F(-5,3), and G(-7,5), is drawn inside a rectangle, as shown below.
Lady bird [3.3K]

Check the picture below.

so hmmm let's get the whole area of the rectangle, and then <u>get the areas of those 3 triangles and subtract their area from that of the rectangle's,</u> what's leftover is what we didn't subtract, namely, the white triangle.

\stackrel{\textit{\huge Areas}}{\stackrel{rectangle}{(3)(4)}~~ - ~~\stackrel{green~triangle}{\cfrac{1}{2}(2)(3)}~~ - ~~\stackrel{pink~triangle}{\cfrac{1}{2}(2)(2)}~~ - ~~\stackrel{yellow~triangle}{\cfrac{1}{2}(4)(1)}} \\\\\\ 12~~ - ~~3~~ - ~~2~~ - ~~2\implies 5

5 0
2 years ago
Other questions:
  • The specific gravity of a substance is the ratio of its weight to the weight of an equal volume of water. Kerosene weighs 0.82 g
    7·2 answers
  • A store gives away gift bags during a sale. Of these gift bags, 50% are green, 20% are yellow, and 30% are blue. The average num
    5·1 answer
  • Please help me with this
    6·1 answer
  • Natalie has 500 candy bars to sell for a fundraiser. Let C be the number of candy bars. Let P be the amount made from selling th
    11·1 answer
  • Can you graph a line if its slope is undefined? Explain.
    13·1 answer
  • The members of a film crew are at least 75 miles from their camp and must carry equipment back to camp before a storm arrives. T
    7·2 answers
  • 46÷6=? R ? What is the remainder for 46÷6= All i'm asking for is just the remainder.
    5·2 answers
  • I will mark you brainliest <br> what is 1+1
    15·1 answer
  • The following are the last 10 run scores Colin got in cricket:
    5·2 answers
  • A figure is reflected across the x-axis to create a new figure. Which rule describes this transformation?
    12·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!