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).

Last Updated on February 11, 2019 by Essay Pro