A recurring theme when working with graphs is that the best representation depends on what you need to do with your graph. For example, using adjacency lists (or arrays) keeps the overhead low and lets you efficiently iterate over N(v) for any node v. However, checking whether u and v are neighbors is linear in the minimum of their degrees, which can be problematic if the graph is dense, that is, if it has many edges. In these cases, adjacency sets may be the way to go.
- Chapter 2: The Basics
- from Python Algorithms: Mastering Basic Algorithms in the Python Language, Second Edition
- Publisher: Apress
- Released: September 2015
adjacency set is better for checking neighborship, list is better for iteration
Share this highlighthttp://www.safaribooksonline.com/a/python-algorithms-mastering/8197681/