Handbook of Data Structures and Applications, 2nd Edition

4

Graphs*

Narsingh Deo

University of Central Florida

4.1Introduction

4.2Graph Representations

Weighted Graph Representation

4.3Connectivity, Distance, and Spanning Trees

Spanning Trees

4.4Searching a Graph

Depth-First Search•Breadth-First Search

4.5Simple Applications of DFS and BFS

Depth-First Search on a Digraph•Topological Sorting

4.6Minimum Spanning Tree

Kruskal’s MST Algorithm•Prim’s MST Algorithm•Boruvka’s MST Algorithm•Constrained MST

4.7Shortest Paths

Single-Source Shortest Paths, Nonnegative Weights•Single-Source Shortest Paths, Arbitrary Weights•All-Pairs Shortest Paths

4.8Eulerian and Hamiltonian Graphs

Acknowledgments

References

4.1Introduction

Trees, as data structures, are somewhat limited because they can only represent relations ...