Graphs - Directed and Otherwise
Many computer science algorithms can be represented using graphs
There are several different kinds of graphs, each better suited to a specific class of problems
The algorithms can be designed to walk through a graph in different ways
This chapter focuses on graphs, from both a theoretical and practical point-of-view
Graphs - Formally Defined
Graph: An ordered pair of sets <V, E>
V is a set of vertices (or points, or nodes)
E is a set of edges (or lines or arcs) connecting points)
An edge is given by a pair {m, n}, where m and n are in the vertex set V
In undirected graphs, {m, n} = {n, m}
Examples of Undirected Graphs
Directed Graphs
Undirected graphs are okay, but what we really want to concentrate on are directed graphs
For a directed graph, usually called a digraph, we use ordered pairs <s, d> to describe edges
s and d are in V
s is the source vertex
d is the destination vertex
Examples of Directed Graphs
Properties of Directed Graphs
We use sGd to mean that there is an edge in G from s to d
“iff” means “if and only if”
Reflexivity/Irreflexivity
Reflexivity: G is reflexive iff xGx for all x in V
If we refer to <x, x> as a self-loop, then G is reflexive iff every vertex in G’s vertex set has a self-loop
Irreflexivity: G is irreflexive if no vertex has a self-loop
Note that is is possible to G to be neither reflexive, nor irreflexive
Page 380
Symmetry/Antisymmetry
Symmetry: G is symmetric iff for every case where xGy it is also true that yGx
Note that this does not mean that every pair of vertices must be connected by an edge, but rather if a pair is connected by <x, y>, then they must also be connected by <y, x>
Symmetry/Antisymmetry (cont.)
Antisymmetry: G is antisymmetric iff no two distinct vertices have edges in both directions
A single vertex and have a self-loop
Note that just because a graph is not symmetric does not mean it is antisymmetric
G may have some pairs of vertices that have two edges between them, and some that do not
Page 382
Transitivity
Transitivity: G is transitive iff for each triple of vertices such that xGy and yGz, it is also true that xGz
In other words, if we can get from x to z by way of y, we can get there directly if G is transitive.
Note that a graph with only one vertex is transitive
Page 383
Paths
Path: A path is a sequence of edges <v1, v2>, <v2, v3>, <v3, v4>, …, <vk-1, vk> such that the destination of one is the source of the next
A path is simple iff all vertices in the path, except possibly the first and last, are distinct
The length of a path is the number of edges (not vertices) in it
If there is a path from x to y, then y is reachable from x
Cycles
Cycle: A cycle is a path such that the destination of the last edge is the source of the first edge
It goes back where it started
A self-loop is a cycle of length 1
A digraph is acyclic if it has no cycles in it
A simple cycle is a simple path that is a cycle
Connectivity
Connected: A graph is connected iff it is all in one piece, i.e., there are no pieces that are disconnected
Strong Connectivity: A digraph is strongly connected iff from each vertex there is at least one path (not necessarily of length 1) to all other vertices
In/Out Degree
In Degree: The In Degree of a vertex is the number of arrows pointing to it
Out Degree: The Out Degree of a vertex is the number of arrows staring from it
Adjacency Matrix
We can represent the presence of edges in a graph using a K x K matrix G’ of boolean values (p. 385)
G’(x,y) is True iff xGy, and False otherwise
It is easy to determine whether an edge exists (i.e., y is adjacent to x) by simply looking it up in the matrix
What is the Big O of this operation?
How big is G’?
Adjacency List
Since for most graphs, the adjacency matrix for G’ will be sparse, we can use lists instead
Lookups are more expensive, since we have to traverse some lists
What is the runtime complexity of a lookup?
p. 386
Weighted Adjacency Matrix
The preceding representations provide some structure to digraphs, but tell us nothing about the content
We can substitute numeric values for the boolean values
These numbers could represent distances (e.g. travelling salesman problem)
p. 387
State Table
We can also represent the connectivity with information about the cases when we transition to another node
We represent this in a state table
p. 388
Graph Traversal
There are two main ways to visit nodes in a graph
Depth-First Search
Go to the end of a path, then backtrack
Breadth-First Search
Visit all siblings before digging deeper
We maintain a list of Visited nodes while we are traversing
Depth-First Search
The algorithm for a depth-first search is:
Start at a node x
Place x in the Visited list
Process x
Do whatever it is we want to do while visiting
For each vertex y adjacent to x, if y has not been visited, call DFS recursively
Depth-First Search Example
p. 389
Breadth-First Search
The algorithm for a breadth-first search is:
Make a queue Q empty
Start at a node x
Place x in the Visited list
Enqueue x onto Q
Process x
Breadth-First Search (cont.)
Dequeue a value y from Q
For each vertex z adjacent to y loop
if z is not visited
Place z on the Visited list
Process z
Enqueue z on Q
end if
end loop
Breadth-First Search Example
p. 391