Graph Representations and Traversal Algorithms

Sparse vs Dense Graph Representations

• Graph Representation Preferences:
  • For sparse graphs: Use linked list representation.
  • Sparse graphs have fewer connections, hence a linked list uses less memory and avoids storing many zero or dummy values.
  • For dense graphs: Use adjacency matrix representation.
  • Dense graphs have more connections, and an adjacency matrix efficiently stores the presence of edges.

Adjacency Matrix and Linked List Representation

• Adjacency Matrix:
  • Two-dimensional array where cell values indicate presence of an edge between nodes.
  • Example:
  • An edge between node 1 and node 2 is represented by a value of 1 at (1, 2)
  • No edge is represented by a value of 0.
  • For undirected graphs, the matrix is symmetrical.
• Linked List Representation:
  • Nodes are stored in a linked list with pointers to other nodes, accommodating edges in the structure.
  • Each node can have a list of connections (edges) to other nodes.
  • Suitable for both directed and undirected graphs.

Weights in Graphs

• In weighted graphs, edges can have values that represent weights (e.g., costs, distances).
• Adjacency matrices must accommodate weights instead of just presence.
• Special symbols (such as infinity) may represent the absence of an edge to avoid confusion with a weight of zero.

Graph Algorithms and Traversal

• Graph Traversals are fundamental for various graph algorithms. The purpose is to visit every node and perform operations like printing data.
• Common algorithms include:
  • Depth First Search (DFS):
  • Explores as far as possible along each branch before backtracking.
  • Can be implemented using a stack or recursion.
  • Breadth First Search (BFS):
  • Explores all neighbors at the present depth before moving on to nodes at the next depth level.
  • Typically implemented using a queue.

Depth First Search (DFS)

• Process:
  • Start from a node, mark it visited, and explore deeper towards unvisited neighbors.
  • Uses a stack to keep track of the path back to previous nodes when dead ends are reached.
• Traversal Example:
  • Starting at node A: visit A, then go to neighbors (B, C), mark them.
  • After hitting a dead end, backtrack to the most recent node with unexplored neighbors.

Breadth First Search (BFS)

• Process:
  • Start from a node, visit it, then visit all its immediate neighbors before moving deeper in the graph.
  • Uses a queue to maintain the order of node visits.
• Traversal Example:
  • From node A: enqueue immediate neighbors (B, C), visit them, and continue to explore their neighbors in the same manner.

Complexity of Graph Traversal Algorithms

• Time Complexity:
  • Both DFS and BFS have a time complexity of $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges.

Importance of Marking in Traversals

• Marking Nodes: Distinguishes between nodes that have been encountered and those that have been processed (visited).
• This prevents revisiting nodes and optimizes traversal algorithms, ensuring efficient exploration of the graph.

Summary of Graph Representation and Traversal

• Choosing the right representation for a graph (linked lists for sparse and adjacency matrix for dense) is key to efficiency.
• Mastering traversal algorithms (DFS and BFS) is essential, as they form the basis for solving complex graph-related problems effectively.