DOC PREVIEW
UW CSE 332 - Introduction to Graphs

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSE332: Data AbstractionsLecture 15: Introduction to GraphsDan GrossmanSpring 2010Graphs• A graph is a formalism for representing relationships among items– Very general definition because very general concept•A graph is a pairG = (V,E)–A set of vertices, also known as nodesV = {v1,v2,…,vn}–A set of edgesE = {e1,e2,…,em}• Each edge eiis a pair of vertices (vj,vk)• An edge “connects” the vertices• Graphs can be directed or undirectedSpring 2010 2CSE332: Data AbstractionsHanLeiaLukeV = {Han,Leia,Luke}E = {(Luke,Leia), (Han,Leia), (Leia,Han)}An ADT?• Can think of graphs as an ADT with operations like isEdge((vj,vk))• But what the “standard operations” are is unclear• Instead we tend to develop algorithms over graphs and then use data structures that are efficient for those algorithms• Many important problems can be solved by:1. Formulating them in terms of graphs2. Applying a standard graph algorithm• To make the formulation easy and standard, we have a lot of standard terminology about graphsSpring 2010 3CSE332: Data AbstractionsSome graphsFor each, what are the vertices and what are the edges?• Web pages with links• Facebook friends• “Input data” for the Kevin Bacon game• Methods in a program that call each other• Road maps (e.g., Google maps)• Airline routes• Family trees• Course pre-requisites•…Wow: Using the same algorithms for problems for this very different data sounds like “core computer science and engineering”Spring 2010 4CSE332: Data AbstractionsUndirected Graphs•In undirected graphs, edges have no specific direction– Edges are always “two-way”Spring 2010 5CSE332: Data Abstractions• Thus, (u,v) ∈ E implies (v,u) ∈ E. – Only one of these edges needs to be in the set; the other is implicit•Degreeof a vertex: number of edges containing that vertex– Put another way: the number of adjacent verticesABCDDirected graphs• In directed graphs (sometimes called digraphs), edges have a specific directionSpring 2010 6CSE332: Data Abstractions• Thus, (u,v) ∈ E does not imply (v,u) ∈ E. • Let (u,v) ∈ E mean u → v and call u the source and vthe destination• In-Degree of a vertex: number of in-bound edges, i.e., edges where the vertex is the destination• Out-Degree of a vertex: number of out-bound edges, i.e., edges where the vertex is the sourceor2 edges hereABCDABCSelf-edges, connectedness, etc.[Before you get the wrong idea, graphs are very flexible…]•A self-edge a.k.a. a loop is an edge of the form (u,u)– Depending on the use/algorithm, a graph may have:• No self edges• Some self edges• All self edges (in which case often implicit, but we will be explicit)• A node can have a degree / in-degree / out-degree of zero• A graph does not have to be connected– Even if every node has non-zero degreeSpring 2010 7CSE332: Data AbstractionsMore notationFor a graph G=(V,E):• |V| is the number of vertices• |E| is the number of edges–Minimum?– Maximum for undirected?– Maximum for directed?• If (u,v) ∈ E– Then v is a neighbor of u, i.e., v is adjacent to u– Order matters for directed edgesSpring 2010 8CSE332: Data AbstractionsABCV = {A, B, C, D}E = {(C, B), (A, B), (B, A)(C, D)}DMore notationFor a graph G=(V,E):• |V| is the number of vertices• |E| is the number of edges– Minimum? 0– Maximum for undirected? |V||V+1|/2 ∈ O(|V|2)– Maximum for directed? |V|2∈ O(|V|2)(assuming self-edges allowed, else subtract |V|)• If (u,v) ∈ E– Then v is a neighbor of u, i.e., v is adjacent to u– Order matters for directed edgesSpring 2010 9CSE332: Data AbstractionsABCDExamples againWhich would use directed edges? Which would have self-edges? Which would be connected? Which could have 0-degree nodes?• Web pages with links• Facebook friends• “Input data” for the Kevin Bacon game• Methods in a program that call each other• Road maps (e.g., Google maps)• Airline routes• Family trees• Course pre-requisites•…Spring 2010 10CSE332: Data AbstractionsWeighted graphs• In a weighed graph, each edge has a weight a.k.a. cost– Typically numeric (most examples will use ints)– Orthogonal to whether graph is directed– Some graphs allow negative weights; many don’tSpring 2010 11CSE332: Data Abstractions20303560MukilteoEdmondsSeattleBremertonBainbridgeKingstonClintonExamplesWhat, if anything, might weights represent for each of these? Do negative weights make sense?• Web pages with links• Facebook friends• “Input data” for the Kevin Bacon game• Methods in a program that call each other• Road maps (e.g., Google maps)• Airline routes• Family trees• Course pre-requisites•…Spring 2010 12CSE332: Data AbstractionsPaths and Cycles•A path is a list of vertices [v0,v1,…,vn] such that (vi,vi+1)∈E for all 0 ≤ i < n. Say “a path from v0 to vn”•A cycle is a path that begins and ends at the same node (v0==vn)Spring 2010 13CSE332: Data AbstractionsSeattleSan FranciscoDallasChicagoSalt Lake CityExample: [Seattle, Salt Lake City, Chicago, Dallas, San Francisco, Seattle]Path Length and Cost• Path length: Number of edges in a path• Path cost: sum of the weights of each edgeExample where P= [Seattle, Salt Lake City, Chicago, Dallas, San Francisco, Seattle]Spring 2010 14CSE332: Data AbstractionsSeattleSan FranciscoDallasChicagoSalt Lake City3.5222.5322.52.5length(P) = 5cost(P) = 11.5Simple paths and cycles•A simple path repeats no vertices, except the first might be the last[Seattle, Salt Lake City, San Francisco, Dallas][Seattle, Salt Lake City, San Francisco, Dallas, Seattle]•Recall, a cycle is a path that ends where it begins[Seattle, Salt Lake City, San Francisco, Dallas, Seattle][Seattle, Salt Lake City, Seattle, Dallas, Seattle]•A simple cycle is a cycle and a simple path[Seattle, Salt Lake City, San Francisco, Dallas, Seattle]Spring 2010 15CSE332: Data AbstractionsPaths/cycles in directed graphsExample:Is there a path from A to D?Does the graph contain any cycles?Spring 2010 16CSE332: Data AbstractionsABCDPaths/cycles in directed graphsExample:Is there a path from A to D? NoDoes the graph contain any cycles? NoSpring 2010 17CSE332: Data AbstractionsABCDUndirected graph connectivity• An undirected graph is connected if for allpairs of vertices u,v, there exists a path from u to v• An undirected graph is complete, a.k.a. fully connected if for all pairs of vertices u,v, there


View Full Document

UW CSE 332 - Introduction to Graphs

Download Introduction to Graphs
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to Graphs and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Graphs 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?