Week 7 Graphs 2 Notes + Floyd Warshall #7
Description
Determining if a graph has a cycle
Can start at some node, BFS out, marking where we've been. If we reach a node where we've been before, then there must be a cycle. This works as is for undirected graphs, but not for directed graphs. For directed graphs, you'd need to start from each node, BFSing out, and checking if you've reached the node you started from. (don't just check if you've visited it before bc that'll give you false cycles)
Trees
Main property = acyclic
Anywhere can be the root node, it's flexible
Binary trees: each node has at most 2 children. Special property = linear memory since at most you need to store left and right children (2 * N matrix, where each of the Nth node's left and right children are stored)
Shortest Paths
Floyd-Warshall Algorithm (O(N^3))
Gets every possible shortest path on the graph using transient connectivity (basically it'll output adj matrix with shortest paths for every pair of nodes)
For each pair of nodes, it asks if it's easier to go straight from A to B, or to use a middle node and go A --> C --> B
Everything that isn't directly connected (before running the algorithm) should be INF apart, and every node has a distance of 0 to itself
Try to stay below 100-200 nodes, but you can still try for up to ~500 nodes
Make sure the order of all the variables are okay
Don't care about # of edges or directed / indirected as long as the adj matrix is built correctly
Pseudocode:
for (int i = 0; i < N; i++)
for (int j - 0; j < N; j++)
for (int k = 0; k < N; k++)
adj [i] [j] = min ( adj [i] [j], adj [i] [k] + adj [k] [j] )