Undirected Graphs Explained: Structures, Algorithms, and Use Cases

Undirected Graph is a fundamental non-linear data structure consisting of a set of vertices (nodes) connected by edges (links), where edges have no direction. In other words, an edge between vertex u and v allows traversal from u to v and vice versa—unlike directed graphs (digraphs), where edges have a one-way direction.

Undirected graphs model relationships where connections are mutual (e.g., friendships, roads between cities, network connections) and are the foundation for algorithms like BFS, DFS, and MST (Minimum Spanning Tree).

Core Concepts & Terminology

1. Key Definitions

Vertex (Node): A fundamental unit representing an entity (e.g., a city, a person, a router).
Edge: A connection between two vertices (e.g., a road between two cities, a friendship between two people).
Adjacent Vertices: Two vertices connected by an edge (e.g., u and v are adjacent if there is an edge (u, v)).
Degree of a Vertex: The number of edges connected to the vertex (e.g., a vertex with 3 edges has degree 3).
Path: A sequence of vertices where each consecutive pair is connected by an edge (e.g., u → a → b → v is a path from u to v).
Cycle: A path that starts and ends at the same vertex, with no repeated edges (e.g., u → a → b → u).
Connected Graph: A graph where there is a path between every pair of vertices (no isolated components).
Disconnected Graph: A graph with two or more isolated components (no path between vertices in different components).
Tree: A connected acyclic graph (no cycles) with exactly V-1 edges (V = number of vertices).

2. Graph Representation

Two common ways to represent undirected graphs:

A. Adjacency List (Most Common)

Uses a list (or dictionary) where each vertex maps to a list of its adjacent vertices.
Efficient for sparse graphs (few edges relative to vertices) — saves space and speeds up traversal.

B. Adjacency Matrix

Uses a V×V matrix where matrix[u][v] = 1 if there is an edge between u and v, and 0 otherwise.
Efficient for dense graphs (many edges) — allows O(1) edge existence checks.

Example Undirected Graph

plaintext

Vertices: {0, 1, 2, 3, 4}
Edges: {(0,1), (0,2), (1,3), (2,3), (3,4)}

Adjacency List Representation:
0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2, 4]
4: [3]

Adjacency Matrix Representation (5×5):
   0 1 2 3 4
0  0 1 1 0 0
1  1 0 0 1 0
2  1 0 0 1 0
3  0 1 1 0 1
4  0 0 0 1 0

Undirected Graph Implementation (Python)

We’ll implement an undirected graph using an adjacency list (dictionary-based for flexibility with numeric/string vertices) with core operations: adding vertices/edges, traversal (BFS/DFS), cycle detection, and connected components.

Full Implementation

python

运行

from collections import deque

class UndirectedGraph:
    def __init__(self):
        self.adj_list = {}  # Key: vertex, Value: list of adjacent vertices
    
    # -------------------------- Add Operations --------------------------
    def add_vertex(self, vertex):
        """Add a vertex to the graph. Return False if vertex already exists."""
        if vertex not in self.adj_list:
            self.adj_list[vertex] = []
            return True
        return False
    
    def add_edge(self, v1, v2):
        """Add an undirected edge between v1 and v2. Return False if vertices don't exist."""
        # Check if both vertices exist
        if v1 not in self.adj_list or v2 not in self.adj_list:
            return False
        # Add v2 to v1's adjacency list (if not already present)
        if v2 not in self.adj_list[v1]:
            self.adj_list[v1].append(v2)
        # Add v1 to v2's adjacency list (undirected edge)
        if v1 not in self.adj_list[v2]:
            self.adj_list[v2].append(v1)
        return True
    
    # -------------------------- Remove Operations --------------------------
    def remove_edge(self, v1, v2):
        """Remove the undirected edge between v1 and v2. Return False if edge doesn't exist."""
        if v1 not in self.adj_list or v2 not in self.adj_list:
            return False
        # Remove v2 from v1's adjacency list
        try:
            self.adj_list[v1].remove(v2)
        except ValueError:
            return False  # Edge doesn't exist
        # Remove v1 from v2's adjacency list
        try:
            self.adj_list[v2].remove(v1)
        except ValueError:
            return False
        return True
    
    def remove_vertex(self, vertex):
        """Remove a vertex and all its edges. Return False if vertex doesn't exist."""
        if vertex not in self.adj_list:
            return False
        # Remove all edges connected to the vertex
        for adjacent_vertex in self.adj_list[vertex]:
            self.adj_list[adjacent_vertex].remove(vertex)
        # Remove the vertex from the adjacency list
        del self.adj_list[vertex]
        return True
    
    # -------------------------- Traversal Operations --------------------------
    def bfs(self, start_vertex):
        """Breadth-First Search (BFS) — returns list of vertices visited in BFS order."""
        if start_vertex not in self.adj_list:
            return []
        
        visited = set()
        queue = deque([start_vertex])
        visited.add(start_vertex)
        result = []
        
        while queue:
            current_vertex = queue.popleft()
            result.append(current_vertex)
            # Add all unvisited adjacent vertices to the queue
            for adjacent_vertex in self.adj_list[current_vertex]:
                if adjacent_vertex not in visited:
                    visited.add(adjacent_vertex)
                    queue.append(adjacent_vertex)
        
        return result
    
    def dfs_recursive(self, start_vertex):
        """Depth-First Search (DFS) — recursive implementation."""
        if start_vertex not in self.adj_list:
            return []
        
        visited = set()
        result = []
        
        def dfs_helper(vertex):
            visited.add(vertex)
            result.append(vertex)
            # Recursively visit all unvisited adjacent vertices
            for adjacent_vertex in self.adj_list[vertex]:
                if adjacent_vertex not in visited:
                    dfs_helper(adjacent_vertex)
        
        dfs_helper(start_vertex)
        return result
    
    def dfs_iterative(self, start_vertex):
        """Depth-First Search (DFS) — iterative implementation (avoids stack overflow for large graphs)."""
        if start_vertex not in self.adj_list:
            return []
        
        visited = set()
        stack = [start_vertex]
        visited.add(start_vertex)
        result = []
        
        while stack:
            current_vertex = stack.pop()  # LIFO: pop from end of stack
            result.append(current_vertex)
            # Add unvisited adjacent vertices to the stack (reverse to maintain order)
            for adjacent_vertex in reversed(self.adj_list[current_vertex]):
                if adjacent_vertex not in visited:
                    visited.add(adjacent_vertex)
                    stack.append(adjacent_vertex)
        
        return result
    
    # -------------------------- Utility Operations --------------------------
    def get_vertices(self):
        """Return list of all vertices in the graph."""
        return list(self.adj_list.keys())
    
    def get_edges(self):
        """Return list of all edges (as tuples, sorted to avoid duplicates)."""
        edges = set()
        for vertex in self.adj_list:
            for adjacent_vertex in self.adj_list[vertex]:
                # Store edges as sorted tuples (e.g., (0,1) instead of (1,0)) to avoid duplicates
                edge = tuple(sorted((vertex, adjacent_vertex)))
                edges.add(edge)
        return list(edges)
    
    def is_connected(self):
        """Check if the graph is connected (all vertices are reachable from any start vertex)."""
        if not self.adj_list:
            return True  # Empty graph is trivially connected
        
        start_vertex = next(iter(self.adj_list.keys()))
        visited = set(self.bfs(start_vertex))
        return len(visited) == len(self.adj_list)
    
    def has_cycle(self):
        """Check if the undirected graph contains a cycle (using DFS)."""
        visited = set()
        
        def cycle_helper(vertex, parent):
            visited.add(vertex)
            for adjacent_vertex in self.adj_list[vertex]:
                if adjacent_vertex not in visited:
                    # Recursively check adjacent vertices
                    if cycle_helper(adjacent_vertex, vertex):
                        return True
                elif adjacent_vertex != parent:
                    # Found an adjacent vertex that is visited and not the parent → cycle exists
                    return True
            return False
        
        # Check all components (in case of disconnected graph)
        for vertex in self.adj_list:
            if vertex not in visited:
                if cycle_helper(vertex, None):
                    return True
        return False
    
    def get_connected_components(self):
        """Return list of connected components (each component is a list of vertices)."""
        visited = set()
        components = []
        
        for vertex in self.adj_list:
            if vertex not in visited:
                # BFS to find all vertices in the component
                component = self.bfs(vertex)
                components.append(component)
                visited.update(component)
        
        return components

# Test the UndirectedGraph implementation
if __name__ == "__main__":
    # Initialize graph
    g = UndirectedGraph()
    
    # Add vertices
    g.add_vertex(0)
    g.add_vertex(1)
    g.add_vertex(2)
    g.add_vertex(3)
    g.add_vertex(4)
    g.add_vertex(5)
    print("Vertices:", g.get_vertices())  # Output: [0, 1, 2, 3, 4, 5]
    
    # Add edges
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 3)
    g.add_edge(2, 3)
    g.add_edge(3, 4)
    g.add_edge(5, 5)  # Self-loop (allowed in some graphs; note: degree of 5 increases by 2)
    print("Edges:", g.get_edges())  # Output: [(0,1), (0,2), (1,3), (2,3), (3,4), (5,5)]
    
    # Traversals
    print("\n=== Traversals (Start Vertex: 0) ===")
    print("BFS:", g.bfs(0))  # Output: [0, 1, 2, 3, 4]
    print("DFS Recursive:", g.dfs_recursive(0))  # Output: [0, 1, 3, 2, 4] (order may vary)
    print("DFS Iterative:", g.dfs_iterative(0))  # Output: [0, 2, 3, 4, 1] (order may vary)
    
    # Cycle Detection
    print("\nHas Cycle?", g.has_cycle())  # Output: True (cycle: 0→1→3→2→0)
    
    # Connected Components
    print("Connected Components:", g.get_connected_components())  # Output: [[0,1,2,3,4], [5]]
    
    # Remove Edge
    g.remove_edge(1, 3)
    print("\nEdges after removing (1,3):", g.get_edges())  # Output: [(0,1), (0,2), (2,3), (3,4), (5,5)]
    
    # Remove Vertex
    g.remove_vertex(3)
    print("Vertices after removing 3:", g.get_vertices())  # Output: [0,1,2,4,5]
    print("Edges after removing 3:", g.get_edges())  # Output: [(0,1), (0,2), (5,5)]

Time and Space Complexity

Adjacency List vs. Adjacency Matrix

Operation	Adjacency List	Adjacency Matrix	Explanation
Add Vertex	O(1)	O(V²)	Adjacency list: Add key to dictionary. Matrix: Resize and copy V×V matrix.
Add Edge	O(1)	O(1)	List: Append to adjacency lists. Matrix: Set `matrix[u][v] = 1`.
Remove Edge	O(D)	O(1)	List: Search adjacency list (D = degree of vertex). Matrix: Set `matrix[u][v] = 0`.
Remove Vertex	O(V)	O(V²)	List: Remove vertex and update all adjacency lists. Matrix: Resize matrix.
BFS/DFS	O(V + E)	O(V²)	List: Visit all vertices (V) and edges (E). Matrix: Check all V² entries.
Cycle Detection	O(V + E)	O(V²)	Uses BFS/DFS under the hood.
Edge Existence Check	O(D)	O(1)	List: Search adjacency list. Matrix: Direct lookup.

Space Complexity	Adjacency List	Adjacency Matrix	Explanation
Overall	O(V + E)	O(V²)	List: Stores vertices and edges. Matrix: Stores V×V entries (even if sparse).

Key Takeaway

Use Adjacency List for: Sparse graphs (E ≈ V), frequent traversals (BFS/DFS), or dynamic graphs (adding/removing vertices).
Use Adjacency Matrix for: Dense graphs (E ≈ V²), frequent edge existence checks, or small graphs (V ≤ 1000).

Pros and Cons of Undirected Graphs

Pros

Natural Relationship Modeling: Perfect for mutual connections (friendships, roads, network links) where direction doesn’t matter.
Efficient Traversals: BFS/DFS run in O(V + E) time with adjacency lists—optimal for most real-world graphs (sparse).
Flexible Representations: Adjacency lists handle dynamic graphs (add/remove vertices/edges) efficiently.
Well-Supported Algorithms: Rich ecosystem of algorithms (MST, shortest path, cycle detection) tailored for undirected graphs.

Cons

No Directional Information: Cannot model one-way relationships (use directed graphs for that).
Self-Loops and Multiple Edges: Require special handling (e.g., self-loops contribute 2 to a vertex’s degree).
Sparse vs. Dense Tradeoffs: Adjacency lists are inefficient for dense graphs; adjacency matrices waste space for sparse graphs.

Real-World Applications of Undirected Graphs

Social Networks: Model users (vertices) and friendships (edges) — used for friend recommendations (BFS/DFS to find mutual friends).
Transportation Systems: Model cities (vertices) and roads/highways (edges) — used for route planning (shortest path algorithms like Dijkstra’s).
Computer Networks: Model routers/switches (vertices) and network cables (edges) — used for network topology analysis and fault detection.
Biology: Model molecules (vertices) and chemical bonds (edges) — used for drug discovery and protein structure analysis.
Web Graphs: Model web pages (vertices) and hyperlinks (edges) — used for search engine ranking (PageRank, though PageRank uses directed graphs).
Game Development: Model game maps (vertices = locations, edges = paths) — used for AI pathfinding (BFS/DFS to find shortest paths).
Cluster Analysis: Model data points (vertices) and similarity (edges) — used for grouping similar data (connected components).