General

• Graph G = (V, E)


  Consists of a set of vertices, V, and a set of edges, E. Each edge is a pair (v, w), where v, w ∊ V. Edges are sometimes referred to as arcs. If the pair is ordered, then the graph is directed.
• Directed graphs


  Also referred to as digraphs
• Vertex w is adjacent to v


  If and only if (v, w) ∊ E
• Undirected graph


  If edge (v, w), then (w, v) also exists. w is adjacent to v and v is adjacent to w.
• Edge weight/cost


  A third component of an edge
• Path in a graph


  1. Sequence of vertices w1, w2, w3, …, wN such that (wi, wi+1) ∊ E for 1 ≤ i < N

  2. Length of path is number of edges, N - 1

  3. Allows path from vertex to itself with length 0
• Loop


  Path v, v with edge (v, v)
• Simple path


  All vertices are distinct, except first and last could be the same
• Cycle in a directed graph


  Path of length at least 1 such that w1 = wN
• Simple cycle


  Cycle where the path is simple
• Acyclic directed graph (DAG)


  Directed graph with no cycles
• Connected undirected graph


  There is a path from every vertex to every other vertex
• Strongly connected directed graph


  There is a path from every vertex to every other vertex
• Weakly connected directed graph


  Underlying undirected graph is connected, but graph is not strongly connected
• Complete graph


  There is an edge between every pair of vertices
• Real-life graph models


  • Airport system
  • Traffic flow
• Adjacency matrix representation


  2D array where A[u][v] is true if edge (u, v) exists, otherwise false. Can store weights instead of booleans.
• Adjacency list representation


  For each vertex, keep a list of adjacent vertices. Space requirement is O(|E| + |V|).
• Adjacency lists are the standard way to represent graphs
• For very sparse graphs, start adjacency lists with smaller capacity to avoid wasted space
• Adjacency list implementation options


  • Use a map where keys are vertices and values are adjacency lists
  • Maintain adjacency lists as data members of a Vertex class