CS 302 Assignment 4: Breadth First Search
Using a Circular Linked List Implementation of Queue.

Due date: Monday, February 26, 2018, midnight.

  • All programming assignments must be submitted electronically. Submit them to the graduate assistant, Kaushik Deshmukh by email
    on or before the due date. Your email must come from your university or engineering college account, and your programs must compile and run on College computers.
  • The assignment is to write a program which uses a queue to traverse a directed graph in breadth first order.
  • The principle purpose of this assignment is to give you experience writing code with dynamic data structures, and in particular, the linear linked list implementation of set and the circular linked list implementation of queue.
    1. Each directed graph is given as a list of directed edges. The first line of the input file is n = the number of nodes in the graph, which will not exceed 100.
    2. Each node is an integer in the range 0 .. n-1.
    3. Each remaining line of the file is a directed edge, and contains the names of two nodes. If the line is i j, then there is a directed edge from i to j.
    4. Your program should do the following:
      1. Read the file and create the array of out-neighbor lists. Each of the out-neighbor lists should be implemented as an unordered linked list.
      2. Write the array of out-neighbor lists.
      3. Initialize a queue, implemented as a circular linked list with a dummy node.
      4. Insert (enqueue) 0 into the queue.
      5. Use that queue to visit all nodes reachable from 0 in breadth first order, and print those nodes in the order visited. Recall that breadth first order is not uniquely defined, so there are multiple correct answers.
    5. A small directed graph with 10 nodes.
    6. My output file for the small graph.
    7. A large directed graph with 100 nodes.
    8. My output file for the large graph.
      I have changed the output style somewhat.
  • I'll try to post the redacted version of the code very soon.