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

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

20 Pages
118 Views
Unlock Document

Department
Computer Science
Course
CS 341
Professor
Forbes Burkowski
Semester
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

Log In


OR

Join OneClass

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

Sign up

Join to view


OR

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.


Submit