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
A phone company charges a flat rate of $15 to make phone calls for a month.they charge $0.10 per minute for each call made.if th
Ne4ueva [31]

Answer:

450 minutes

Step-by-step explanation:

15 + 0.1x = 60

15 - 15 + 0.1x = 60 - 15

0.1x = 45

\frac{0.1x}{0.1} = \frac{45}{0.1}

x = 450

5 0
3 years ago
Read 2 more answers
Determine if the statement is true or false.
seropon [69]

Answer:

False

Step-by-step explanation:

There are two concepts:

1. Row Echelon Form: There can be more than two <em>row echelon forms</em> of a single matrix, so different sequences of row operations can lead to different <em>row echelon forms</em> of a single matrix.

2. Reduced Row Echelon Form: It's unique for each matrix, so different sequences of row operations always lead to the same <em>reduced row echelon form</em> for the same matrix.

7 0
3 years ago
ÑÈÈĐ ÂÑŠWÈŘ ÃŚÃP
Mila [183]

Answer:

629.9

Step-by-step explanation:

5 0
3 years ago
PLEASE HELPPPPPPPPPPPPPPPPPPPPPPP
lara [203]

F=\{\ x\ |\ x

F ∪ H is defined as the set that consists of all elements belonging to either set F or set H (or both).

F ∩ H is defined as the set composed of all elements that belong to both F and H

4 0
3 years ago
Match the circle equations in general form with their corresponding equations in standard form. x2 + y2 − 4x + 12y − 20 = 0 (x −
Lemur [1.5K]
The equation form of a circle is (x - a)² + (y - b)² = r²

Equation 1:

x² - 4x + y² + 12y - 20 = 0 ⇒ use the completing the square method for x² - 4x and y² + 12y

x² - 4x = (x - 2)² - 4
y² + 12y = (y + 6)² - 36

Put them back together, we have
(x - 2)² - 4 + (y + 6)² - 36 - 20 = 0
(x - 2)² + (y + 6)² -4 - 36 - 20 = 0
(x - 2)² + (y + 6)² - 60 = 0
(x - 2)² + (y + 6)² = 60

Equation 2:

x² + y² + 6x - 8y - 10 = 0
(x² + 6x) + (y² - 8y) -10 = 0
(x + 3)² - 9 + (y - 4)² -16 - 10 = 0
(x + 3)² + (y - 4)² - 9 - 16 - 10 = 0
(x + 3)² + (y - 4)² - 35 = 0
(x + 3)² + (y - 4)² = 35

Equation 3:

3x² + 12x + 3y² +18y - 15 = 0
3 [x² + 4x + y² + 6y - 5] = 0
x² + 4x + y² + 6y - 5 = 0
(x² + 4x) + (y² + 6y) - 5 = 0
(x + 2)² - 4 + (y + 3)² - 9 - 5 = 0
(x + 2)² + (y + 3)² - 4 - 9 -5 = 0
(x + 2)² + (y + 3)² - 18 = 0
(x + 2)² + (y + 3)² = 18

Equation 4:

5x² + 5y² - 10x + 20y - 30 = 0
5 [x² + y² - 2x + 4y - 6] = 0
x² + y² - 2x + 4y - 6 = 0
(x² - 2x) + (y² + 4y) - 6 = 0
(x - 1)² - 2 + (y + 2)² - 4 - 6 =0
(x - 1)² + (y + 2)² - 2 - 4 - 6 = 0
(x - 1)² + (y + 2)² - 12 = 0
(x - 1)² + (y + 2)² = 12

Equation 5:

2x² + 2y² - 24x - 16y -8 = 0
2 [x² + y² - 12x - 8y - 4] = 0
x² + y² - 12x - 8y - 4 = 0
(x² - 12x) + (y² - 8y) - 4 = 0
(x - 6)² - 36 + (y - 4)² - 16 - 4 = 0
(x - 6)² + (y - 4)² -36 - 16 - 4 = 0
(x - 6)² + (y - 4)² - 56 = 0
(x - 6)² + (y - 4)² = 56

Equation 6:

x² + y² + 2x - 12y - 9 = 0
(x² + 2x) + (y² - 12y) - 9 = 0
(x + 1)² - 1 + (y - 6)² - 36 - 9 = 0
(x + 1)² + (y - 6)² - 1 - 36 - 9 = 0
(x + 1)² + (y - 6)² - 46 = 0
(x + 1)² + (y - 6)² = 46


3 0
3 years ago
Read 2 more answers
Other questions:
  • The weight of an apple is 150g rounded to the nearest 5g
    12·1 answer
  • A florist has 36 red roses and 42 white roses. The florist wants to put an equal number of roses in each centerpiece along with
    6·2 answers
  • Ara has a cube with side lengths of 4.2 cm. Which is the best estimate of the volume of the cube?
    11·1 answer
  • What is the answer to 7+4p-6
    9·2 answers
  • Find the measure of angle y. Round your answer to the nearest hundredth.
    6·2 answers
  • Posting algebra again :/
    14·1 answer
  • Brian invests £4900 into his bank account.
    5·2 answers
  • Ralph bought 3 boxes with 20 pencils each and 4 boxes with 10 pens each. To find the total number of pencils and pens, Ralph eva
    7·2 answers
  • Can i have help with this
    15·2 answers
  • Parvinis older than Jan, who is
    10·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!