Graph Data Structure: Types, Uses, Examples, Algorithms

Introduction

• Graph Data Structure: A tool to represent relationships and connections between objects.
• Importance: Used in social networks, computer networks, navigation systems, and recommendation engines.

What is Graph Data Structure?

• Graph: Shows connections (like a map of roads connecting cities).
  • Nodes (Vertices): Represent objects (e.g., people in a social network).
  • Edges: Represent connections (e.g., friendships).

Types of Graph Data Structure With Examples

1. Directed Graph

   • Edges have a direction.
   • Example: Twitter network (Alice follows Bob).

2. Undirected Graph

   • Edges have no direction.
   • Example: Facebook friendship (Alice and Bob are mutual friends).

3. Weighted Graph

   • Edges have weights or costs.
   • Example: Road map with distances as weights.

4. Unweighted Graph

   • All edges have the same weight.
   • Example: Simple social network.

5. Cyclic Graph

   • Contains at least one cycle.
   • Example: Routes forming a loop between cities.

6. Acyclic Graph

   • No cycles present.
   • Example: Family tree.

7. Connected Graph

   • Path exists between every pair of nodes.
   • Example: Network where computers can communicate.

8. Disconnected Graph

   • At least one pair of nodes with no path.
   • Example: Isolated groups in a network.

9. Bipartite Graph

   • Nodes divided into two sets with no internal connections.
   • Example: Students and courses graph.

10. Complete Graph

    • Edge between every pair of nodes.
    • Example: Everyone is friends with everyone in a small network.

Graph Data Structure Terminology

• Vertex (Node): Object or point.
• Edge (Link): Connection between two vertices.
• Degree, In-Degree, Out-Degree: Number of connections a node has.
• Path and Cycle: Sequence of vertices and a path that starts and ends at the same vertex.
• Adjacency: Direct connection between two vertices.

Representations of Graph Data Structure

1. Adjacency Matrix: 2D array indicating edge existence.
2. Adjacency List: Array of lists representing node connections.

Graph Traversal Algorithms

1. Depth-First Search (DFS)

   • Explore each branch before backtracking.
   • Uses a stack (explicitly or recursively).

2. Breadth-First Search (BFS)

   • Explore nodes level by level.
   • Uses a queue.

Shortest Path Algorithms

1. Dijkstra's Algorithm: Finds shortest paths in graphs with non-negative weights.
2. Bellman-Ford Algorithm: Handles graphs with negative weights, detects negative cycles.
3. Floyd-Warshall Algorithm: Computes shortest paths between all pairs of nodes.

Minimum Spanning Tree Algorithms

1. Kruskal's Algorithm
   • Sort edges and avoid cycles to find MST.
2. Prim's Algorithm
   • Start from a node, add edges incrementally to form MST.

Uses of Graph Data Structure (Applications)

• Social Networks: Facebook, LinkedIn.
• Computer Networks: Internet routers, switches.
• Web Page Ranking: Google PageRank.
• Transportation: GPS navigation.
• Scheduling: Task execution order.
• Biology: Protein interactions.
• Game Development: Pathfinding in AI.
• Electrical Circuits: Circuit design.

Difference Between Tree and Graph Data Structure

• Tree: Hierarchical, single path, no cycles.
• Graph: Network-like, multiple paths, may contain cycles.

Graph Data Structure Implementation

• C, C++, Java, Python: Code snippets for graph implementation.

FAQs About Graph Data Structure

• Adjacency Matrix vs. List vs. Edge List: Different ways to represent graphs.
• Path and Cycle: Definitions and differences.
• Connected Graph: Every pair of vertices has a path.
• Minimum Spanning Tree: Connects all vertices with minimum edge weight.
• DFS: Depth-First Search explained.