CSC 372
Laboratory: First Graph Lab - Searching
File Needed: stack.h,
stack.cpp, 372lab6.cpp,
graph1.txt, graph2.txt,
graph3.txt
Background: The .txt files represent graphs. You
should assume that all graphs are connected. Each graph file contains
a first line that states the number of nodes in the graph and, then,
the number of edges in the graph. Below the first lines are lines
of THREE integers that represent edges. For example a graph file
containing
3 2
0 1 34
0 2 87
has three nodes labeled 0, 1, and 2 and two edges: one between
0 and 1 with weight 34 and one between 0 and 2 with weight 87. Thus,
each graph file tells the program how many nodes are in the graph
and how many (directed) edges there are along with all edges in
the form (Start node, Finish node, edge weight). Graph1.txt is the
graph in figure 8.7 on page 279. In the text nodes are labeled with
letters; in the files the labels are numbers A corresponds to 0,
B to 1, etc. Graph2.txt is the graph in figure 8.8 on page 281,
and graph3.txt is the graph in figure 8.15 on page 291. The last
graph is undirected so, the edges are all listed in both directions.
This difference is used so that all graph files can be used with
other laboratories.
In all cases the graph in the program is generated and implemented
as an adjacency matrix rather than a linked list. The program will
ask the user for the name of a graph file and proceed to build the
graph as an adjacency matrix.
Requirements: The program loads the graph into an adjacency
matrix. Complete the depth-first traversal of the graph writing
out the node values as you remove them from the stack. Start the
traversal at node 0.
Hand in your program and all associated files on a 3.5" diskette.
© Computer Science Department NSU.
Permission granted for non-commercial use only.
|