ICS 46 - Graphs

ICS 46 - Graphs

Adjacency List

• Faster to iterate through

• Better for sparse data

Adjacency Matrix

• O(n²) memeory used, not ideal for sparse data sets

Depth First Traversal

DFS is also a traversal approach in which the traverse begins at the root node and proceeds through the nodes as far as possible until we reach the node with no unvisited nearby nodes.

Breadth First Search

BFS is a traversal approach in which we first walk through all nodes on the same level before moving on to the next level.

Iterative Deepening DFS

Toplogical Sort

Kruskals

Prims

Dijkstras

Bellman-Ford

A*