12/28/2010
Graphs
For expressing non-hierarchically
related items
1
12/28/2010
Graphs
A graph consists of
A set of vertıces (nodes) (V = {v0, . . .})
A set of edges (arcs): pairs of vertices (E)
Vertices with an edge between are called adjacent.
Depending on problem, nodes or edges may have
labels (or weights)
If the edges have an order (first, second), they
are directed edges, then we have a directed
graph (digraph), otherwise an undirected graph.
We can label the edges of a graph with numeric
values, the graph is called a weighted graph.
Graphs
A path between two vertices is a sequence of
edges that begins at one vertex and ends at one.
A simple path passes through a vertex only
once.
A cycle is a path, without repeated edges, leading
from a node back to itself.
A graph is cyclic if it has a cycle, else acyclic.
Directed Acyclic Graph – DAG.
2
12/28/2010
Graph Examples
Graphs
An undirected graph is connected if there is a path between every
pair of nodes. That is, if one node of the pair is reachable from the
other.
If a directed graph has this property, it is called strongly connected
If a directed graph becomes connected when arc directions are
neglected, it is called weakly connected.
A complete graph is a graph in which there is an edge between
every pair of vertices
A DAG is a (rooted) tree iff connected, and every node but the root
has exactly one parent.
A connected, acyclic, undirected graph is also called a free tree.
Free: we’re free to pick the root; e.g.,
3
12/28/2010
Graph – An Example
1 2 A graph G (undirected)
3 4 5
The graph G= (V,E) has 5 vertices and 6 edges:
V = {1,2,3,4,5}
E = { (1,2),(1,3),(1,4),(2,5),(3,4),(4,5), (2,1),(3,1),(4,1),(5,2),(4,3),(5,4) }
• Adjacent:
1 and 2 are adjacent -- 1 is adjacent to 2 and 2 is adjacent to 1
• Path:
1,2,5 ( a simple path), 1,3,4,1,2,5 (a path but not a simple path)
• Cycle:
1,3,4,1 (a simple cycle), 1,3,4,1,4,1 (cycle, but not simple cycle)
Representation
Adjacency Matrix
○ A two dimensional array
Adjacency List
○ For each vertex we keep a list of adjacent vertices
4
12/28/2010
Adjacency Matrix
Space requirement O(|V|2)
Acceptable if the graph is dense.
Adjacency Matrix
10
5
12/28/2010
Adjacency Matrix
11
Adjacency List
An adjacency list for a graph with n vertices numbered
0,1,...,n-1 consists of n linked lists. The ith linked list has a
node for vertex j if and only if the graph contains an edge
from vertex i to vertex j.
Adjacency list is a better solution if the graph is sparse.
Space requirement is O(|E| + |V|), which is linear in the
size of the graph.
In an undirected graph each edge (v,w) appears in two
lists.
Space requirement is doubled.
12
6
12/28/2010
Adjacency List
13
Adjacency List
14
7
12/28/2010
Graph Traversals
A graph-traversal algorithm starts from a
vertex v, visits all of the vertices that can be
reachable from the vertex v.
Two basic graph-traversal algorithms:
Depth-First Traversal
Breadth-First Traversal
15
Depth-First Traversal
Start from a given vertex. Visiting a vertex v,
the depth-first traversal algorithm visits (if
possible) an unvisited adjacent vertex to
vertex v.
You should specify the order in which it
should visit the vertices adjacent to v.
We may visit the vertices adjacent to v in sorted order.
16
8
12/28/2010
Depth-First Traversal Example
17
Recursive Depth-First Traversal
void traverse(Graph G, Node v) {
if(!marked(v) {
mark(v);
visit(v);
for each edge(v, w)
traverse(G, w);
}
}
9
12/28/2010
Non-recursive Depth-first Traversal
void traverse (Graph G, Vertex v) {
Stack<Vertex> S;
S.push(v);
while(!S.isEmpty()) {
Vertex current = S.pop();
if(!marked(current)) {
mark(current);
visit(current);
for each edge(current,w)
if(!marked(w)) S.push(w);
}
}
Depth-first Traversal
Stack
10
12/28/2010
Breadth-First Traversal
After visiting a given vertex v, visit every
vertex adjacent to v
You should specify the order in which it
should visit the vertices adjacent to v.
We may visit the vertices adjacent to v in sorted order.
21
Breadth-First Traversal Example
22
11
12/28/2010
Iterative Breadth-First Traversal
bft(Graph G, Vertex v) {
// Traverses a graph beginning at vertex v
Q Queue<Vertex>;
Q.enqueue(v);
mark(v);
while(!Q.isEmpty()) {
current = Q.dequeue();
visit(current);
for each edge(current, u)
if(!marked(u)) {
mark(u);
q.enqueue(u);
}
}
} 23
Topological Sorting
12
12/28/2010
Topological Sorting
13
12/28/2010
Topological Sorting
Analysis:
Finding the node with no predecessor O(|V|) // scan the array of vertices
Repeat this for V nodes O(|V|2)
When you keep set of nodes with no
predecessor (with in-degree zero) in
a stack or queue and use adjacency list O(|E|+|V|)
Unweighted Shortest-Path problem
Find the shortest path (measured by
number of edges) from a designated vertex
S to every vertex.
1 2
3 4 5
6 7
28
14
12/28/2010
Unweighted Shortest-Path Algorithm
void Graph::unweighted_shortest_paths(vertex s) {
Queue<Vertex> q;
for each Vertex v
v.dist = INFINITY;
s.dist = 0;
q.enqueue(s);
while(!q.isEmpty()) {
Vertex v= q.dequeue();
for each w adjacent to v
if(w.dist == INFINITY) {
w.dist = v.dist + 1;
w.path = v;
q.enqueue(w);
}
}
}
29
Weighted Shortest-path Problem
(Dijkstra’s algorithm)
Find the shortest path (measured by total cost) from
a designated vertex S to every vertex. All edge costs
are nonnegative.
2
1 2
4
3 10
1
2
3 4 5
2
8 4
5 2
1
6 7
30
15
12/28/2010
Shortest Paths: Dijkstra’s Algorithm
Problem: Given a graph (directed or undirected) with non-negative edge weights, compute
shortest paths from given source node, s, to all nodes. (Single source shortest path problem)
• “Shortest” = sum of weights along path is smallest.
• For each node, keep estimated distance from s, and of preceding node in shortest path from s.
PriorityQueue<Vertex> pq;
For each node v { v.dist = ∞; v.path = null; }
s.dist = 0;
add all vertices to pq;
while(!pg.isEmpty()) {
Vertex v = pq.deleteMin();
for each edge(v,w)
if(v.dist + weight(v,w) < w.dist) {
update w.dist = v.dist + weight(v,w);
w.path = v;
}
}
32
16
12/28/2010
33
Shortest Paths: Dijkstra’s Algorithm
Analysis:
With priority queue: O(|E|log|V|+|V|log|V|) O(|E|log|V|)
Without priority queue: O(|E|+|V|2) O(|V|2)
17
