10.3 Graph ADT and Basic Operations

Graphs are powerful data structures that model relationships between entities. They consist of vertices and edges, representing connections in various real-world scenarios like social networks, transportation systems, and computer networks.

Graph ADTs provide a blueprint for implementing graphs, offering methods for vertex and edge manipulation, traversal, and analysis. Understanding graph operations and their complexities is crucial for efficient problem-solving in computer science and beyond.

Graph ADT and Basic Operations

Graph ADT implementation

• Graph ADT represents a collection of vertices (nodes) and edges (connections between vertices)
• Can be directed (edges have a specific direction) or undirected (edges have no specific direction)
  • Directed graphs (digraphs) have edges with a specific direction (one-way streets)
  • Undirected graphs have edges with no specific direction (two-way streets)
• Can be weighted (edges have associated weights) or unweighted (edges have no associated weights)
  • Weighted graphs have edges with associated numerical values (road networks with distances)
  • Unweighted graphs have edges without any associated values (social networks)
• Object-oriented implementation involves defining Vertex, Edge, and Graph classes
  • Vertex class represents each vertex in the graph
    • Contains data associated with the vertex (label, value, etc.)
    • May include methods for adding/removing edges connected to the vertex
  • Edge class represents each edge in the graph
    • Contains references to the vertices it connects (endpoints)
    • May include a weight value for weighted graphs (cost, distance, etc.)
  • Graph class manages the collection of vertices and edges
    • Contains methods for adding/removing vertices and edges
    • Provides methods for graph traversal (DFS, BFS) and other graph operations (shortest path, connectivity)

Vertex and edge manipulation

• Adding a vertex creates a new instance of the Vertex class and adds it to the graph's collection of vertices
  • Time complexity: O(1) as it involves a simple insertion operation
• Removing a vertex removes it from the graph's collection of vertices and all edges connected to it
  • Time complexity: O(E), where E is the number of edges in the graph, as it requires updating all connected edges
• Adding an edge creates a new instance of the Edge class, adds it to the graph's collection of edges, and updates the adjacency lists or matrices of the connected vertices
  • Time complexity: O(1) as it involves a simple insertion operation
• Removing an edge removes it from the graph's collection of edges and updates the adjacency lists or matrices of the connected vertices
  • Time complexity: O(1) as it involves a simple deletion operation

Graph traversal techniques

• Depth-first search (DFS) explores as far as possible along each branch before backtracking
  • Implemented using a stack data structure (recursion or explicit stack)
  • Time complexity: O(V + E), where V is the number of vertices and E is the number of edges
  • Space complexity: O(V) for the stack to keep track of visited vertices
  • Applications: finding connected components, topological sorting, solving mazes
• Breadth-first search (BFS) explores all neighboring vertices before moving to the next level
  • Implemented using a queue data structure
  • Time complexity: O(V + E), where V is the number of vertices and E is the number of edges
  • Space complexity: O(V) for the queue to keep track of visited vertices
  • Applications: shortest path algorithms (Dijkstra's algorithm), web crawlers

Complexity of graph operations

• Adjacency list representation
  • Space complexity: O(V + E) as it stores each vertex and edge separately
  • Adding/removing a vertex: O(1) as it involves a simple insertion/deletion operation
  • Adding/removing an edge: O(1) as it involves updating the adjacency lists of the connected vertices
  • DFS and BFS: O(V + E) time complexity as it visits each vertex and edge once
• Adjacency matrix representation
  • Space complexity: O(V^2) as it stores a matrix of size V x V
  • Adding/removing a vertex: O(V^2) due to matrix resizing and updating all entries
  • Adding/removing an edge: O(1) as it involves updating a single entry in the matrix
  • DFS and BFS: O(V^2) time complexity as it requires iterating through the entire matrix
• Factors affecting the choice of representation
  • Density of the graph (ratio of edges to vertices)
    • Adjacency list is more efficient for sparse graphs (few edges relative to vertices)
    • Adjacency matrix is more efficient for dense graphs (many edges relative to vertices)
  • Frequency of graph operations (additions, removals, traversals)
    • Adjacency list is more efficient for frequent vertex/edge additions and removals
    • Adjacency matrix is more efficient for frequent edge existence checks and updates
  • Space constraints of the system
    • Adjacency list requires less space for sparse graphs
    • Adjacency matrix requires more space but provides faster access for dense graphs