#USING PYTHON WOULD BE BEST#

Graphs have been broadly employed in modeling various kinds of applications. In this project, you apply graph algorithms to solve applications specified below.

1. Write a program that displays connected components of a graph with DFS (or BFS.) Test your program with fig, a graph in its adjacency dictionary representation.

fig = {'A': set(['B', 'E', 'F']),

'B': set(['A', 'C', 'F']),

'C': set(['B', 'D', 'G']),

'D': set(['C', 'G']),

'E': set(['A', 'F', 'I']),

'F': set(['A', 'B', 'E', 'I']),

'G': set(['C', 'D', 'J']),

'H': set(['K', 'L']),

'I': set(['E', 'F', 'J', 'M']),

'J': set(['G', 'I']),

'K': set(['H', 'O', 'L']),

'L': set(['K', 'H', 'P']),

'M': set(['I', 'N']),

'N': set(['M']),

'O': set(['K']),

'P': set(['L'])

}

2. Write a program that locates a path for a given graph with DFS (and BFS) for the same starting and ending nodes. Test your program with the graph above and write your findings in your project report.

3. A connected digraph can be decomposed to its strongly connected components as a meta graph in the form of a DAG. Find the DAG of the graph provided below with an available piece of software.

4. Applying Dijkstras algorithm, one can find the shortest path tree for a connected weighted graph. Write a program that produces the shortest path tree for a user provided weighted graph and starting node. Test your program with the graph below.

Write a program that produces the minimum spanning tree for a user provided weighted graph. Test your program with the graph above.

1. Questions related to problem #1: Do DFS and BFS find the same connected components of for a given graph?

2. Questions related to problem #2: What is the necessary condition that DFS or BFS can find a path between any two vertices? If there is a path between two given vertices, do DFS and BFS always find the same path or not?

3. Questions related to problem #3: How many strongly connected components are there in the provided digraph? Illustrate their topological order with a linearized DAG.

4. Questions related to problem #4: The test weighted graph is undirected. Can you apply Dijkstras algorithm to find shortest paths for a weighted digraph? The test graph is positive weighted. Can you apply Dijkstras algorithm to find shortest paths for a weighted digraph with negative weights?

5. Question related to problem #5: Are a shortest path tree and a minimum spanning tree the same?

Graph for question 3

Graph for question 4

4 S 2 12 9 6 11 4: backspace o O U