Skip to Content

COMP225 : Algorithms and Data Structures

Practical Week 10
Objectives: To understand more about graphs.

  1. Debug this program

    Ensure you know how to terminate your program on end-of-file. Debug the following program. eofa.cpp For revision see programs at COMP125 eof programs

  2. (*)

    Submit Program

    Complete the following program which performs a Depth First Search of a graph represented by an adjacency matrix, displaying each vertex as it is visited. Each vertex (0,1,...) should be displayed on a separate line. The DFS should start from vertex 0.

    dfs.cpp You may assume all input is correct. You may assume a maximum of 100 vertices.

  3. Write a function which when passed the adjacency matrix of a graph will return the sum of the degrees of the vertices. You can add this function to a separate copy of above program. (i.e. don't wreck the submitted part).

  4. Help with Assignment 3

    The next step in developing assignment 3 is to build a representation of a graph - probably an adjacency matrix. You have read in a pair of cities c1 and c2 and cost (cost of flying from c1 to c2), have assigned c1 and c2 integer identifiers say int1 and int2.

    Declare a matrix of size 100 (maximum number of different cities flown between).Insert the cost of flying between c1 and c2 into the matrix.

    Issues to consider : what should the matrix be initialised to? What should the diagonal be set to?

Remember all Carrano's source code is available on web-site here You may use Carrano's graph class and implementation if you wish.