CSE 326: Data Structures Part 8 GraphsOutlineGraph ADTWhat Graph is THIS?ReferralWeb (co-authorship in scientific papers)Biological Function Semantic NetworkGraph Representation 1: Adjacency MatrixGraph Representation 2: Adjacency ListDirected vs. Undirected GraphsGraph DensityWeighted GraphsPaths and CyclesPath Length and CostConnectivityTrees as GraphsDirected Acyclic Graphs (DAGs)Application of DAGs: Representing Partial OrdersTopological SortTopo-Sort Take OneTopo-Sort Take TwoRecall: Tree TraversalsDepth-First SearchIterative Version DFS Pre-order TraversalLevel-Order Tree TraversalBreadth-First SearchQUEUEGraph TraversalsDemos on Web Page DFS BFSIs BFS the Hands Down Winner?Space RequirementsDFS Space RequirementsConclusionIterative Deepening DFSAnalysis of Iterative DeepeningAsymptotic AnalysisA Better Case(More) ConclusionsSingle Source, Shortest Path for Weighted GraphsThe Trouble with Negative Weighted CyclesEdsger Wybe Dijkstra (1930-2002)Dijkstra’s Algorithm for Single Source Shortest PathPseudocode for DijkstraImportant FeaturesDijkstra’s Algorithm in ActionDemo Dijkstra’sData Structures for Dijkstra’s AlgorithmCSE 326: Data Structures Lecture 8.B Heuristic Graph SearchHomework Hint - Problem 4Slide 49Huge GraphsImplicitly Generated GraphsBlocks WorldProblem: Branching FactorAn Easier CaseBest-First SearchBest First in ActionProblem 1: Led AstrayProblem 2: OptimalitySub-Optimal SolutionSynergy?A* (“A star”)OptimalityProblem 2 RevisitedSlide 64Slide 65Slide 66Slide 67Slide 68Slide 69What Would Dijkstra Have Done?Proof of A* OptimalityWhat About Those Blocks?3-Blocks State Space Graph3-Blocks Best First Solution3-Blocks BFS Solution3-Blocks A* SolutionOther Real-World ApplicationsComing UpCSE 326: Data Structures Part 8.C Spanning Trees and MoreTodayIncremental HashingMaze RunnerJava NoteAmazing Java TrickLongest Path ProblemDijkstraReverse DijkstraDoes it Work?ProblemCounting Connected ComponentsUsing DFSUsing Union / FindSlide 93Machine Vision: Blob FindingSlide 95Blob FindingTradeoffsHigh-Level Blob-LabelingBlob-Labeling AlgorithmSpanning TreeApplications of Minimal Spanning TreesKruskal’s Algorithm for Minimum Spanning TreesKruskal’s Algorithm in Action (1/5)Kruskal’s Algorithm in Action (2/5)Kruskal’s Algorithm in Action (3/5)Kruskal’s Algorithm in Action (4/5)Kruskal’s Algorithm Completed (5/5)Why Greediness WorksData Structures for Kruskal’s AlgorithmSlide 110Prim’s AlgorithmSlide 112Sentence DisambiguationPowerPoint PresentationSentence Disambiguation as Shortest PathSlide 116Technical ConcernsLogs to the RescueTo Think AboutQuestionAll Pairs Shortest PathDynamic Programming ApproachFloyd-Warshall AlgorithmCSE 326: Data StructuresPart 8GraphsHenry KautzAutumn Quarter 2002Outline•Graphs (TO DO: READ WEISS CH 9)•Graph Data Structures•Graph Properties•Topological Sort•Graph Traversals–Depth First Search–Breadth First Search–Iterative Deepening Depth First•Shortest Path Problem–Dijkstra’s AlgorithmGraph ADTGraphs are a formalism for representing relationships between objects–a graph G is represented as G = (V, E)•V is a set of vertices•E is a set of edges–operations include:•iterating over vertices•iterating over edges•iterating over vertices adjacent to a specific vertex•asking whether an edge exists connected two verticesHanLeiaLukeV = {Han, Leia, Luke}E = {(Luke, Leia), (Han, Leia), (Leia, Han)}What Graph is THIS?ReferralWeb(co-authorship in scientific papers)Biological Function Semantic NetworkGraph Representation 1: Adjacency MatrixA |V| x |V| array in which an element (u, v) is true if and only if there is an edge from u to vHanLeiaLukeHan Luke LeiaHanLukeLeiaRuntime:iterate over verticesiterate ever edgesiterate edges adj. to vertexedge exists?Space requirements:Graph Representation 2: Adjacency ListA |V|-ary list (array) in which each entry stores a list (linked list) of all adjacent verticesHanLeiaLukeHanLukeLeiaspace requirements:Runtime:iterate over verticesiterate ever edgesiterate edges adj. to vertexedge exists?Directed vs. Undirected GraphsHanLeiaLukeHanLeiaLuke•In directed graphs, edges have a specific direction:•In undirected graphs, they don’t (edges are two-way):•Vertices u and v are adjacent if (u, v)  EGraph DensityA sparse graph has O(|V|) edgesA dense graph has (|V|2) edgesAnything in between is either sparsish or densy depending on the context.Weighted Graphs20303560MukilteoEdmondsSeattleBremertonBainbridgeKingstonClintonThere may be more information in the graph as well.Each edge has an associated weight or cost.Paths and CyclesA path is a list of vertices {v1, v2, …, vn} such that (vi, vi+1)  E for all 0  i < n.A cycle is a path that begins and ends at the same node.SeattleSan FranciscoDallasChicagoSalt Lake Cityp = {Seattle, Salt Lake City, Chicago, Dallas, San Francisco, Seattle}Path Length and CostPath length: the number of edges in the pathPath cost: the sum of the costs of each edgeSeattleSan FranciscoDallasChicagoSalt Lake City3.5222.5322.52.5length(p) = 5 cost(p) = 11.5ConnectivityUndirected graphs are connected if there is a path between any two verticesDirected graphs are strongly connected if there is a path from any one vertex to any otherDirected graphs are weakly connected if there is a path between any two vertices, ignoring directionA complete graph has an edge between every pair of verticesTrees as Graphs•Every tree is a graph with some restrictions:–the tree is directed–there are no cycles (directed or undirected)–there is a directed path from the root to every nodeABD ECFHGJIBAD!Directed Acyclic Graphs (DAGs)DAGs are directed graphs with no cycles.main()add()access()mult()read()Trees  DAGs  Graphsif program call graph is a DAG, then all procedure calls can be in-linedApplication of DAGs: Representing Partial Orderscheck inairportcalltaxitaxi toairportreserveflightpackbagstakeflightlocategateTopological SortGiven a graph, G = (V, E), output all the vertices in V such that no vertex is output before any other vertex with an edge to it.check inairportcalltaxitaxi toairportreserveflightpackbagstakeflightlocategateTopo-Sort Take OneLabel each vertex’s in-degree (# of inbound edges)While there are vertices remainingPick a vertex with in-degree of zero and output itReduce the in-degree of all vertices adjacent to itRemove it from the list of verticesruntime:Topo-Sort Take TwoLabel each vertex’s