Graphs
From charlesreid1
Graphs are mathematical objects consisting of nodes and edges. The original inventor of graph theory was Leonhard Euler, who used it to solve the Seven Bridges of Königsberg problem.
Notes
Goodrich - Data Structures - Chapter 12
The Goodrich book is less extensive, less mathematical, and more practical. The focus is on graph implementations, not on graph theory.
Data Structures
Goodrich begins Chapter 12 by covering data structures common in storing graphs: Graphs/Data Structures
- Edge list (two linked lists, one for vertices, one for edges)
- Adjacency list (one linked list for vertices, storing references to edges)
- Adjacency map (map that stores vertices as keys, other vertices and the edge that links them to the key vertex as values)
- Adjacency matrix (N x N matrix, where N is number of vertices, with entry (i,j) indicating an edge connecting vertex i to vertex j)
Graph Traversals
Depth first search on graphs:
Breadth first search on graphs:
Transitive Closure
Transitive closure graphs:
Directed Acyclic Graphs
Topographical sort of directed acyclic graphs:
Shortest Paths
Dijkstra's algorithm:
Minimum Spanning Trees
Minimum spanning trees:
Diestel - Graph Theory
Link to book: http://www.cs.unibo.it/babaoglu/courses/cas00-01/tutorials/GraphTheory.pdf
Chapter 1: Basics
Chapter 1 is a litany of definitions, concepts, and theorems important to laying the groundwork for discussing graph theory.
Chapter 2: Matching
Chapter 2 introduces wave after wave of new terms and notation, and is a bit hard to follow. It covers the concept of finding a set of edges that can connect all vertices between two subsets of vertices on a graph.
Chapter 3: Connectivity
Chapter 3 covers k-connectedness on graphs. Being k-connected means any two of its vertices can be joined by k independent paths.
Remaining Chapters
Reading this book is like trying to eat cardboard. No real insight or learning here.
Flags
