Class Notes (835,068)
Canada (508,910)
CS 341 (26)

Lecture #8A - Graph Algorithms Introduction and Traversals Fall 2009

20 Pages
Unlock Document

Computer Science
CS 341
Forbes Burkowski

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 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

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
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.

Add your courses

Get notes from the top students in your class.