Graphs

Understanding graphs as a data structure.

What are Graphs?

A graph is a non-linear data structure consisting of vertices (nodes) and edges that connect these vertices. Unlike trees, which have a strict hierarchical structure, graphs can represent more complex relationships where connections can form cycles and nodes can have multiple paths between them.

Types of Graphs

  1. Directed vs Undirected

    • Directed (Digraph): Edges have a direction (one-way connection)
    • Undirected: Edges have no direction (two-way connection)

  2. Weighted vs Unweighted

    • Weighted: Edges have associated costs or weights
    • Unweighted: All edges have equal importance

  3. Special Types

    • Complete Graph: Every vertex is connected to every other vertex
    • Bipartite Graph: Vertices can be divided into two sets with edges only between sets
    • Tree: Connected graph with no cycles
    • DAG (Directed Acyclic Graph): Directed graph with no cycles

Graph Representations

  1. Adjacency Matrix

    • 2D array where matrix[i][j] represents edge between vertices i and j
    • Space Complexity: O(V²)
    • Good for dense graphs

  2. Adjacency List

    • Array/List of lists where each index stores connected vertices
    • Space Complexity: O(V + E)
    • Better for sparse graphs

Common Graph Operations

  • Basic Operations

    • Add vertex: O(1)
    • Add edge: O(1) for adjacency list, O(1) for matrix
    • Remove vertex: O(V + E) for list, O(V²) for matrix
    • Remove edge: O(E) for list, O(1) for matrix
    • Check if edge exists: O(V) for list, O(1) for matrix

  • Traversal Operations

    • Depth First Search (DFS): O(V + E)
    • Breadth First Search (BFS): O(V + E)

Code Examples

Here's how you implement a basic graph in different languages:

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        # Add edge for undirected graph
        self.graph[u].append(v)
        self.graph[v].append(u)

    def bfs(self, start):
        visited = set()
        queue = deque([start])
        visited.add(start)

        while queue:
            vertex = queue.popleft()
            print(vertex, end=" ")

            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

# Create the graph
g = Graph()

# Add edges
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)

print("BFS starting from vertex 0: ", end="")
g.bfs(0)  # Perform BFS starting from vertex 0

Common Graph Algorithms

  • Depth-First Search (DFS)

  • Breadth-First Search (BFS)

Problems to Solve

Important Problems on Graphs

Resources