Graph Algorithms
This lab builds on your graph data structure from Lab3. You will implement
Breadth-First Search and Depth-First Search.
The input format
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 5This file is interpreted as follows:
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),
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