$29
QUESTIONS (Write a program to find the adjacency list of a given directed graph)
1. Write a program to find the adjacency list of a given directed graph G which is represented as
adjacency matrix.
Input Format:
• The first line of the input contains a positive integer n, the number of vertices in the graph, in the range 1 to 1000.
• The next lines represents the Adjacency matrix representation of the given graph.
Output Format:
Then lines contain the adjacency list of each node in ascending order. Each line contains the label of the respective node followed by the nodes adjacent to it sorted in ascending order from left to right separated by single space. If a node has no adjacent nodes, then the line corresponding to its adjacency list will contain
the label of that node only.
Note: In a graph with n vertices, the vertices are labeled from 0 to n − 1.
Sample Input:
5
01001
00100
00000
00100
00010
Sample Output:
014
12
23
• 3
32
• 3
2. You are given a connected undirected graph G. Write a program for Breadth First Traversal (BFS) of the graph. Find the BFS traversal of the graph starting from the 0th vertex from left to right according to the graph.
Input Format:
• First line consists of V, the number of vertices in the graph, in the range 1 to 1000.
• The subsequent n lines contains the label of the respective node followed by the nodes adjacent to it in ascending order.
Output Format:
• The corresponding Depth First traversal.
Sample Input 1:
5
0123
10
204
30
• 2
Sample Output 1:
01234
2
Scanned with CamScanner
Sample Input 2:
4
013
102
21
30
Sample Output 2:
0132
3. You are given a connected undirected graph G. Write a program for Depth First Traversal (DFS) of the graph. You can use a recursive approach to find the DFS traversal of the graph starting from the Oth vertex from left to right according to the graph.
Input Format:
• First line consists of V, the number of vertices in the graph, in the range 1 to 1000.
• The subsequent n lines contains the label of the respective node followed by the nodes adjacent to it in ascending order.
Output Format:
• The corresponding Depth First traversal.
Sample Input 1:
5
0123
10
204
30
42
Sample Output 1:
01243
Sample Input 2:
4
013
102
21
30
Sample Output 2:
0123
4. Write a program to compute the minimum spanning tree of a connected undirected graph G using
the following algorithms:
(a) Kruskal's algorithm
(b) Prim's algorithm
Input Format:
• First line contains a character from { 'a', 'b'}:
If the input character is 'a' then compute the minimum spanning tree using Kruskal's algorithm
3
Scanned with CamScanner
Else if the character is 'b' compute the minimum spanning tree using Prim's algorithm
• Second line contains an integer n Є [1, 1000], that denotes the number of vertices in the graph.
• The subsequent n lines contain the label of the respective node followed by the nodes adjacent to it sorted in ascending order from left to right separated by single space.
• The subsequent n lines contain label of the respective node followed by the weights of the edges corresponding to the adjacency list separated by single space. The edge weights are real numbers in the range [-10000, 10000].
Further, no two edges have the same weight.
Output Format:
• Single line containing the sum of the edge weights of the minimum spanning tree.
Sample Input 1:
a
7
015
1026
213
3246
• 356
504
6134
02810
1281614
21612
3122218
4222524
51025
6141824
Sample Output 1:
99
Sample Input 2:
b
7
015
1026
213
3246
• 3 5 6
504
6134
02810
1281614
21612
3122218
4222524
51025
6141824
Sample Output 2:
99
5. Write a program that implements Dijkstra's algorithm for computing shortest paths in a directed
graph with positive edge weights. Assume that the nodes are labeled from 0 to n -
• 1.
4
Scanned with CamScanner
Input Format:
• The first line of the input contains a positive integer n = [1, 1000], the number of nodes in the graph.
• The subsequent n lines contain the label of the respective node followed by the nodes adjacent to it, sorted in ascending order from left to right separated by single space. If a node has no adjacent nodes, then the line corresponding to its adjacency list will contain the label of that node only.
• The subsequent n lines contain label of the respective node followed by the weights of the edges corresponding to the adjacency list separated by single space. The edge weights are positive real numbers in the range (0, 10000]. If a node has no adjacent nodes, then the line corresponding to its adjacent edge weights will contain the label of that node only.
• The rest of the input consists of multiple lines, each one containing a four-letter string followed by zero, one or two integers. The integers, if given, will be in the range 0 to n-1.
—
-
The string "apsp" is followed by a single integer, the label of the source vertex.
Print the shortest path distance from the source vertex to all the n vertices in the graph,
sorted in the order of their labels, in single space separated format. Print "INF" for
nodes that are
The string "sssp" is followed by two integers, respectively, labels of the source and des- tination nodes. Print the shortest path from the source node to the destination node, if such a path exists. Print "UNREACHABLE", otherwise.
The string "stop" means terminate the program.
Output Format:
The output, if any, of each command should be printed on a separate line.
Sample Input:
9
014
15
23
• 6
4
5278
62
74
857
0220
• 3
27
• 5
4
5164
60
72
• 21
apsp
0
sssp 06
sssp 07
sssp 5 6
sssp 8 7
sssp 40
stop
LO
5
Scanned with CamScanner
Sample Output:
02613125 18109
18
10
13
1
UNREACHABLE
Note: For further queries contact
SEEMA seema_p210047cs@nitc.ac.in
Scanned with CamScanner
