Programming Assignment 1

General instructions:

• Please name your submission as rollno.c, send the file to the TAs email addresses.
• You are not supposed to use any built-in library function for any advanced operation, for example, checking bipartiteness of a graph and so on. Consult with the TAs if you have doubts regarding what kind of library functions you can use.
• For evaluation: You will be asked to fix an appointment with the TAs for demonstration of code. They can also ask you to make minor modifications of your code and show the results.

• Part 1: In the first part of this assignment you will be given as input a graph in the adjacency list format and you are required to implement a breadth first traversal (BFS) of the graph. Please follow the input/output specifications given below.

Input: Let's assume the input will be read from a text file. The first line should contain the number of vertices (n) and the starting vertex for breadth first traversal. Thereafter, there would be n lines for specifying the neighbours of vertices 1 to n (in that order).

Sample Input/Output Example: (Path on 4 vertices)

4 2

2

1 3

2 4

3

Output:

Stating vertex followed by the trace of BFS

Example:

2 1 3 4

• Part 2: Write a subroutine to check if there is a cycle in the graph. Output any cycle if there are multiple cycles in the graph.

Input: The first contains the number of vertices. From 2nd line onwards, the i^th line has vertices adjacent to vertex (i-1).

Example: (Path on 4 vertices)

4 2

2

1 3

2 4

3

Output:

1) No (if the input graph has no cycles)

2) Yes (if input graph has a cycle along with one cycle). Print vertices on the cycle.

• Part 3: Figure out if the graph is bipartite. If it is, output the bi-partitions, else output a witness that the graph is not bipartite.

Input: The first line has the number of vertices (n). From 2nd line onwards, the i^th line has vertices adjacent to vertex (i-1)

Example: (Path on 4 vertices)

4 2

2

1 3

2 4

3

Output:

1) Yes (if the instance is a bipartite graph). Print the vertices belonging to the bi-partitions in parenthesis.

Example:

Yes (1 3) (2 4)

2) No (if the graph is not bipartite). Print any witness to show that the graph is not bipartite.