Graphs

Identification

Graph Basics

• Graphs consist of nodes and edges where a path leads from node a to node b and its length is n edges
• A path is a cycle, if the first and last nodes are the same
• A graph is connected if there is a path between any two nodes
• Edges can be directed, undirected, or weighted
• Two nodes are neighbours if there is an edge between them
• Graphs can be Trees
• Graphs can be DAGs

Solving Steps

1. Choose graph representation
   1. Adjacency List
   2. Adjacency Matrix
2. Choose traversal technique
   1. Breadth First Search
   2. Depth First Search
   3. Dijkstras Algorithm
   4. Bellman-Ford Algorithm
   5. A* Algorithm
3. Implement a flavour on top of our technique
   1. Backtracking (if DFS)?
   2. Topological Sort

Paths

A path in a graph is a sequence of vertices between any two vertices. The order only matters in a directed graph.

A connected component of an undirected graph G is a subgraph of G such that:

1. The subgraph is connected
2. No vertex in the subgraph is connected to any vertex outside

We can use Preorder and Postorder to do things like Topological Sort, and classify edges.

Connectivity in Directed Graphs

Strongly connected:

• A graph is strongly connected if for every pair of vertices u and v there is a directed path from u to v and from v to u.
  Weakly connected:
• A graph is weakly connected if it is connected when the direction on each edge is ignored

DFS is good and easy to implement but rarely finds shortest paths. Breadth First Search does a better job.

Shortest Path

Given a weighted graph, once way to find the shortest path from $s$ to every reachable vertex is to convert each edge of weight $l_e$ into $l_e$ edges of length 1 and then run BFS. However, we need to add many edges and vertices to the graph, and we waste time traversing these fake new edges.

The typical way to do this is to use Dijkstras Algorithm.