Implement Prim's algorithm to determine the Minimum Spanning Tree of a weighted undirected connected graph with N nodes. Use a adiacency matrix to represent the graph.
The input is given in a text file with following format:
The first line contains the total number of nodes, N.
The second line contains the total number of edges, M.
The next lines contain the edges, given as triplets of three numbers.
Number1 and number2 are integers in the range 0..N-1, representing node ID's
and number3 is a positive number representing the weight of the edge.
The output of the program is the total cost of the MST.
Use input data from files given here
Implement Prim's algorithm to determine the Minimum Spanning Tree of a weighted undirected connected graph with N nodes. Use a adiacency matrix to represent the graph.
The input is given in a text file with following format:
The first line contains the total number of nodes, N.
The second line contains the total number of edges, M.
The next lines contain the edges, given as triplets of three numbers.
Number1 and number2 are integers in the range 0..N-1, representing node ID's
and number3 is a positive number representing the weight of the edge.
The output of the program is the total cost of the MST and the list of edges which compose the MST.
Use input data from files given here
Implement Prim's algorithm to determine the Minimum Spanning Forest of a weighted undirected graph with N nodes, the graph can be a disconnected graph. Use a adiacency matrix to represent the graph.
The input is given in a text file with following format:
The first line contains the total number of nodes, N.
The second line contains the total number of edges, M.
The next lines contain the edges, given as triplets of three numbers.
Number1 and number2 are integers in the range 0..N-1, representing node ID's
and number3 is a positive number representing the weight of the edge.
The output of the program is the list of the MST that compose the forest. For each MST give its cost and the list of edges which compose the MST.
Use input data from files given here
Implement Prim's algorithm to determine the Minimum Spanning Tree of a weighted undirected connected graph with N nodes. Use adiacency lists to represent the graph and a priority queue based on heaps as auxiliary structure. You can use a priority queue from standard colections.
The input is given in a text file with following format:
The first line contains the total number of nodes, N.
The second line contains the total number of edges, M.
The next lines contain the edges, given as triplets of three numbers.
Number1 and number2 are integers in the range 0..N-1, representing node ID's
and number3 is a positive number representing the weight of the edge.
The output of the program is the total cost of the MST.
Use input data from files given here
Implement Kruskal's algorithm to determine the Minimum Spanning Tree of a weighted undirected connected graph with N nodes. Use a adiacency matrix to represent the graph. Use Disjoint Sets implemented with weighted union on lists.
The input is given in a text file with following format:
The first line contains the total number of nodes, N.
The second line contains the total number of edges, M.
The next lines contain the edges, given as triplets of three numbers.
Number1 and number2 are integers in the range 0..N-1, representing node ID's
and number3 is a positive number representing the weight of the edge.
The output of the program is the total cost of the MST and the set of edges which are part of the MST.
Use input data from files given here
Implement Kruskal's algorithm to determine the Minimum Spanning Tree Forest of a weighted undirected graph with N nodes. The graph may be disconnected. Use a adiacency structure with lists to represent the graph and Disjoint Sets with weighted union over linked lists as auxiliary structure.
The input is given in a text file with following format:
The first line contains the total number of nodes, N.
The second line contains the total number of edges, M.
The next lines contain the edges, given as triplets of three numbers.
Number1 and number2 are integers in the range 0..N-1, representing node ID's
and number3 is a positive number representing the weight of the edge.
The output of the program is the list of trees forming the minimum spanning tree forest. For each tree, give its cost and the set of edges which are part of the tree.
Use input data from files given here
Find how many distinct groups of friends are there. A group of friends is a group of persons where any two persons in the group are friends, either directly or indirectly.
The input of the program is a text file where on the first line we have N, the number of persons, the second line contains M the number of friendship relations and on the following M lines there are pairs of two names (the number id, between 0 and N-1) of persons which are direct friends.
The output is the number of distinct groups of friends. The program must build the solution while parsing the input file (do not store all direct relationships in memory - do NOT build the graph !).
Use input data from files given here (relations)
The cost of connecting two points [xi, yi] and [xj, yj] is the euclidian distance between them.
Compute the minimum cost to connect all points. All points are connected if there is exactly one simple path between any two points.
The input is a text file with the format: the first line contains the value of N while the next N lines contain pairs of integer numbers which are the x and y coordinates of the N points.
The output is the minimum cost to connect all the points.
Use input data from files given here (points)
The schedule of planned works is given in the form of triplets representing city1 city2 planned month.
Find the earliest time moment (earliest month) when all the cities will be connected by a network, or print that there will be no such moment. The cities are connected by a network if for any pair of cities there is a path between them.
The input is read from a text file in the form:
The first line contains the value of N
The second line contains the value of M
The next M lines contain triplets of 3 numbers: number1 number2 number3,
where number1 and number2
are city IDs (0..N-1) and number3 is a month (1..M).
Hint: use Disjoint Sets
Use input data from files given here
The input is read from a text file in the form:
The first line contains the value of N
The second line contains the value of M
The next M lines contain pairs: number1 number2
where number1 and number2
are city IDs (0..N-1) representing a planned road.
If the cities are not connected by the planned roads, propose new roads to be added to the construction plan. The proposal must contain a minimum number of new roads to be added such that cities become connected.
Hint: use Disjoint Sets
Use input data from files given here (relations)
Determine the maximum number of edges that can be removed so that both Alice and Bob still have enough edges so that they can have a path between any 2 nodes.
The input is read from a text file in the form:
The first line contains value of N.
The second line contains value of M.
The next M lines contain triplets of the form
(number1, number2, number3), where number1 and number2
are IDs of nodes (0..N-1) and number3 is the type of the edge (1, 2 or 3).
Use input data from files given here (alicebob)
Example:
Input: 4 6 0 1 2 0 2 3 0 3 1 1 2 2 1 3 1 2 3 2 Output: maximum number of edges to be removed is 2Hint: use Disjoint Sets and an adapted version of Kruskal to build the networks needed by Alice and Bob