Transcript slides

Graphs and Shortest Paths
Using ADTs and generic
programming
Graphs
v2
v1
 A graph consists of a set of
vertices V and a set of
edges E  VV
v3
 Undirected graph:
v4
v5
v7
v8
v6
 E consists of unordered
pairs: Edge (u, v) is the
same as (v, u)
 Undirected graphs are
drawn with nodes for
vertices and line segments
for edges
Digraphs
 A directed graph, or
digraph:
v2
v1
v4
v3
v5
v7
v8
v6
 E is set of ordered pairs,
and not necessarily a
symmetric set. Even if
edge (u, v) is present, the
edge (v, u) may be absent
 Directed graphs are drawn
with nodes for vertices and
arrows for edges
Paths and Weights
v2
v1
3
5
v4
v7
v3
1
-2
2
v5
-1
v8
v6
4
 A path is a sequence of vertices
w1,w2,…,wn, where there is an
edge for each pair of consecutive
vertices
 The length of a path of n vertices
is n-1 (the number of edges)
 A path is simple if all its vertices
are distinct (except that the first
and last may be equal)
 Edges may have weights
associated with them
 The cost of a path is the sum of
the weights of the edges along
the path
Cycles
v2
v1
v4
v3
v5
v2
v1
v4
v6
v3
v5
v6
v7
v7
v8
v8
 A cycle is a path w1,w2,…,wn=w1, where the first and the
last vertices are the same
 A cycle is simple if the path is simple.
 Above, v2, v8, v6, v3, v5, v2 is a (simple) cycle in the
undirected graph, but not (even a path) in the digraph
Further terminology
v2
v1
 An undirected graph G is
connected if, for each pair of
vertices u, v, there is a path
that starts at u and ends at v
 A digraph H that satisfies the
above condition is strongly
connected
 Otherwise, if H is not strongly
connected, but the undirected
graph G with the same set of
vertices and edges is
connected, H is said to be
weakly connected
v3
v4
v5
v6
v7
v8
v2
v1
v4
v3
v5
v7
v8
v6
Data structures representing graphs
 A digraph can be stored
as a 2-dimensional array
A, with indexes ranging
from 0 to
n-1, where n=|V|
 Unweigthed graphs:
A[u][v]==true if edge
(u,v) is in the graph,
otherwise
A[u][v]== false
 Graphs with weights:
A[u][v]== w, the
weight of the edge (u,v)
 Undirected graphs can be
represented more efficiently,
having the second range be
0 to i, where i is the index
in the first range.
 This representation, the
Adjacency Matrix, requires
O(n2) space, where n is the
number of vertices
 It is wasteful for sparse
graphs, where most of the
possible edges are not
present.
Adjacency matrix example
v2
v1
v4
v3
v5
v7
v0
v6
A
0
1
2
3
4
5
6
7
0
F
F
T
F
F
F
F
T
1
F
F
F
F
F
F
F
F
2
F
F
F
F
F
T
F
F
3
F
F
F
F
F
F
F
F
4
F
T
F
F
F
F
F
F
5
F
F
F
T
F
F
F
F
6
T
F
F
T
F
F
F
F
7
F
F
F
F
F
F
F
F
Graph density and efficient storage
 A complete graph contains an
edge for every pair of vertices
 On the other extreme, sparse
graphs contain much fewer
than the O(n2) possible edges
 Example: Every intersection
in Manhattan is a vertex, an
edge is the portion of a
street between intersections
 In this graph, each vertex
has an average of 4 edges,
so |E| = O(n)
 The adjacency list is a spaceefficient approach to storing
sparse graphs
 For each vertex, maintain a list
of outgoing edges (pointers to
other vertices)
 Takes O(|V|+|E|) space
 Approach 1: A Hashtable
maps vertices to adjacency
lists
 Approach 2: Vertex structure
maintains a list of pointers to
other vertices
Adjancency list example
v2
v1
v4
v3
v5
v7
v0
v6
0
1
2
3
4
5
6
7
6,7
2
0
5
1
2
3
4
Graph-based algorithms
Introduction to some graph-based
problems and approaches
Topological sorting
Let G be a directed acyclic graph (DAG)
Topological sorting refers to ordering the
vertices of G such that if there is an edge
from vi to vj, then vj appears after vi
Topological sorting
 E.g.: Binary tree, where
the binary nodes store no
pointers to parent
root
1
2
4
5
 Children pointers are
viewed as representing
directed edges from
parent to child
3
6
7
 The binary node is a
vertex structure
 Level-order and pre-order
would be topological
sortings in this graph.
Topological sorting (example)
 A topological sorting
of the above could be:
MAC3311, COP3210,
MAD2104, CAP3700,
COP3400, COP3337,
COP4555, MAD3305,
MAD3512, COP3530,
CDA4101, COP4610,
CDA4400, COP4225,
CIS4610, COP5621,
COP4540
Topological sorting (algorithm)
 In a DAG, there must be a vertex with no
incoming edges
 Have each vertex maintain its indegree
 Have each vertex maintain a Boolean flag
found
 Repeatedly find a vertex of current indegree 0,
assign it a rank, then reduce the indegrees of
the vertices in its adjacency list
 If a vertex of current indegree 0 has been
already found, a cycle exists, output failure
Initializing indegree computation
struct Vertex{
list<Vertex> adj;
//
Adjacency list
bool known;
int indegree;
int rank;
// Other data and
// member functions // as
needed
};
// Assume vertices in
// vector<Vertex> verts;
void computeInDegrees(){
for(int i=0; i<verts.size();
verts[i].indegree =0, i++);
for(int i=0; i< verts.size(); i++) {
for(list<Vertex>::iterator j=
verts[i].adj.begin();
j!= verts[i].adj.end();
(*j).indegree++, j++);
}
}
In plain English, the above first sets all indegrees temporarily to 0,
then visits all vertices’ adjancency lists, and for each edge found,
increments the indegree of pointed vertex
Topological sorting (final)
int topologicalSort() {
list<Vertex> zeroIn;
computeInDegrees(); //Initialize indegrees
for(int i=0; i< verts.size(); i++) {
if (verts[i].indegree ==0)
zeroIn.push_back(verts[i]);
}
int rank=0;
Vertex curr;
while(rank < verts.size()) {
if(zeroIn.empty()) return FAILURE; //A cycle found!
curr = zeroIn.back();
zeroIn.pop_back();
curr.rank = rank++;
for(list<Vertex>::iterator j = curr.adj.begin(); j != curr.adj.end(); j++) {
(*j).indegree--;
if( (*j).indegree == 0) zeroIn.push_back(*j);
}
}
return SUCCESS;
}