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) ., 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 ., a flight all the edges are directed ., route network Undirected graph n n all the edges are undirected ., flight network © 2014 Goodrich, Tamassia, Goldwasser Graphs 3 Applications cslab1a q Electronic circuits n n q n Highway network Flight network Computer networks n n n q Printed circuit board Integrated circuit Transportation networks n q cslab1b Local area network Internet Web 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 .
