Graph Algorithms

Contents:

• 1 Graph Nomenclature
  • 1.1 Subgraph
  • 1.2 Directed Graph
  • 1.3 Undirected Graph
  • 1.4 Paths and Connected Graphs
  • 1.5 Cyclic Graph
  • 1.6 Acyclic Graph
• 2 Modeling Graphs
  • 2.1 Representing Graphs as Lists
  • 2.2 Representing Graphs as Adjaceny Matrices
  • 2.3 Representing Sparse Graphs as Adjaceny Lists
• 3 Abstract Data Types for Graphs
  • 3.1 Adjacency List
  • 3.2 Reduced Graph
  • 3.3 List
  • 3.4 Mapping
• 4 Creating Adjacency Lists
• 5 Depth First Search
  • 5.1 Recursive Depth First Search
  • 5.2 Non-recursive Depth First Search
  • 5.3 Depth First Spanning Trees
  • 5.4 Depth First Traversal
• 6 Graph Structure Analysis
  • 6.1 Connected Components of a Graph
  • 6.2 Isolated Vertex Detection
  • 6.3 Cycle Detection
    • 6.3.1 Detecting Cycles in Undirected Graphs
    • 6.3.2 Detecting Cycles in Directed Graphs
• 7 Determining the Degree of Each Vertex
• 8 Vertex Elimination
  • 8.1 Eliminating a Single Vertex
  • 8.2 Eliminating Many Vertices
  • 8.3 Initializing Minimum Degree Vertex Tracking
  • 8.4 Maintaining the Reduced Graph
  • 8.5 Querying the Reduced Graph State
• 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:

• 1 Vertex Degree Summary for Figure 1

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