Class Notes (835,243)
Canada (509,044)
CPSC 319 (12)
Lecture 9

CPSC 319 Lecture 9: 09 Graphs

10 Pages
Unlock Document

Computer Science
CPSC 319
Leonard Manzara

Graphs Classification - Data structures where each node may have many predecessors and many successors - Are a generalization of tree structures, which are a generalization of linear structures Definitions - A graph consists of: o A non-empty set of vertices (nodes), and o A (possibly empty) set of edges (arcs) that connect vertices - The set of vertices is denoted with V o a = b ,b ,…,b 7 : A o a is the number of vertices in the set - The set of edges is denoted with E o Each edge is a pair of vertices from V: § E.g. b ,b c : o The set is a list of edges connecting vertices § E.g. J = bc,b 7 b ,bc, b:,b , 7 ,b: : ; o J is the number of edges in the set - A graph is denoted with d = (a,J) - If the edge pair is unordered, then the graph is said to be undirected o The path between the vertices is bidirectional o On diagrams, the edges are shown with plain lines (no arrows) - If the edge pair is ordered, the graph is a directed graph (digraph) o The path between vertices is unidirectional o On diagrams, the edges are shown with arrows - Two vertices are adjacent if an edge directly connects them o The vertices are called end vertices (or endpoints) § If directed, first endpoint is the origin, and the other is the destination o The neighbors of a vertex are all vertices that are adjacent to it - An edge is incident on a vertex if the vertex is one of the edge's endpoints o The degree of a vertex v is the number of incident edges on v § Denoted deg(v) o if deg(v) = 0, then v is an isolated vertex § Since E can be empty, a graph can consist entirely of isolated vertices - Two or more edges connecting the same 2 vertices are called parallel or multiple edges o A graph containing these is a multigraph - An edge connecting a vertex to itself is called a self-loop o A graph containing loops is called a pseudograph - A simple graph contains no loops or parallel edges - An edge may have a weight (or edge cost) that measures the cost of traversing it o Are positive integers or real numbers o A graph that incorporates weights is a weighted graph § On diagrams, edges are labeled with their weights - A path is a sequence of vertices connected by edges. o E.g. b ,b ,b c : ; - The unweighted path length is the number of edges on the path - The weighted path length is the sum of costs of edges on the path - In a simple path, each vertex occurs only once in the sequence - A circuit is a path that begins and ends at the same vertex, and no edges are repeated o However, vertices may be repeated - A simple cycle is a circuit where all vertices (except the first and last) are different o i.e. Is a simple path - In a connected graph, there is a path between every pair of distinct vertices - In a complete graph, there is one edge connecting every pair of vertices - A directed acyclic graph (DAG) is a digraph containing no cycles Operations on Graphs - Standard operations on the ADT o Create: set up an empty graph o Clear: remove contents of the graph o Insert node: add a vertex to the graph o Insert edge: connect one vertex to another o Delete node: remove a node (and incident edges) from the graph o Delete edge: remove a connection between nodes o Retrieve: get data stored in a node o Update: overwrite data for a node o Traverse: process each node in a specified order o Find node: search for a particular node o Find edge: search for a connection between nodes Graph Representation - E.g. Drozdek p. 378 (older version), p. 407 (newer version) - Adjacency matrix o Is a × a 2-D array o Each row and column is labeled with a vertex o 1 indicates an edge connecting vertices o 0 indicates no edge - Adjacency list o Uses a linked list for all the vertices o Each vertex has its own linked list showing adjacent vertices § i.e. Shows incident edges 378 ■ Chapter 8 Graphs FIGURE 8.2 Graph representations. (a) A graph represented as (b–c) an adjacency list, (d) an adja- cency matrix, and (e) an incidence matrix. a a c d f b \ c d e b d e f g \ (a) c a f \ d a b e f a c d f \ b d e c a f e b d d a b e f e b d \ f a c d g f a c d \ (b) g \ \ (c) a b c d e f g ac ad af bd be cf de df a 0 0 1 1 0 1 0 a 1 1 1 0 0 0 0 0 b 0 0 0 1 1 0 0 b 0 0 0 1 1 0 0 0 c 1 0 0 0 0 1 0 c 1 0 0 0 0 1 0 0 d 1 1 0 0 1 1 0 d 0 1 0 1 0 0 1 1 e 0 1 0 1 0 0 0 e 0 0 0 0 1 0 1 0 f 1 0 1 1 0 0 0 f 0 0 1 0 0 1 0 1 g 0 0 0 0 0 0 0 g 0 0 0 0 0 0 0 0 (d) (e) Another representation is a matrix, which comes in two forms: an adjacency matrix and aninci dence matrix. An adjacency matrix of graph G = (V,E) is a binary |V |× |V |matrix such that each entry of this matrix Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Depth-First Graph Traversal - Basic idea: o Visit vertex b o Recursively visit each unvisited vertex adjacent to b § Implicitly uses a stack o After backtracking, traverse any unvisited vertices with same recursive process - Vertices must include a field to indicate if it has been visited - Pseudocode (Drozdek p. 379-380) - Example traversals (Drozdek p. 380-381): solid lines show traversal path - This algorithm creates a tree (or set of trees) that include all vertices of the graph o Called a spanning tree o Edges included in this tree are called forward edges (or tree edges) § Shown with solid lines o Edges not included are called back edges § Indicated with dashed lines 380 ■ Chapter 8 Graphs o Is < a + J for the adjacency list : o Is < a if num(u) is 0r the adjacency matrix attach edge(uv) to edges; DFS(u); DFS(v)
 num(v)= i++;
thFirstSearch() for all vertices v for all vertices u adjacent to v edges = null; ii = 1;u) is 0 while there is a vertex v such that num(v) is 0 DFS(v);ttach edge(uv) to edges; DFS(u); output edges; Figure 8.3 contains an example with the numbers num(v) assigned toeach vertex v shown in parentheses. Having made all necessaorn ,isatzyialitnii depthFirstSearch()depthFirstSearch()calls DFS(a). DFS() is first invoked for vertex a; num(a) is for alassigned number 1. a has four adjacent vertices, and vertex e is chosen for the next in- vocatinum(v) = 0;which assigns number 2 to this vertex, that is,num(e) = 2, and puts the edge(ae) in edges.Vertex e has two unvisited adjacent vertices,and DFS()is called 
edgesfor the first of them, the vertexf. The call DFS(f) leads to the assignmentnum(f ) = 3 
i = 1;nd puts theedge(ef ) in edges.Vertex f has only one unvisited adjacent vertex,i; thus, the fourth call, DFS(i),lea ds to the assignment num(i) = 4 and totheattachingof 
while there is a vertex v such that num(v) is 0 adjacent vertices; hence,we return to call DFS(f) and then to DFS(e) in which vertex i is accessed only to learn that num(i) is not 0, whereby the edge(ei) is not included in edges.Therestoftheexecutioncanbe output edges;sily in Figure 8.3b. Soldi lines indicate edges included in the setedges. FIGURE 8.3 An example of application of the depSection 8.2 Graph Traversals a ■rap381 a from vertex v has not been processed.Asaresult,certdges in the original graph do not appear in the resulting tree. The edges included in this tree are calle d forward e edges (or tree edges), and the edges not included in this tree are calle d back edges and f are shown as hashed lines. f(3) g(5) h(8) i Figure 8.4 illustrates the exi(4)ion of this algorithm for adigraph.Notice that the ori(a)al graph results in three spanning trees, alth(b)hwe started with only two iso- lated subgraphs. FIGURE 8.4 The depthFirstSearch() algorithm applied to a digraph. Note that this algorithm guarantees generating a tree (or a forest, a set of trees) that includes or spans over all vertices of the original graph. A tree that meets this condition is called a spanning tree. The fact that a tree is generated is ascertaine d by a the fact that the algorithm does not include in the resulting tree any edge that leads e from the currently analyzed verte(2)o a vertedy analyzed.Ane dge is added to edges only if the con dition in “if num(u) is 0”istrue;thatis,ifu reachable f g h f(4) g(6) h(8) i i(3) (a) (b) The complexity ofepthFirstSearch() is O( V |+ |E|) because (a) initializ- Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. ing num(v) for each vertex v requ|V|steps; (b) DFS(v) is called deg(v) times for each v—that is, once for each edge of v (to spawn into more calls or to finish the chain Breadth-first Graph Traversal 382 - ■ BasChapter 8 Graphs o Process first vertex 382 ■ Chapter 8 Graphs o Then process all its unvisited neighbor vertices breadthFirstSearch() o Then all unforitall verticeu of neighbors, etc. o Needs a queue hnums(u) = 0;) for all verticeu - Pseudocode (Drozdek p. 382) null; - Example traversals (Drozdek p. 382) while = there is a vertvxsuch that num(v) == 0 i = 1; breadthFirstSearch() whileum there is a vertvxsuch that num(v) == 0 enqueue(v); for all vertices u whilev)queue is not empty num(u) = 0;
 enqueue(v); while= queue is not empty edges = null;
 for all verticeu adjacent tov i = 1;
 v = ifeqnume(u) is 0 while there is a vertex v such that num(v) == 0cent tov if num (u) =is0+; num(v)=i++; enqueue(u); enqueue(v); nattach edg(vu) to
More Less

Related notes for CPSC 319

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.