The first part of the lab we will write methods to do the following tasks:
Read in a graph
Your program should read in a text file that has a adjacency matrix. Some algorithms will expect a weighted graph, but one will expect a directional graph(1s and 0s). You can assume the matrix will always be symmetrical, the rows and columns represent the nodes so it has to be symmectrical.
You will need to read in a weighted graph for some of the weighted graph algorithms in the outlab, and a (directional) boolean graph for reachability algorithms. Example:
01101
10011
10001
01000
11100
That is directional, here is weighted…….
0 9 3 0 6
9 0 0 4 5
3 0 0 0 8
0 4 0 0 0
6 5 8 0 0
Weighted graphs are always mirror images because to get from first node to second node it is always 9 no matter which way you travel.
Write a method that does breadth-first search (Queue).
Write a method that does depth-first search (recursion ….I said stack in class, and that’s all recursion really is, but it’s easier than implementing a stack).
Continue with your program from above and add the following:
Dijkstra’s Algorithm
Prim’s Algorithm
Floyd’s (find all reachable paths with a directed graph start with adjacency matrix)
Floyd and Warsall’s (Find shortest path).