Collection of nodes/vertices and connecting edges
Can be (un)directed, (uni|bi)directional, weighted, (un)connected, (a)cyclic.
Usually represented as a matrix, can also be constructed as an ADT.
Path-finding (Traversal) Techniques:
current vertex = start vertex
While current vertex exists
Add it to "visited" list
Add to "revisit" stack
If current vertex has edges to vertices not in "visited" list
current vertex = unvisited vertex
Else
current vertex = pop from revisit stack
DFS = visited list
current vertex = start vertex
While current vertex exists
Add it to "visited" list
Add to "revisit" queue
If current vertex has edges to vertices not in "visited" list
current vertex = unvisited vertex
Else
current vertex = dequeue from revisit queue
BFS = visited list
Yes, apparently the only difference is that DFS uses a stack while BFS uses a queue!
Compute shortest distance between any two vertices. Requires graph be weighted.
A "distances" dict/map that contains distances from start vertex to rest of the vertices.
Do a BFS from start vertex
Sum weight to current vertex from start
If it is less than that in "distances", update "distances" with new path/weight