这个作业是用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