Data Structures and Algorithms: Graphs

337<br /> <br /> Graphs<br /> <br /> 3<br /> 74<br /> 1<br /> <br /> LAX<br /> <br /> 1233<br /> <br /> ORD<br /> 802<br /> <br /> SFO<br /> <br /> 1843<br /> <br /> DFW<br /> <br /> Data structures and Algorithms<br /> <br /> Acknowledgement:<br /> These slides are adapted from slides provided with Data Structures and Algorithms in C++<br /> Goodrich, Tamassia and Mount (Wiley, 2004)<br /> <br /> Outline and Reading<br /> Data structures for graphs (§13.2)<br /> Graph traversal (§13.3)<br /> Depth-first search<br /> Breadth-first search<br /> <br /> Directed graphs (§13.4)<br /> Shortest paths (§13.6)<br /> Dijkstra's Algorithm<br /> <br /> Minimum spanning trees (§13.7)<br /> Kruskal's Algorithm<br /> Prim-Jarnik Algorithm<br /> <br /> Graphs<br /> <br /> 2<br /> <br /> Graph<br /> A graph is a pair (V, E), where<br /> V is a set of nodes, called vertices<br /> E is a collection of pairs of vertices, called edges<br /> Vertices and edges are positions and store elements<br /> <br /> Example:<br /> A vertex represents an airport and stores the three-letter airport code<br /> An edge represents a flight route between two airports and stores the<br /> mileage of the route<br /> <br /> 2555<br /> <br /> 337<br /> <br /> HNL<br /> <br /> 3<br /> 74<br /> 1<br /> <br /> LAX<br /> <br /> 1233<br /> <br /> Graphs<br /> <br /> 849<br /> <br /> ORD<br /> <br /> 14<br /> <br /> 802<br /> <br /> SFO<br /> <br /> 1843<br /> <br /> LGA<br /> 138<br /> <br /> DFW<br /> <br /> 2<br /> <br /> PVD<br /> <br /> 7<br /> 1120<br /> <br /> 10<br /> 99<br /> <br /> MIA<br /> 3<br /> <br /> Edge Types<br /> (u,v)<br /> Directed edge<br /> ordered pair of vertices (u,v)<br /> first vertex u is the origin<br /> second vertex v is the destination<br /> <br /> v<br /> <br /> u<br /> flight AA 1206<br /> <br /> ORD<br /> <br /> DFW<br /> 802 miles<br /> <br /> e.g., a flight<br /> <br /> Undirected edge<br /> flight route<br /> <br /> unordered pair of vertices (u,v)<br /> <br /> ORD<br /> <br /> e.g., a flight route<br /> <br /> 802 miles<br /> <br /> DFW<br /> <br /> Directed graph (Digraph)<br /> all the edges are directed<br /> e.g., flight network<br /> <br /> Weighted edge<br /> Weighted graph<br /> <br /> Undirected graph<br /> all the edges are undirected<br /> e.g., route network<br /> <br /> all the edges are weighted<br /> <br /> Graphs<br /> <br /> 4<br /> <br /> Applications<br /> Electronic circuits<br /> Printed circuit board<br /> Integrated circuit<br /> <br /> Transportation networks<br /> Highway network<br /> Flight network<br /> <br /> Computer networks<br /> Local area network<br /> Internet<br /> Web<br /> <br /> Databases<br /> Entity-relationship diagram<br /> Graphs<br /> <br /> 5<br /> <br />