A graph is a collection of vertices and edges
Graphs can be undirected and directed Directed - edges do not go both ways Disjoint - disconnected / separate
Adjacency List
- vertices that are connected to a vertex V One per vertex Stores all neighbors
Adjacency Matrix
Can represent a graph with an Adjacency Matrix element at can be expressed as
Depth-first Search
Start from a node and recurse through Standard recursion graph search Done by marking nodes as visited, and then exploring current node’s neighbors if not visited
Previsit - main code of recursion step (after marking node, before recursing children) Postvisit - after the recursion step in the recursion method
To explore unconnected points (points unreachable from starting point), resume DFS from some other unvisited vertex until all visited ^^^^ explores all connected components
To run in directed graphs, can just only explore a neighbor if edge direction allows
Connectivity
Connected - path between any pair of vertices (undirected)
Connected component
internally connected subgraph but edges to any other vertices
Descendant
V is a descendant of U if there are solid edges in a path that lead to it in a auxilary graph
Disjoint Graphs
Types of Edges
Tree Edge
Solid edges in auxilary graph
Forward edge
From an ancestor to a non-child descendant Not a tree edge
Back Edge
From a descendant to an ancestor
Cross Edge
An edge that leads to a node that has already been explored
- considered completely explored if already postvisited
Circuit
A sequence of vertices
Cycle
A circuit where all vertices (except first and last) are distinct Sometimes a directed cycle is called a dicycle
Acyclic graph - a graph without a cycle
Can use DFS to discover if a directed graph has a cycle
- finding a back edge (edge going from descendant to ancestor)
Lemma
A directed graph is acylic DFS has no back edges
Directed, Acylic Graph - DAG
- important for modeling relations like casualties, hierarchies
Linearization or topological sort of a Directed Graph
Lemma: All DAG’s have a topological sort and can be found in linear time
Algorithm: run DFS and sort vertices by past level, highest o lowest Exercise: show this is a valid linear order