# Analysis of Algorithms Graphs 337 LAX 2010 Goodrich, Tamassia Graphs 3 4 17 1233 ORD 802 SFO 1843 DFW 1 Graphs A graph is a pair (V, E), where V is a set of nodes, called vertices E is a collection of pairs of vertices, called edges Example: A vertex represents an airport and stores the three-letter airport code An edge represents a flight route between two airports and stores the mileage of the route SFO 2010 Goodrich, Tamassia 337 HNL 2555 1843 43 7 1 LAX

1233 ORD 802 DFW Graphs 849 2 14 PVD LGA 87 3 1 1120 10 9 9 MIA 2 Edge Types Directed edge Undirected edge unordered pair of vertices (u,v) e.g., a flight mileage flight ORD AA 1206 PVD ORD 849

miles PVD Directed graph (digraph) ordered pair of vertices (u,v) first vertex u is the origin or source second vertex v is the destination e.g., a flight number all the edges are directed Undirected graph all the edges are undirected 2010 Goodrich, Tamassia Graphs 3 Applications cslab1a Electronic circuits cs.brown.edu Highway network Flight network Internet Social networks Printed circuit board Integrated circuit brown.edu qwest.net Computer networks

math.brown.edu Transportation networks cslab1b Six degrees of separation cox.net Facebook, line, etc. Databases att.net John Paul Entity-relationship diagram 2010 Goodrich, Tamassia Graphs David 4 Terminology End vertices (or endpoints) of an edge Edges incident on a vertex e W for digraphs h and i are parallel edges h

X c X has degree 5 In-degree and out-degree Parallel edges b d U and V are adjacent Degree of a vertex a, d, and b are incident on V U Adjacent vertices a U and V are the endpoints of a V j Z i g f Y Self-loop j is a self-loop 2010 Goodrich, Tamassia Graphs 5 Terminology (cont.) Path

Simple path sequence of alternating vertices and edges begins with a vertex ends with a vertex each edge is preceded and followed by its endpoints path such that all its vertices and edges are distinct Examples P1=(V,b,X,h,Z) is a simple path P2=(U,c,W,e,X,g,Y,f,W,d,V) is a path that is not simple 2010 Goodrich, Tamassia Graphs a U c V b d P2 P1 X e W h Z g f Y 6

Terminology (cont.) Cycle Simple cycle circular sequence of alternating vertices and edges each edge is preceded and followed by its endpoints cycle such that all its vertices and edges are distinct Examples C1=(V,b,X,g,Y,f,W,c,U,a,) is a simple cycle C2=(U,c,W,e,X,g,Y,f,W,d,V,a,) is a cycle that is not simple 2010 Goodrich, Tamassia Graphs a U c V b d C2 X e C1 g W f h Z Y

7 Properties Quiz! Property 1 Notation n m deg(v) v deg(v) 2m Proof: each edge is counted twice number of vertices number of edges degree of vertex v Property 2 In an undirected graph with no self-loops and no multiple edges m n (n 1))2 Proof: each vertex has degree at most (n 1)) Example n 4 m 6 deg(v) 3 What is the bound for a directed graph? 2010 Goodrich, Tamassia Graphs 8 Main Methods of the Graph ADT Vertices and edges Update methods are positions store elements

Accessor methods e.endVertices(): a list of the two endvertices of e e.opposite(v): the vertex opposite of v on e u.isAdjacentTo(v): true iff u and v are adjacent *v: reference to element associated with vertex v *e: reference to element associated with edge e 2010 Goodrich, Tamassia Graphs insertVertex(o): insert a vertex storing element o insertEdge(v, w, o): insert an edge (v,w) storing element o eraseVertex(v): remove vertex v (and its incident edges) eraseEdge(e): remove edge e Iterable collection methods incidentEdges(v): list of edges incident to v vertices(): list of all vertices in the graph edges(): list of all edges in the graph 9 Data Structures for Graphs

Edge-list structure Adjacency-list structure Adjacency-matrix structure 2010 Goodrich, Tamassia Graphs 10 Edge-List Structure Note list element origin node destination node reference to position in edge list Edge to Node list a element reference to position in node list v c b d w z Edge u

Node u Node only list of links to nodes a Edge list z w v b c d list of links to edges Edge list 2010 Goodrich, Tamassia Graphs 11 Adjacency-List Structure a Incidence list for each node Adjacency list u v b w list of links to incident edges uv vuw wv

Augmented edgeNote list references to positions in incidence list of end nodes u v w Incidence list for each node a 2010 Goodrich, Tamassia Edge list Graphs b 12 Adjacency-Matrix Structure b u Integer index associated with node w Adjacency matrix v a Augmented nodes Reference to edge for adjacent nodes

0 u 1 The old fashioned matrix just has 0 for no edge and 1 for edge 0 0 1 a 2010 Goodrich, Tamassia Graphs 2 2 v 1 w 2 b 13 Quiz! Performance n vertices, m edges no parallel edges no self-loops We shall stick to this structure! Edg e List Adjacency List Adjacenc y Matrix

nm nm n2 v.incidentEdges( ) m deg(v) n u.isAdjacentTo(v ) m min(deg(u), deg(v)) 1) insertVertex(o) 1) 1) n2 insertEdge(v, w, o) 1) 1) 1) Space Assume V & E are stored in doubly linked lists eraseVertex(v) 2010 Goodrich, Tamassia m Graphs deg(v) Create a 2new matrix 14 n