CSCI 2110辅导、讲解python, C/C++编程语言、讲解Data Structures

CSCI 2110 Data Structures and Algorithms

ASSIGNMENT NO. 5

Date Given: Wednesday,November 28, 2018

Due: Monday, December 10, 2018,11.55 p.m.

You are to write a program to read a text file containing information  about an undirected,

unweighted graph, create an adjacency matrix representation, and  traverse the graph using

either breadth-first ordepth-first search methods.

Follow these steps:

1. Reada text file (specified by the user – don’t hard code!)that contains the number of vertices

on the first line followed by the edges. You may assume that the  vertices are represented by

StringsA, B, C, etc. For instance, forthe following graph

the input text file will be (order of the edgesdoesn’tmatter):

5

E A

E B

A B

A D

B D

D C

You may also assume that the input fileis error-free (that is,it  will have the right number of

entriesand theappropriate values).

2. Nextcreate an adjacency matrix that represents the graph. For example, for the above data,

you would create a 2 d array of5 rows and 5 columns and the adjacencymatrixwould be:

A B C D E

A 0 1 0 1 1

B 1 0 0 1 1

C 0 0 0 1 0

D 1 1 1 0 0

E 1 1 0 0 0

In general, youwould create anadjacency matrix of thetype:

int[][]adjMatrix = newint[num][num];

where num is the value that is read on the first line.

Note: It is easy to convert a String toan integer or acharacter toan integer. Forinstance,

int num= Integer.parseInt(inputFile.nextLine());

will read the first line in theinput text file as an integer.

Then supposeyou read the second line as two strings firstVertexandsecondVertex:

String firstVertex = inputFile.next();

String secondVertex = inputFile.nextLine();

In the example,firstVertex will be E and secondVertex will be A.With the following statements:

int x =firstVertex.charAt(0)-65;

int y =secondVertex.charAt(0)-65;

x will have thevalue 4and y will havethe value 0. These are the correct array indices for Eand

A.

Now allyou need to do is to update adjMatrix[x][y] = 1and adjMatrix[y][x] = 1.

Display the adjacency matrix.

3. Next traverse the graph either usingdepth first search OR breadth first search method and

print the vertices. Print the traversal. You can assume any node as thestarting vertex.

The algorithms for depth first search and breadth firstsearch are given below:

Depth First Search (DFS): (recursive algorithm – see lecture notes)

Start at a vertex v1. Put it inthe result list.

Pick a neighborof v1, say v2. Go to v2.

Pick a neighborof v2, say v3. Go to v3.

Continue and mark each vertex that has been visited. List the markedvertex in the result list.

If you hit a deadend, backtrackto the previous neighbor and pick aneighbor that has not been

visited.

BreadthFirst Search (BFS):

Overview: Startat a vertex v1.

Visit all the neighborsof v1.

Then visit all the neighbors ofthe neighbors of v1.

Continue until all the verticesare visited.

Algorithm:

Initialize an empty queue and aresult list.

Enqueuethe first vertex.

while the queue is not empty

Dequeueand list the vertex v in the result list

Enqueueeach neighbor of v (if it is not already in the result list or not already in the

queue)

end while

What tosubmit:Source code andsample inputs and outputs in a text file.