false

Class Notes
(835,068)

Canada
(508,910)

University of Waterloo
(18,569)

Computer Science
(798)

CS 341
(26)

Forbes Burkowski
(15)

Lecture

Unlock Document

Computer Science

CS 341

Forbes Burkowski

Fall

Description

Graph Algorithms
• Graphs and their representation:
• A graph G = (V, E)
• V is a set of vertices V i {v | i = 1, 2, …, n}
• E is a set of edges E = {ej| j = 1, 2, …, m} that
connect the vertices.
• Edge e may be represented by the pair (u, v)
where u and v are the vertices being connected
by e.
• Depending on the problem, the pair may be
ordered or unordered.
Graph Algorithms
• Many problems can be represented as
graphs:
• Traveling Salesperson Problem
• Airline flights
• Friends who know each other
• Moves in a game (each node = the state of the
board or game, each edge = a valid move
between different positions).
1 Directed and Undirected Graphs
• An undirected graph, G = is the pair:
• V = set of distinct vertices
• E = set of edges;
• For example:
V = {t, u, v, w, x, y, z}
E = {{u, v}, {u, w}, {v, w}, {v, y}, {x, z}}
Directed and Undirected Graphs
• A directed graph, G = :
• Similar to an undirected graph except E is a set
of ordered pairs.
• For example:
E = {, , , , }
2 More Definitions
• Weighted graphs:
• A weighted graph has a value assigned to each of
its edges.
• More formally, there is a weight function w: E R.
• R = real numbers.
• We denote this as either w(e) with e in E or w(u, v) with
u and v representing the vertices of the edge.
More Definitions
• Degree:
• The degree of vertex v, denoted by deg(v), is the
number of edges that meet at v.
• Let v be a vertex in a directed graph G.
• The number of vertices of G adjacent from v is called
the outdegree of v.
– i.e. the number of edges originating in v.
• The number of vertices of G adjacent to v is called the
indegree of v.
– i.e. the number of edges at v.
3 Representations of Graphs
• Pointers:
• Represent each vertex with a node.
• Each vertex (i.e. node) has pointers to adjacent
vertices.
• Problem: How do we rapidly determine whether
there is a pointer from u to v?
• In general, the representation should provide the
functionality needed for the application.
• Reasonable questions for a graph:
– Is there an edge between vertex i and vertex j ?
– Whatare the neighbours of vertex i ?
Representations of Graphs
• Adjacency matrix:
• Assign each vertex an integer
u v w x y z t index
u 1 1 (in this example, u = 1, v = 2, etc.)
v 1 1 1
w 1 1 • M[i, j] = 1 if i and j are
neighbours, 0 otherwise.
x 1
y 1
z 1 • The matrix is symmetric for an
undirected graph.
t
• For a directed graph we will likely
have an asymmetric matrix.
4 Representations of Graphs
• Adjacency matrix notes:
• Blank row: no neighbours — isolated point.
• M[i, i] = 1 ➔ self-loop
• Undirected graphs are symmetrical
• Space
• |V| bits
• (|V| + |V|)/2 (if undirected, but harder to actually
implement).
• Additional information, such as cost of an edge, could be
stored in the matrix.
Representations of Graphs
• Cost of operations
• Are vertices i and j adjacent?O(1)
• Add or delete edge O(1)
• Add vertex: increases size of matrix
• Find neighbours of v O(|V|)
(even if no neighbo.rs)
5 Representations of Graphs
• Adjacency lists:
• a linked memory representation.
• Each vertex has a linked list of its neighbouring vertices.
• Adjacency Lists:
Undirected Example Directed Example
v w
u u w y a b c
v b e
w u v b
x z c
y v d b
z x e
t f f
Representations of Graphs
• Adjacency list notes:
• Space:
• O(|V| + |E|)
2
• Much smaller than O(|V| ) for a sparse graph .
• Cost of operations:
• Add an edge O(1)
• Delete an edge Search lists for each endpoint.
• Add vertex Depends on the implementation.
• Find neighbours O(# neighbours) (better than Adj. Matrix)
• Are i, j adjacent? Search the list (worse than Adj. Matrix)
6 Graph Theory Definitions
• Path:
• Given the graph G(V, E), a path from vertex u to vertex w
is a sequence of vertices (v0, 1 , …,kv ) such that u =0v ,
w = v k and (vi-1vi is in E for all i = 1, 2, …, k.
• Simple path:
• A path is simple if all the vertices in the path are distinct.
• Cycle:
• In a directed graph, a path (v , v , …, v ) forms a cycle if
0 1 k
v0= v k and the path contains at least one edge.
• A graph with no cycles is acyclic.
• Connected graphs:
• An undirected graph is connected if every pair of
vertices is connected by a path.
Graph Theory Definitions
• Reachable:
• Vertex v is reachable from vertex u if there is a
simple path in G going from u to v.
• Connected components:
• The connected components of a graph are the
equivalence classes of vertices under the “is
reachable from” relation.
• So, an undirected graph is connected if it has
exactly one connected component.
7 Graph Theory Definitions
• Subgraph:
• is a subgraph of G V ’⊆V,and sE’⊆ E.t(G’= ) ’,E ’
• Induced subgraph:
• Given a setV ’⊆V , the subgraph of G induced
by V ’is the graph where
G’= ( ’,E )
E’= {(u,v ∈) u,v∈V ’ .}
Graph Theory Definitions
• Spanning tree:
• Given G = (V, E), a spanning tree is a connected
acyclic subgraph containing all the vertices in V.
• A spanning tree is not necessarily unique.
8 Graph Theory Definitions
Lemma: In a spanning tree
• Any two vertices are connected by a unique
(simple) path.
• If any edge is removed from the spanning
tree, then we get a disconnected graph.
• Adding any extra edge results in a unique
cycle.
• The number of edges is n – 1.
Tree traversals
• Review from CS 134:
• We usually describe tree traversals recursively.
• Preorder (visit node before children)
• Postorder (visit children before node)
• Inorder
– For binary trees only
– Visit left child, node, right child
• All take Θ(n) time for an n-node tree.
9 BFS and DFS
• Breadth-first, depth-first search
• Each search strategy starts at a node, and
explores the entire connected component.
• General view:
• Vertices start out coloured white (not visited).
• A visited vertex is coloured gray (visited, but may
still have white neighbors).
• When all neighbours of a vertex are visited, it is
coloured black.
General View of Searching
• The gray nodes form a “frontier” or “wave front”.
• We choose any non-black neighbour of a gray
node to be next visited.
• In general, we want to perform a
computation:
• Do preprocessing when colouring gray.
• Do postprocessing when colouring black.
10 Breadth First Search
• General strategy for BFS:
• Use a queue (first-in, first-out) to store gray
nodes.
• Start by taking any vertex, colour it gray, add it to
the queue.
• Repeat:
• Dequeue a vertex (call it u).
• Find a white node adjacent to u, colour it gray and add
it to the queue.
• When you cannot find any such white node colour u
black.
Example of BFS
A
B C G
D E
F

More
Less
Related notes for CS 341

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.