Graphs in Data Structures

Graph Overview

• A graph is a non-linear data structure comprising nodes (or vertices) and edges.
• Represents relationships between entities.
• Important distinction: Objects and Entities refer to elements in the graph, not programming class instances.

Key Components

• Nodes (Vertices): Represent the entities or objects.
• Edges: Represent the relationships between nodes (can be directed or undirected).

Types of Graphs

Simple Examples

• Directed Graph: Edges have specific directions.
  • Example: Flight routes where direction is important (e.g., New York to Atlanta).
• Undirected Graph: Edges do not have specific directions.
  • Example: Facebook friendships (mutual relationships).

Complex Examples

• Weighting: Graphs can be weighted or unweighted based on whether edges have associated numerical values.
• Acyclic vs. Cyclic Graphs:
  • Cyclic Graph: Contains at least one cycle (path that starts and ends at the same node).
  • Acyclic Graph: Contains no cycles.

Differences Between Trees and Graphs

• Trees do not have cycles; graphs may.
• In trees, all nodes are connected; this is not always true for graphs.
• Edges in trees are typically undirected, whereas graphs can have directed edges.
• Applications vary; trees often represent hierarchical structures (e.g., file systems), while graphs are used for networks (e.g., social networking).

Graph Representation Methods

1. Adjacency Matrix

• Uses a 2-D array of size $n \times n$, where $n$ is the number of nodes.
• Each cell indicates whether there is an edge between two nodes, e.g., arr(u,v) = 1 for an existing edge.
• Space complexity: $O(n^2)$.

2. Adjacency List

• Each node has a list of its neighbors.
• More memory efficient for sparse graphs.
• Space complexity: $O(V + E)$, where $V$ is the number of nodes and $E$ is the number of edges.

Graph Class Implementation Examples:

• Adjacency Matrix:

class Graph:
    def __init__(self, n):
        self.nodes = n  # create the adjacency matrix 
        self.adj = [[0] * n for _ in range(n)]
    def add_edge(self, u, v):
        self.adj[u][v] = 1
    def print_adj_matrix(self):
        for row in self.adj:
            print(row)

• Adjacency List:

class Graph:
    def __init__(self):
        self.adj_list = {}
    def add_edge(self, u, v):
        if u in self.adj_list:
            self.adj_list[u].append(v)
        else:
            self.adj_list[u] = [v]
    def print_adj_list(self):
        for key in self.adj_list:
            print('Node:', key, 'Neighbors:', self.adj_list[key])

Graph Traversal Methods

Breadth First Search (BFS)

• Explores node neighbors level-by-level using a queue.
• Starting from a source node, visits all its neighbors before moving to the next level.

Depth First Search (DFS)

• Explores as far as possible along each branch before backtracking using a stack.
• Starting from a source node, it goes deep into the graph before visiting siblings.

Illustrative Example

• BFS path from node 0: 0 > 1 > 2 > 3 > 4 > 5 > 6
• DFS path from node 0: 0 > 1 > 3 > 5 > 6 > 2 > 4