tailieunhanh - Data Structures and Algorithms: Graphs

Data Structures and Algorithms: Graphs products Data structures for graphs, Graph traversal, Depth-first search, Breadth-first search, Directed graphs, Shortest paths, Dijkstra's Algorithm, Minimum spanning trees. | 337 Graphs 3 74 1 LAX 1233 ORD 802 SFO 1843 DFW Data structures and Algorithms Acknowledgement: These slides are adapted from slides provided with Data Structures and Algorithms in C++ Goodrich, Tamassia and Mount (Wiley, 2004) Outline and Reading Data structures for graphs (§) Graph traversal (§) Depth-first search Breadth-first search Directed graphs (§) Shortest paths (§) Dijkstra's Algorithm Minimum spanning trees (§) Kruskal's Algorithm Prim-Jarnik Algorithm Graphs 2 Graph 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 Vertices and edges are positions and store elements 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 2555 337 HNL 3 74 1 LAX 1233 Graphs 849 ORD 14 802 SFO 1843 LGA 138 DFW 2 PVD 7 1120 10 99 MIA 3 Edge Types (u,v) Directed edge ordered pair of vertices (u,v) first vertex u is the origin second vertex v is the destination v u flight AA 1206 ORD DFW 802 miles ., a flight Undirected edge flight route unordered pair of vertices (u,v) ORD ., a flight route 802 miles DFW Directed graph (Digraph) all the edges are directed ., flight network Weighted edge Weighted graph Undirected graph all the edges are undirected ., route network all the edges are weighted Graphs 4 Applications Electronic circuits Printed circuit board Integrated circuit Transportation networks Highway network Flight network Computer networks Local area network Internet Web Databases Entity-relationship .