Graphs - Data Structures

A graph is a non-linear data structure consisting of nodes (vertices) and edges that connect these vertices.

Introduction

Graphs are used to represent relationships between objects. They are fundamental in modeling networks, social connections, and various real-world problems.

Graph Terminology

Vertex (Node): A point in the graph
Edge: A connection between two vertices
Path: Sequence of vertices connected by edges
Cycle: A path that starts and ends at the same vertex
Degree: Number of edges connected to a vertex

Types of Graphs

1. Directed Graph (Digraph)

Edges have direction. If there's an edge from A to B, it doesn't mean there's an edge from B to A.

2. Undirected Graph

Edges have no direction. If A is connected to B, then B is connected to A.

3. Weighted Graph

Edges have weights or costs associated with them.

4. Unweighted Graph

All edges have equal weight (usually 1).

Graph Representation

1. Adjacency Matrix

A 2D array where matrix[i][j] = 1 if there's an edge from i to j.

Space Complexity: O(V²)

2. Adjacency List

An array of lists where each list represents neighbors of a vertex.

Space Complexity: O(V + E)

Graph Traversal Algorithms

Depth-First Search (DFS)

def dfs(graph, start, visited):
    visited.add(start)
    print(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Time Complexity: O(V + E)

Breadth-First Search (BFS)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)