COSC 2436 Lab 7: Graphs
1. Introduction
Given a list of edges in a graph, determine if the graph has a valid path from a given
source vertex to a destination vertex. Using either BFS or DFS algorithm
implementation, you can check if the destination vertex had been visited or not after
traversing the graph from the source vertex. You can use any STL implementation for
this lab.
2. Input File
- The first line will contain an integer that indicates the number of vertices
(nodes).
- The second line will contain two integers that indicate the source node and the
destination node.
- Each of the following lines will contain two integers a and b, which indicates an
edge between a and b.
- Each edge is bi-directional, meaning this graph is undirected.
- There will be no blank lines to skip
3. Output File
- Output “true” if there is a valid path from the source node to the destination
node. Otherwise, output “false”.
4. Examples
input1.txt
8 (this represents the number of nodes)
5 2 (source node is 5, destination node is 2)
0 1 (there is an edge from node 0 to node 1, and node 1 to node 0)
1 3
1 5
2 7
3 4
4 5
4 6
output1.txt
false
5. Turn in your lab assignment
Lab 7 needs to be turned into our Linux server, follow the link here
https://rizk.netlify.app/courses/cosc2430/2_resources/
Make sure to create a folder under your root directory, name it lab7 (the name must be
lowercase), and only copy your code to this folder, no test cases or other files are
needed.
PS: This document may have typos, if you think something is illogical, please email the
TAs for confirmation.
