Graphs

Unstructured structures: sets
Hierarchy structures: Trees
Basic objects and relationship between them: Graphs

Basic objects: nodes, vertices   ...  websites
Relationship: edges, arcs, links  ...  hypelinks

Definition:
Basic objects: vertices.. V
Relationship: edges... E
Size: |V| + |E|
Directed or undirected
Weighted or unweighted
Path: a sequence of vertices and edges that depicts hopping along graph
In degree: number of edges coming to v
Out degree: number of outgoing edges from v

Adjacent matrix: (better for dense graph)
  Pro: quick add/delete edges etc.
  Con: Adding vertices (need to expand the matrix), and storing N^2 piece information.
Adjacency list: (better for sparse matrix)
  A map: vertices -> neighbors
  private Map<Integer, ArrayList<Integer>> adjListsMap
  Pro: easy (not quick) add/delete edges; easy (not quick) to add vertices; use less memory

Searching a graph:
1. DFS
  Need to keep track of visited node. - HashSet. Constant time add, remove, and find.
  Keep track of the next node to visit. - Use a stack. add and remove node.
  Keep track of the path from start to goal. - HashMap. Link each node to the node from which it was  discovered.
DFS algorithms (recursive)
DFS(S, G, visited, parents):
    if S==G return;
    for each of S's neighbors, n, not in visited set:
        add n to visited;
        add S as n's parent in the parent map;
        DFS(n, G, visited, parents);

DFS algorithms (stack)
DFS(S, G):
    Initialize: stack, visited HashSet and parent HashMap
    Push S to the stack and add to visited
    while stack is not empty:
        pop node curr from top of stack;
        if curr == G return parent map
        for each neighbor of curr, n, not in visited:
            add n to visited
            add curr as n's parent to parent map
            push n to the stack
    // if get here then there is no path

2. BFS
  Just change the to-visit stack to a queue.
BFS(S, G):
    Initialize: queue, visited HashSet and parent HashMap
    Enqueue S onto the queue and add to visited
    while queue is not empty:
        dequeue node curr from front of queue
        if curr == G return parent map
        for each of curr's neighbor, n, not in visited yet:
            add n to visited set
            add curr as n's parent in parent map
            enqueue n onto the queue
    // if get here there is no path
BFS find the shorter path than DFS.