(Redirected from Algorithms/Graphs)

Graphs are mathematical objects consisting of vertices and edges.

The original inventor of graph theory was (arguably) 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

This is arguably the most important graph algorithm, as many, many graph algorithms are based on the traversal procedure.

Depth first search and traversals on graphs: Graphs/Depth First Traversal

Euler tours on graphs: Graphs/Euler Tour

### Transitive Closure

Transitive closure graphs: Graphs/Transitive Closure

Floyd Warshall algorithm: Graphs/Floyd Warshall

### Directed Acyclic Graphs

Directed acyclic graphs are graphs that are both directed and that do not contain cycle.

Detecting cycles: Graphs/Cycles

Directed acyclic graphs: Graphs/DAGs

Topographical sort of directed acyclic graphs: Graphs/Topological Sort

### Shortest Paths

Dijkstra's algorithm:

### Minimum Spanning Trees

Minimum spanning trees:

## Diestel - Graph Theory

### 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.