这个作业是用C语言完成图相关的数据结构和算法
CS 211: Computer Architecture, Fall 2020
Programming Assignment 2: Graph Algorithms in C
Introduction
In this assignment, you will improve your C programming skills by implementing graph algorithms.
First, you represent a graph data structure in C by representing undirected and weighted directed
graphs. Second, you implement two simple graph traversal algorithms – breadth-first search (BFS)
and depth-first search (DFS). Third, you will use the DFS traversal to single-source shortest path
computation in directed acyclic graphs (DAGs). Lastly, you will implement Dijkstra’s shortest
path algorithm that is not limited to DAGs and can be used to find single-source shortest paths
in all directed graphs that have no edges with negative weights. Your program must follow the
input-output guidelines listed in each section exactly, with no additional or missing output.
The second file includes queries on the constructed graph. Each line contains a separate query that
starts with the query type and a vertex, separated by a space. There are three query types. Outdegree queries start with the letter ’o’, followed by a space and the vertex’s name. Upon processing
an out-degree query, your program must print out the queried vertex’s out-degree1
, followed by a
newline character. In degree queries start with the letter ’i’, followed by a space and the vertex’s
name. Upon processing an in degree query, your program must print out the queried vertex’s in
degree2
, followed by a newline character. Adjacency queries start with the letter ’a’, followed by
a space and the vertex’s name. Upon processing an adjacency query, your program must print
out the vertices adjacent to the queried vertex, each vertex separated by a space and finally, a
newline character. When you print the results of the adjacency query, the results have to be sorted
lexicographically.
We will not give you improperly formatted files. You can assume all your input files will be in
proper format, as stated above.
Third: Breadth-first Search (BFS) (20 points)
In this part, you will implement the bread-first search (BFS) graph traversal algorithm. For a given
input graph G=(V,E) and a source vertex s, BFS starts exploring the edges of G until it discovers all
vertices reachable from the source vertex. During a BFS search, we start by visiting the adjacent
vertices to the source vertex, processing them, and subsequently exploring vertices in order of edge
distance (i.e., the smallest number of edges) from it. Figure 3 shows an example graph and its
BFS traversal starting from source vertex B. Note that the vertices are processed in order of their
distance from the source3
.
You will write a program that will read an undirected graph from a file using your implementation
from part 1 and perform BFS starting from different source vertices.
Input-Output format: Your program will take two file names as its command-line input. The
first file includes the undirected graph. This file is similar to the graph file from part 1. Your
3For more information on BFS and example pseudocode, see https://en.wikipedia.org/wiki/Breadth-first_
search
5
program reads the contents of this file and constructs the graph data structure. The first line in
this file provides the number of vertices in the graph. Next, each line contains the name of each
vertex in the graph. Afterwards, each following line includes information about an edge in the
graph. Each edge is described by the name of its pair of vertices, separated by a space.
The second file includes BFS queries on the constructed graph. Each line contains a different BFS
query specifying a source vertex for the BFS. Your program must read the source vertex, perform
a BFS traversal on the constructed graph using the chosen source vertex, and print out the graph
vertices in order of BFS processing. Each vertex is separated by a space and finally, a newline
character.
Example Execution:
Let’s assume we have the following graph and query file:
graph.txt
query.txt:
B
E
Then the result will be:
$./third graph.txt query.txt
B A D C E F
E C D F A B
We will not give you improperly formatted files. You can assume all your input files will be in
proper format, as stated above.
You have traverse the immediate children of a node in a lexicographic order. For
example, if A node has three edges to nodes B, C, and D, then the BFS will process B first, then
C, and finally D. This requirement ensures that every graph has a single unique BFS traversal for
Figure 4: This figure illustrates a directed graph and its DFS traversal steps starting from vertex
A.
a given source vertex. You can easily satisfy this requirement by maintaining the adjacency list in
a lexicographically sorted order.
Fourth: Depth-first Search (DFS) (20 points)
In this part, you will implement the depth-first search (DFS) graph traversal algorithm. For a given
input graph G=(V,E), DFS visits an unvisited vertex v. At each step in DFS, we choose an unvisited
vertex adjacent to the most recently discovered vertex. We continue this process until all vertices
reachable from v are discovered. If any undiscovered vertices remain, we choose one of them and
repeat the above process until all vertices are discovered. For example, Figure 4 illustrates a DFS
traversal of the example graph in Figure 2(a) 4
.
In this part, you write a program that will read a directed graph from a file using your implementation from part 2 and perform a DFS traversal, printing out the graph vertices in order of DFS
vertex visit. When you are choosing a vertex to visit next among the adjacent children, you have
to pick the vertex that is not visited yet and occurs first in the lexicographic order.
Input-Output format: Your program will take a file name as its command-line input. This file
includes a directed graph, and it follows the same format from part 2. Your program reads the
contents of this file and constructs the graph data structure. The first line in this file provides
the number of vertices in the graph. Each following line includes information about a weighted
directed edge in the graph. Each weighted edge is described by the name of its pair of vertices,
followed by the edge weight, separated by a space. Your program must read and construct this
graph, perform a DFS traversal, and print out the graph vertices in order of DFS visitation. Each
vertex is separated by a space and, finally, a newline character.
Then the result will be:
$./fourth graph.txt
A C E D B
We will not give you improperly formatted files. You can assume all your input files will be in
proper format, as stated above.
Hints and Suggestions
• In a DFS traversal, each vertex is processed at most once. A DFS traversal will visit all graph
vertices even when the graph is disconnected. Make sure your program works correctly in
such cases.
• You may have noticed that your program can safely ignore the graph edge weights in this
part. However, this part’s solution is going to be used in part 5, which requires reading graph
weights. Hence reusing part 2’s solution for weighted directed graphs is recommended in
programming this part of the assignment.
• When visiting graph vertices, visit them based on lexicographical ordering.
Fifth: Single-source Shortest Path in a Directed Acyclic Graph
(DAG) (40 points)
Given a weighted directed graph G=(V,E) and the source vertex s, the single-source shortest path
problem’s goal is to identify the shortest path from the source vertex to all vertices in the graph.
For example, finding the shortest path from our home to different adjacent cities can be modeled
as a single-source shortest path problem with our home being the source vertex.
Depending on the input graphs type, a single-source shortest path problem can be solved using
different algorithms that vary in asymptotic running time and complexity. For example, the BFS
algorithm from part 3 is sufficient to solve the single-source shortest path problem for unweighted
(g)
Order
Figure 5: This figure illustrates a directed graph and the steps involved in identifying its topological
sort
graphs. However, we need other algorithms to solve the single-source shortest path problem in
weighted graphs5
.
In this part, your task is to write a program to solve the single-source shortest path problem for a
type of directed called directed acyclic graphs (DAG). A DAG is a directed graph with no cycles6
.
The single-source shortest problem in DAGs can be solved by visiting the DAG’s vertices in a
topologically sorted order and updating the shortest path of the visited vertex’s adjacent vertices.
You must use the DFS traversal from part 4 to topologically sort the DAG.
Algorithm 1 shows the steps to compute the single source path for the graph G and source vertex
src. The algorithm maintains a distance array that is initially set to infinity for all vertices except
the source vertex. distance[u] contains the shortest path from the source vertex to vertexu at
the end of the algorithm or infinity if no path between src and u exists.
A topological sorting of the a DAG G(V,E) is an ordering of its vertices, T such that for every directed (u,v), vertex u appears before vertex v in its topological ordering. For example, Figure 5(a)
shows an example DAG and its topological sort. Figure 5(b-f) illustrates the steps taken by the
DFS inspired algorithm7
1 procedure DAG-SSP(G, src)
2 T ← T opologicalSort(G)
3 foreach vertex v in Graph G do
4 distance[v] ← inf
5 end
6 distance[src] ← 0
7 foreach vertex u in topologically sorted order T do
8 foreach vertex v ∈ u.Adjacent do
9 if distance[v] > distance[u] + weight(u, v) then
10 distance[v] ← distance[u] + weight(u, v)
11 end
12 end
Figure 5(g) shows updates to the distance array by using algorithm Algorithm 1 on the DAG from
Figure 5(a).
Input-Output format: Your program will take two file names as its command-line input. This
first file includes a DAG, and it follows the same format from parts 2 and 4. Your program reads the
contents of this file and constructs the graph data structure. The first line in this file provides the
number of vertices in the DAG. Each following line includes information about a weighted directed
edge in the DAG. Each weighted edge is described by the name of its pair of vertices, followed by
the edge weight, separated by a space. Your program must read and construct this DAG,
The second file includes single source shortest path queries on the constructed DAG. Each line
contains a different single-source shortest path query by specifying a source vertex. Your program
must read the source vertex, perform the single source shortest path algorithm using the provided
source vertex, and print out each of vertex in the DAG in lexicographic ordering, followed by the
length of the shortest path to that vertex, and a newline character. Note that an additional newline
character follows the last vertex in DAG. Further, your program must detect if the input graph is
not a DAG. In such cases, your program simply prints out CYCLE, followed by a newline character.
Example Execution:
Let’s assume we have the following graph input file:
graph.txt
7
A
B
C
D
E
F
G
A D 10
A C 5
10
B D 7
C D 3
D E 5
E F 1
C F 10
E G 10
F G 5
query.txt
A
G
Then the result will be:
$./fifth graph.txt query.txt
A 0
B INF
C 5
D 8
E 13
F 14
G 19
A INF
B INF
C INF
D INF
E INF
F INF
G 0
For the scenario when the input graph is not a DAG:
not_dag.txt
2
CA
NJ
NJ CA 3000
CA NJ 3100
query.txt
CA
Then the result will be:
$./fifth not_dag.txt query.txt
CYCLE
11
We will not give you improperly formatted files. You can assume all your input files will be in
proper format, as stated above.
Hints and Suggestions
• The shortest path from the source vertex to itself is 0.
• The shortest path from the source vertex to any unreachable vertex is infinity. In the output,
we represent infinity with INF, as shown in the example execution.
• You can use INT MAX from <limits.h> to represent infinity in your program. The input DAGs
will not contain edges with weights larger than INT MAX. Further, you may safely assume that
the shortest paths do not overflow.
• Edge weights can be negative numbers.
Input-Output format: Your program will take two file names as its command-line input. This
first file includes a weighted directed graph, and it follows the same format from parts 2 and 4.
Your program reads the contents of this file and constructs the graph data structure. The first line
in this file provides the number of vertices in the graph. Each following line includes information
about a weighted directed edge in the graph. Each weighted edge is described by the name of its
pair of vertices, followed by the edge weight, separated by a space. Your program must read and
construct this graph,
The second file includes single source shortest path queries on the constructed each. Each line
contains a different single-source shortest path query by specifying a source vertex. Your program
must read the source vertex, perform Dijkstra’s single-source shortest path algorithm using the
provided source vertex, and print out each of vertex in the graph in lexicographical ordering,
followed by the length of the shortest path to that vertex, and a newline character. Note that an
additional newline character follows the last vertex in DAG.
Example Execution:
Let’s assume we have the following graph input file:
graph.txt
5
A
B
C
12
D
E
B A 10
A C 8
A D 12
B D 5
C E 5
D C 9
E C 7
E D 3
query.txt:
A
E
Then the result will be:
$./sixth graph.txt query.txt
A 0
B INF
C 8
D 12
E 13
A INF
B INF
C 7
D 3
E 0