CSCI 260 Fall 2026: Lab 4 : Graph Algorithms: BFS and DFS




 65% correctness, 20% design decisions, 15% style.
Style includes use of white space, comments, variable naming, among other factors.
Design decisions include information hiding, modularization, efficiency considerations, data organization, proper use of vectors, among other factors.

Graph Algorithms This lab builds on your graph data structure from Lab3. You will implement Breadth-First Search and Depth-First Search.



Getting started

  1. Use git to create the Lab4 repository.
  2. Copy over your Lab3 files for graph.cpp and graph.h. You can do this by changing directory to your csci260 directory, then executing the following commands:
    cp Lab3/*.cpp Lab4/.
    cp Lab3/*.h Lab4/.
    cp Lab3/makefile Lab4/.
    cp Lab3/gen Lab4/.
    The testapp.cpp file has been updated to reflect a larger menu of options for the user to select; please use this new testapp file and not the one from your Lab3. If it needs any fixes, let the instructor know.


The Input
Your program will read in graph data in the following form: 
5
0 1 24
1 4 3 
1 2 16
3 2 14
4 2 6 
4 2 9 
5 5 5
This file is interpreted as follows:
5 vertices, (implicitly named 0, 1, 2, 3, 4)
vertex 0 has an edge to vertex 1 with weight 24 (implicitly, since the graph is undirected, vertex 1 has an edge to vertex 0 with weight 24 as well.) vertex 1 has an edge to vertex 4 with weight 3; etc. That is, after reading in the number of vertices, integers are to be taken in triplets, where the first and second integers are the vertex numbers, and the third is the weight of the edge.

For ease of input, the file contains only integers.

The signal that the end of the file has been reached is when the first number in the triplet is any number ≥ n. Any triplets where the second integer is ≥ n should simply be ignored. If the file ends after reading two valid vertex numbers (i.e., no edge weight is given) the edge should be ignored and the graph input will be deemed completed.



The most important thing is correctness; second is comprehensibility, which includes good design, and third is is software engineering principles like polymorphism.
Your graph code must be your own. Do not use AI for code generation.


Your Task for this lab:
You have been provided with code structure to read in a weighted graph and run graph algorithms on the graph. You have updated it for your Lab3. You have also been provided with a testapp program and a header file.
Debug-print the graph is provided for you. For example, the output for a graph could be: 
0:    1 (24),
1:    0 (24), 4 (3), 2 (16),
2:    1 (16), 3 (14), 4 (9),
3:    2 (14),
4:    1 (3), 2 (9),


Your main tasks are as follows:

  1. (This task is carried over from Lab3.) Build on the code from Lab3 that constructs a graph, given the name of a file of graph data -- return 0 if not found, 1 if found. You are to use the Adjacency List representation. Note that each edge must be entered into two adjacency lists.
  2. Implement all of the following menu options: F L J T B D P H Q.
    You should update the testapp program to handle each of these command options.
    F means file, L list neighbours, J determine whether 2 vertices are adjacent, T spanning tree (you do not have to implment this, leave it as a stub), B list vertices ina BFS manner (prompt for a start vertex), D list vertices in a DFS manner (prompt for a start vertex) H for help with the command, Q to quit. You can leave in the options to add or remove an edge and start a new graph, but you do not need them for this lab.
  3. Implement BFS. Your program should just visit the vertices in the connected component containing the input vertex.
  4. Implement DFS. Your program should just visit the vertices in the connected component containing the input vertex.

You are to use the "testapp.cpp" and "graph.h" and "graph.cpp" files that you developed in Lab3 as a starting place. You will have to allow the edges to have weights, and ensure symmetry (for the undirected graphs that we assume). Weights will not be significant to BFS or DFS.

Duplicate edges, self-loops, and disconnected graphs
The input graphs may have any of the above. Your code should handle these situations gracefully. Your implementation from Lab3 should have dealt with duplicate edges: the 2nd edge overwrites the first. However, your program must be able to encounter self-loops.
For disconnected graphs, you should print out only the vertices reachable from the input vertex.

Test your code thoroughly.


Everything but the data files and the makefile should bear your complete name and student number. Code should be well-documented and well designed. Files are to be submitted via git.


Here is the perl file for generating a graph file at random.

#!/usr/bin/perl
use strict;
use warnings;

my $n;
my $m;
my $w;

# you may want to hash-out/ comment out the printing, or just remove
# the prompts from the files you generate, if you use >> to gen the
# data into a file
print "How many vertices: ";
$n = ;

print "How many edges: ";
$m = ;

print "max edge weight: ";
$w = ;



print $n;

my $count = 0;
while ($count < $m)
{
$count= $count + 1;
my $u = int(rand($n));
my $v = int(rand($n));
my $weight = int(rand($w));
print $u, " ", $v, " ", $weight,"\n";
}
print $n," ",$n," ",$w;

#end of gen
22
0 1 1
0 12 1
1 18 1
1 6 1
6 9 1
9 4 1
9 7 1
4 113 1
7 11 1
11 17 1
3 2 1
3 5 1
2 8 1
5 14 1
14 10 1
8 10 1
10 15 1
15 16 1
19 20 1
22 22 1