Cmsc 341

Cmsc 341

CMSC 341 Lecture 21 Graphs (Introduction) Prof. Neary Based on slides from previous iterations of this course (Dr. Katherine Gibson) Basic Graph Definitions A graph G = (V,E) consists of a finite set of vertices, V, and a finite set of edges, E. Each edge is a pair (v, w) where v, w V V and E are sets, so each vertex v V is unique, and each edge e E is unique. Edges are sometimes called arcs or lines Vertices are sometimes called nodes or points UMBC CMSC 341 Graphs (Introduction) 2 Graph 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

337 HNL 2555 LAX 3 4 17 1233 ORD 802 SFO 1843 DFW 849 PVD LGA 87 3 1

1120 UMBC CMSC 341 Graphs (Introduction) 2 14 10 9 9 MIA 3 Graph Applications Graphs can be used to model a wide range of applications including Intersections and streets within a city Roads/trains/airline routes connecting cities/countries Computer networks Electronic circuits What else?

UMBC CMSC 341 Graphs (Introduction) 4 Edge Types Directed edge Ordered pair of vertices (u,v) First vertex u is the origin flight ORD AA 1206 Second vertex v is the destination (e.g., a flight) 849 Undirected edge ORD miles PVD

PVD Unordered pair of vertices (u,v) (e.g., a flight route) UMBC CMSC 341 Graphs (Introduction) 5 Graph Types Directed graph All the edges are directed (edges are ordered pairs) (e.g., route network) Sometimes called a digraph Undirected graph All the edges are undirected (unordered pairs) (e.g., flight network) Sparse and dense graphs Few and many edges, respectively UMBC CMSC 341 Graphs (Introduction)

6 Example: Undirected Graph 2 3 5 4 1 All edges are two-way Edges are unordered pairs V = { 1, 2, 3, 4, 5 } E = { (1,2), (2,3), (3,4), (2,4), (4,5), (5,1) } UMBC CMSC 341 Graphs (Introduction) 7 Example: Directed Graph 2 3

5 4 1 All edges are one-way (as shown by arrows) Edges are ordered pairs V = { 1, 2, 3, 4, 5 } E = { (1,2), (3,2), (4,3), (2,4), (4,5), (5,1), (5,4) } UMBC CMSC 341 Graphs (Introduction) 8 Graph Terminology and Vocabulary 9 Terminology End vertices (or endpoints) of an edge U and V are the endpoints of a

Edges incident on a vertex Adjacent vertices U and V are adjacent Parallel edges h and i are parallel edges Self-loop a a, d, and b are incident on V j is a self-loop V b d U h

X c e W j Z i g f UMBC CMSC 341 Graphs (Introduction) Y 10 More Terminology Path Sequence of alternating vertices and edges Begins with a vertex V Ends with a vertex b a P1 Each edge is preceded and

d followed by its endpoints U X P2 Simple path c e Path such that all its vertices W g and edges are distinct Examples f Y P1=(V,X,Z) is a simple path P2=(U,W,X,Y,W,V) is a path that is not simple UMBC CMSC 341 Graphs (Introduction) Z h 11 More Terminology Cycle

Circular sequence of alternating vertices and edges Each edge is preceded and followed by its endpoints Acyclic: without a cycle Simple cycle V a U d C2 c Cycle such that all its vertices and edges are distinct Examples C1=(V,X,Y,W,U,V) is simple

C2=(U,W,X,Y,W,V,U) is a cycle that is not simple b UMBC CMSC 341 Graphs (Introduction) X e C1 g W f h Z Y 12 Vocabulary Vertex w is adjacent to vertex v if and only if (v, w) E. For undirected graphs, with edge (v, w), and hence also (w, v), w is adjacent to v and v is adjacent to w.

An edge may also have: Weight or cost -- an associated value Label -- a unique name The degree of a vertex, v, is the number of vertices adjacent to v. Degree is also called valence. UMBC CMSC 341 Graphs (Introduction) 13 Degrees For directed graphs vertex w is adjacent to vertex v if and only if (v, w) E In-degree of a vertex w is the number of edges (v,w) X has in-degree 3 a V b d

U X c Out-degree of a vertex w is the number of edges(w,v) h e W X has out-degree 2 UMBC CMSC 341 Graphs (Introduction) j Z i g f Y 14 Connectedness An undirected graph is connected if there is a path from

every vertex to every other vertex A directed graph is strongly connected if there is a path from every vertex to every other vertex A directed graph is weakly connected if there would be a path from every vertex to every other vertex, disregarding the direction of the edges A complete graph is one in which there is an edge between every pair of vertices A connected component of a graph is any maximal connected subgraph. Connected components are sometimes simply called components UMBC CMSC 341 Graphs (Introduction) 15 Graph Algorithms Graph Traversal Breadth First Search (BFS) Depth First Search (DFS) Uniform Cost Search (UCS) A/A* Search Etc... Shortest Paths

Bellman-Ford Dijsktras Floyd-Warshall UMBC CMSC 341 Graphs (Introduction) 16 Graph Traversal Depth First Search (DFS) DFS(v): Mark v as visited For each edge v -> u: DFS(u) (could use a stack instead of recursion) UMBC CMSC 341 Graphs (Introduction) 17 Graph Traversal Breadth First Search BFS(v): Initialize a queue Q

Mark v as visited, and enqueue v While Q is not empty: w = Q.dequeue() For each edge w -> u: If u is not visited, mark it as visited and enqueue it UMBC CMSC 341 Graphs (Introduction) 18 A Graph ADT Has some data elements q Vertices and Edges Has some operations q getDegree( u ) -- Returns the degree of vertex u (outdegree of vertex u in directed graph) q getAdjacent( u ) -- Returns a list of the vertices adjacent to vertex u (list of vertices that u points to for a directed graph) q isAdjacentTo( u, v ) -- Returns TRUE if vertex v is adjacent to vertex u, FALSE otherwise. Has some associated algorithms to be discussed. 8/3/2007 UMBC CMSC 341 Graphs

19 Adjacency Matrix Implementation Uses array of size |V| |V| where each entry (i ,j) is boolean q TRUE if there is an edge from vertex i to vertex j q FALSE otherwise q store weights when edges are weighted Very simple, but large space requirement = O(|V|2) Appropriate if the graph is dense. Otherwise, most of the entries in the table are FALSE. For example, if a graph is used to represent a street map like Manhattan in which most streets run E/W or N/S, each intersection is attached to only 4 streets and |E| < 4*|V|. If there are 3000 intersections, the table has 9,000,000 entries of which only 12,000 are TRUE. 8/3/2007 UMBC CMSC 341 Graphs 20 Undirected Graph / Adjacency Matrix 1 2

5 3 4 1 2 3 4 5 1 0 1 0 0 1 2 1 0 1 1 0 3 0 1 0

1 0 4 0 1 1 0 1 5 1 0 0 1 0 8/3/2007 UMBC CMSC 341 Graphs 21 Directed Graph / Adjacency Matrix 1 2 5 3

4 1 2 3 4 5 1 0 0 0 0 1 2 1 0 1 0 0 3 0 0 0 1 0 4 0

1 0 0 1 5 0 0 0 1 0 8/3/2007 UMBC CMSC 341 Graphs 22 Weighted, Directed Graph / Adjacency Matrix 1 8 2 2 5 6 5

7 2 3 3 4 1 2 3 4 5 1 0 0 0 0 8 2 2 0 7 0 0 3 0

0 0 3 0 4 0 6 0 0 5 5 0 0 0 2 0 8/3/2007 UMBC CMSC 341 Graphs 23 Adjacency Matrix Performance Storage requirement: O(| V|2 ) Performance: getDegree ( u ) isAdjacentTo( u, v )

O(|V|) O(1) getAdjacent( u ) O(|V|) 8/3/2007 UMBC CMSC 341 Graphs 24 Adjacency List Implementation If the graph is sparse, then keeping a list of adjacent vertices for each vertex saves space. Adjacency Lists are the commonly used representation. The lists may be stored in a data structure or in the Vertex object itself. q Vector of lists: A vector of lists of vertices. The ith element of the vector is a list, Li, of the vertices adjacent to vi. If the graph is sparse, then the space requirement is O( |E| + |V| ), linear in the size of the graph If the graph is dense, then the space requirement is O( |V|2 ) 8/3/2007 UMBC CMSC 341 Graphs 25

Vector of Lists 1 2 2 5 6 7 3 1 2 3 4 5 8 3 5 4 2 4 2 3 1

5 4 2 8/3/2007 UMBC CMSC 341 Graphs 26 Adjacency List Performance Storage requirement: O(|V| + |E|) Performance: O getDegree( u ) isAdjacentTo( u, v ) getAdjacent( u ) 8/3/2007 UMBC CMSC 341 Graphs 27

Recently Viewed Presentations

  • Suicide Prevention Strategy: LGBTs

    Suicide Prevention Strategy: LGBTs

    Jan Bridget. www.galyic.org.uk. All Areas are Relevant to LGBTs. High Risk Groups: young and middle aged men. people with a history of self-harm. Tailor approaches to improve mental health in specific groups, including: Survivors of abuse and violence.
  • Department of Transportation

    Department of Transportation

    KyHealth Choices A New Beginning For Kentucky Medicaid: Ensuring healthcare coverage for Kentucky's most vulnerable citizens KyHealth Choices Kentucky Medicaid Covers nearly half of all births in the Commonwealth per year Provides health coverage to 1 out of every 3...
  • Pharmacy Legacy Training: Controlled Substance Menu ...

    Pharmacy Legacy Training: Controlled Substance Menu ...

    Pyxis, AcuDose, Omnicell) without paperwork … check with your site to confirm your local procedure. So let's take a look at this menu now … Pharmacy Dispense without (VA FORM 10-2638) Select Primary Dispensing Site: MASTER VAULT//
  • The Pros and Cons of Face-to-Face Interviews

    The Pros and Cons of Face-to-Face Interviews

    Book Antiqua Arial Lucida Sans Wingdings 2 Wingdings Wingdings 3 Calibri Apex 1_Apex The Pros and Cons of Face-to-Face Interviews Social Cues Synchronous in Time Synchronous in Place Recording Interview Data Termination Face-to-Face is best when…
  • Fungus  Like Protists Chapter 19 p. 540 Fungus-like

    Fungus Like Protists Chapter 19 p. 540 Fungus-like

    Phylum Myxomycota Acellular Slime Molds Begin life cycles as amebalike cells that grow into large masses The Mass is actually a single cell with thousands of nuclei Slime Mold on the move Slime Mold movement Acellular Slime Mold cont.
  • Spearbearer Roman marble copy of  bronze by Polycleitos

    Spearbearer Roman marble copy of bronze by Polycleitos

    Times New Roman Default Design Spearbearer Roman marble copy of bronze by Polycleitos c. 440 BC Discus Thrower Roman marble copy of bronze by Myron c. 450 BC Slide 3 Slide 4 Apollo West Pediment Temple of Zeus at Olympia...
  • Lecture Presentation Chapter 2 The Metric System John

    Lecture Presentation Chapter 2 The Metric System John

    Applying the Unit Analysis Method. Applying the Unit Analysis Method. Step 1: Write down the unit asked for in the answer. Step 2: Write down the given value related to the answer. Step 3: Apply unit factor(s) to convert the...
  • ABOUT US LOCATION CONNECTIONS SERVICES BERTHS WAREHOUSES EQUIPMENT

    ABOUT US LOCATION CONNECTIONS SERVICES BERTHS WAREHOUSES EQUIPMENT

    Yard Tractor Fleet Sisu tractor units, in tandem with double-wide Magnum trailers and single-wide trailers as appropriate to the cargo. Squamish Terminals - Cargo Delivery Squamish Terminals has maintained a registered Quality Program certification since 1994. It represents our commitment...