Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Data structures and algorithms in Java (6th edition): Chapter 14.5 - Goodrich, Tamassia, Goldwasser

This chapter provides knowledge of graph. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Graphs 3/25/14 15:37 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Graphs 1843 337 © 2014 Goodrich, Tamassia, Goldwasser 43 17 LAX ORD 802 SFO 1233 DFW Graphs 1 Graphs A graph is a pair (V, E), where n   n   n   q   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: n   n   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 2555 337 HNL 1843 ORD 802 q   43 17 LAX 1233 © 2014 Goodrich, Tamassia, Goldwasser DFW Graphs 849 2 14 PVD LGA 7 138 1120 MIA 2 1 Graphs 3/25/14 15:37 Edge Types q   Directed edge n   n   n   n   q   n   flight AA 1206 PVD ORD unordered pair of vertices (u,v) e.g., a flight route 849 miles PVD Directed graph n   n   q   ORD Undirected edge n   q   ordered pair of vertices (u,v) first vertex u is the origin second vertex v is the destination e.g., a flight all the edges are directed e.g., route network Undirected graph n   n   all the edges are undirected e.g., flight network © 2014 Goodrich, Tamassia, Goldwasser Graphs 3 Applications cslab1a q   Electronic circuits n   n   q   n   cs.brown.edu Highway network Flight network brown.edu qwest.net Computer networks n   n   n   q   math.brown.edu Printed circuit board Integrated circuit Transportation networks n   q   cslab1b att.net Local area network Internet Web cox.net John Databases n   Paul David Entity-relationship diagram © 2014 Goodrich, Tamassia, Goldwasser Graphs 4 2 Graphs 3/25/14 15:37 Terminology q   End vertices (or endpoints) of an edge n   q   n   q   U U and V are adjacent b d i W X has degree 5 g f h and i are parallel .