Graph Basics 
Document last modified: 
G = (V, E)
V  finite set called the vertex set whose elements are called vertices
E  is a binary relation on V called the edge set, whose elements are called edges
Examples
Undirected V = {1, 2, 3, 4, 5}

Directed V = {1, 2, 3, 4}

Directed Graph
The ordered pairs in E represent the direction of the edge, i.e., (tail, head) tail is source vertex and head is the target vertex
Undirected Graph
The pairs in E are unordered pairs, i.e., there is no tail or head and there is no direction to the edge, e.g., (u, v) ∈ E is really the same edge as (v, u)
Adjacent Vertices  means there is an edge from u to v, i.e., (u, v), page 1169.
undirected graph  (u, v) means v is adjacent to u, and vice versa.
Example: (2, 3) and (3, 2) are adjacent.
directed graph  (u, v) means v is adjacent to u, but unless there is an edge (v, u), then u is not adjacent to v.
Note that this is the opposite of definitions used by most other authors but the distinction can generally be ignored in the algorithms presented in the text.
Example: (3, 2) means 2 is adjacent to 3 but 3 is not
adjacent to 2.
adjacent vertices are said to be neighbors.
Degree  the number of edges incident on a vertex
undirected graph  the degree equals the number of edges incident on a vertex.
Example: vertex 2 has degree 4.
directed graph:
indegree  equals the number of edges who have their head at a vertex, or targeting the vertex
Example: vertex 2 has indegree 2.
outdegree  equals the number of edges emanating from the vertex.
Example: vertex 2 has outdegree 1.
Path
Of length k from u to u' in G = (V, E) is a sequence of
vertices < v_{0}, v_{1}, ..., v_{k} > where u
= v_{0} and u' = v_{k}, and (v_{i 1}, v_{i})
∈ E, for i = 1, 2, ..., k
P = Path Length  equals the number of edges in the
path
There is always a 0length path from u to u
Reachable  given u and u', u' is reachable from u if
there exists a path P from u to u'
written as u
u' for a
directed graph
1 4 for directed graph at right
Question 22.1 for the directed graph at right
Is 1 adjacent to 2?
Is 2
1?
Is x
y
for all x, y ∈ V
Is the Web a directed or undirected graph?
What does indegree and outdegree correspond to on the Web?
Is x
y
for all x, y ∈ V where V is all Web pages?
What does Google Google?
Cycles
In Directed Graphs:
a cycle path (circuit) is a path < v_{0}, v_{1},
..., v_{k} > such that v_{0} = v_{k} and P
≥
1
a simple cycle is when v_{0}, v_{1},
..., v_{k} in P are distinct, does not contain the same edge
more than once.
a self loop is a cycle of length 1, and a
directed graph with no self loops is referred to as simple
Directed Acyclic Graphs (DAG)  a directed graph
with no cycles (circuits)
In Undirected Graphs:
a simple cycle is when v_{0}, v_{1}, ..., v_{k} in P are distinct and P ≥ 3
(1,2,1) is not a simple cycle.
Undirected Acyclic Graph  an undirected graph
with no simple cycles (circuits)
Same Cycle  two cycles < v_{0}, v_{1}, ..., v_{k} > and < v'_{0}, v'_{1}, ..., v'_{k} > are the same cycle when there exists an integer j, such that v'_{i} = v'_{(i = j) mod k} for i = 0, .., k  1
Question 22.2 for the directed graph at right
Give one cycle.
Is the graph a DAG?
Give an example of a DAG.
Connected
undirected graph
connected  when every pair of vertices in V is
connected by a path. The graph below has 3 components, it is not a
connected graph.
connected components  if the graph is not connected,
then it has connected components where each of these connected
components are made up of a subset of vertices from V, and each
component is connected
directed graph
strongly connected  when every two of vertices in V is
reachable from each other
strongly connected components  if the directed graph is
not strongly connected, then it has strongly connected components where
each of these strongly connected components are made up of a subset of
vertices from V, and each component is strongly connected
weakly connected  when the underlying undirected graph is connected; a strongly connected directed graph is also weakly connected.
Question 22.3
Is the graph at right strongly connected?
Is a binary search tree strongly connected?
Is a binary search tree weakly connected?
What operations might we want to do on a graph? Here are some common ones:
create (G)  create a graph G.
add_edge (G, a, b)  add the edge (a, b) to G.
outdegree (G, a)  return the outdegree of vertex a.
indegree (G, a)  return the indegree of vertex a.
adjacent_to (G, a, b)  return true if a is adjacent to b.
forall_adjacent_to (G, a, f)  apply the function f to all vertices adjacent to a. Usually implemented as an iterative loop doing something for each vertex adjacent to a.
forall_path_to (G, a, f)  apply the function f to all vertices reachable from a by some path. Traditionally called "searching" the graph starting from some vertex.
Representation
Given graph G = (V, E).
• May be either directed or undirected.
• Two common ways to represent for algorithms:
Adjacency lists.
Adjacency matrix.
When expressing the running time of an algorithm, it's often in terms of both V and E.
In asymptotic notation — and only in asymptotic notation — drop the cardinality.
Example: O(V + E) rather than O(V + E).
Adjacency lists
Array Adj of V lists, one array entry per vertex.
Vertex u's list has all vertices v such that (u, v) ∈ E (for both directed and undirected graphs)
C++ representation
typedef struct node {
int to, from;
struct node *next;
} edgenode, *graph;
Example: For an undirected graph:
If edges have weights, can put the weights in the lists.Weight: w : E → R
Use weights for spanning trees and shortest paths.
Performance:
Space: Θ(V + E).
Time: to access all vertices adjacent to u: Θ(degree(u)).
Time: to determine if (u, v) ∈ E: O(degree(u)).
Example: For a directed graph:
Adjacency matrix
V × V matrix A = (a_{i j} ) where i is row, j is column
a_{i j} = 1 if( i, j ) ∈ E
= 0 otherwise
Performance:
Space: Θ(V^{2}), independent of E
Time: to access all vertices adjacent to u: Θ(V).
Time: to determine if (u, v) ∈ E: Θ(1).
Can store weights instead of bits for weighted graph.
Example  4 × 4 matrix
Directed graph
V={1,2,3,4}
V is 4
E={(1,2) (2,4) (3,1) (3,2) (4,3) (4,4)}
E is 6
(1, 2) ∈ E
(3, 1) ∈ E
Outdegree of vertex 3 = 2 or (3,1) and (3,2)
Indegree of vertex 2 = 2 or (3,2) and (1,2)
Question 22.4  5 ×5 matrix
Directed or undirected graph? How do you know?
V?
V?
E?
E?
(1, 2) ∈ E?
(2, 1) ∈ E?
Outdegree of vertex 4?
Indegree of vertex 2?
Which edges are missing on vertex 5 for the graph and matrix to agree?
OPERATIONS
Many of the graph operations take time linear in the size of E, i.e., O(E).
We know from trees and hash tables that we can probably do better.
Question 22.5
Suggest an algorithm to search a directed graph for a strongly connected graph (every vertex is reachable).
What problem must be handled on the directed graph at right?
How might the problem be resolved?
What would you guess the worst case performance for an algorithm searching for a vertex in the directed graph? Consider searching for 5 in the lowerright graph.
What would you guess the worst case performance of the algorithm for determining a strongly connected graph? Consider the upperright graph.
Representation in C called an edge list, a linked list of edges. A node is:
Create the graph is just setting a pointer equal to NULL.
typedef struct node {
int to, from;
struct node *next;
} edgenode, *graph;
add_edge is just inserting a node into the linked list:
adjacent_tovoid add_edge (graph *G, int a, int b) { edgenode *p; p = malloc (sizeof (edgenode)); p>to = b; p>from = a; p>next = *G; *G = p; }outdegreeint adjacent_to (graph G, int a, int b) { edgenode *p; for (p=G; p; p=p>next) if (p>from == a && p>to == b) return true; return false; }int outdegree (graph G, int a) { edgenode *p; int count; count = 0; for (p=G; p; p=p>next) if (p>from == a) count++; return count; }forall_adjacent_to We could do something like this:
forall_path_to For instance, maybe we want to print out every vertex reachable from a given vertex. This is a nontrivial task. A first try would be something like this:void something (graph G, int a) { edgenode *p; for (p=G; p; p=p>next) { if (p>from == a) { /* do something */ } } }But this will get us into trouble if there are cycles in the graph; it will just keep going around and around forever./* this is wrong! */ void search (graph G, int a) { for (p=G; p; p=p>next) { if (p>from == a) { printf ("%i\n", p>to); search (G, p>to); } } }Need to think of something better.
Later on, will see Depth First Search and Breadth First Search: two ways of dealing with this.