# Graph Algorithms

###### Abstract

The network structure of many physical systems is represented by mathematical entities known as graphs. This document examines several of the computational algorithms of graph theory most relevant to network analysis.

Copyright © 1990 - 2012 Timothy Vismor

###### Contents:

- 1 Graph Nomenclature
- 2 Modeling Graphs
- 3 Abstract Data Types for Graphs
- 4 Creating Adjacency Lists
- 5 Depth First Search
- 6 Graph Structure Analysis
- 7 Determining the Degree of Each Vertex
- 8 Vertex Elimination
- References

###### List of Figures:

- 1 Example of a Directed Graph
- 2 Example of an Undirected Graph
- 3 Example of Cycles in a Digraph
- 4 Example of an Acyclic Digraph
- 5 Example of a Directed Tree
- 6 Example of a Rooted Free Tree
- 7 Adjacency List of Directed Graph in Figure 1
- 8 Adjacency List of Undirected Graph in Figure 2

###### List of Tables:

###### List of Algorithms:

- 1 Create Adjacency List of Undirected Graph
- 2 Map Vertices To Labeling Order
- 3 Create Ordered Adjacency List
- 4 Depth First Search
- 5 Recursive Depth First Search
- 6 Depth First Search With Recursion Removed
- 7 Non-recursive DFS Vertex Visitation
- 8 Depth First Traversal
- 9 Extract the Connected Components of a Graph
- 10 Isolated Vertex Detection
- 11 Cycle Detection in Undirected Graphs
- 12 Cycle Detection in Directed Graphs
- 13 Determine Vertex Degree Using Adjacency List
- 14 Determine Vertex Degree of Directed Graph Using Edges
- 15 Determine Vertex Degree of Undirected Graph Using Edges
- 16 Eliminate a Vertex from a Graph
- 17 Initialize Minimum Degree Vertex Tracking
- 18 Increase the Degree of a Vertex
- 19 Decrease the Degree of a Vertex
- 20 Remove a Vertex from the Reduced Graph
- 21 Determine if a Vertex is in the Reduced Graph