Scribd
Upload
11 views2 pages

DSA 1 Lab Assignment 2

The document outlines an assignment for a Data Structure and Algorithms lab at United International University, focusing on two problems. The first problem involves finding the minimum number of edges between two vertices in an undirected graph using Breadth First Search (BFS). The second problem requires calculating the lowest travel cost for Mr. Lee to visit various branches using Depth First Search (DFS).

Uploaded by

asifaaron62
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views2 pages

DSA 1 Lab Assignment 2

The document outlines an assignment for a Data Structure and Algorithms lab at United International University, focusing on two problems. The first problem involves finding the minimum number of edges between two vertices in an undirected graph using Breadth First Search (BFS). The second problem requires calculating the lowest travel cost for Mr. Lee to visit various branches using Depth First Search (DFS).

Uploaded by

asifaaron62
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

United International University (UIU)

Dept. of Computer Science & Engineering (CSE)


CSE 2216: Data Structure and Algorithms 1 Lab
Assignment 2

Problem 1: You are given an undirected graph G(V, E) with N vertires and M edges. You need to
find the minimum number of edges between a given pair of vertices (u, v) using Breadth First
Search (BFS).
For example, the minimum number of edges between vertices (1,5) in the following graph is 2
since (1, 2) and (2, 5) are the only edges resulting in the shortest path between 1 and 5.

Input Ou¢put

V=9 Min number of edges between (0, 5): 3


0 1 Min number of edges between (3, 8): 2
0 7 Mín number of edges between (2, 6): 2
1 7
1 2
2 3
2 5
2 8
3 4
3 5
4 5
5 6
6 7
7 8
findMinNumberEdges(0, 5)
findMinNumberEdges(3, 8)
findM inNumberEdges(2, 6)
Problem 2: Mr. Lee has to travel to various branches abroad to assist his company. But he has
a problem. The cost would be really high as all branches he has to visit are in foreign countries.
He wants to visit every location only one time and return home with the lowest expense. Help
this company-caring man calculate the lowest expense using Depth First Search (DFS).

[Input format]
N, the number of branches (including office) to visit. At this moment, the No. 1 office is regarded as
his company (Departure point). Costs are given to move cities in which branches are located from
the second line to N number lines. i.e. jth column of ith row is the cost to move from ith city to jth
city. If it is impossible to move between two cities, it is given as zero.

[Output format]
Output the minimum cost used to depart from his office, visit all branches, and then return to his
home.

Input Output

Enter N: 5 Minimum cost: 30


0 14 4 10 20

14 0 7 8 7
4 5 0 7 16
11 7 9 0 2
18 7 17 4 0

Enter N: 5 Minimum cost: 18


9 9 2 9 S
6 3 5 1 5
1 8 3 3 3
6 0 9 6 8
6 6 9 4 8

1. Make two separate C/C++ files for the problems.

You might also like