Graphs in Data Structures
A graph is a non-linear data structure consisting of vertices (nodes) and edges (connections) between them. Graphs are widely used to model networks, relationships, and paths in real-world problems.
What is a Graph?
A graph G consists of:
- Vertices (V) – The nodes
- Edges (E) – Connections between nodes
Graphs can be directed (edges have direction) or undirected (edges have no direction).
Types of Graphs
1. Directed Graph (Digraph)
- Edges have a specific direction
- Example: Twitter follower network
2. Undirected Graph
- Edges have no direction
- Example: Facebook friend network
3. Weighted Graph
- Edges carry weights (cost, distance)
- Example: Road networks
4. Unweighted Graph
- Edges have no weights
- Example: Simple social connections
5. Cyclic Graph
- Contains a cycle (loop)
- Example: Road map with loops
6. Acyclic Graph
- No cycles
- Example: Hierarchical organization chart
Graph Representation
1. Adjacency Matrix
- 2D array to represent edges
- Fast lookup, but uses more memory
2. Adjacency List
- Array of lists storing connected vertices
- Memory efficient, suitable for sparse graphs
Basic Operations on Graphs
- Traversal: Visit all vertices
- BFS (Breadth-First Search)
- DFS (Depth-First Search)
- Adding vertices/edges
- Deleting vertices/edges
- Finding paths and cycles
Applications of Graphs
- Social networks (friend connections)
- Routing and navigation (Google Maps)
- Network topology (internet)
- Task scheduling
- Recommendation systems
Advantages of Graphs
- Models real-world networks
- Flexible and dynamic
- Supports efficient traversal and search
- Forms the basis for advanced algorithms (Dijkstra, Prim, Kruskal)
Disadvantages of Graphs
- Complex implementation
- High memory usage for dense graphs
- Traversal can be time-consuming for large graphs
Graph vs Tree
| Graph | Tree |
|---|---|
| Can have cycles | No cycles |
| Can be directed or undirected | Always hierarchical |
| Multiple paths between nodes | Only one path between nodes |
| General-purpose structure | Specialized for hierarchy |
Real-World Example of Graphs
- Airline flight networks
- Road and railway systems
- Computer networks
- Social media platforms
- Project task dependencies
Conclusion
Graphs are a powerful and versatile non-linear data structure used to model complex relationships and networks. Understanding graphs and their traversal methods is essential for solving real-world problems in networking, social media, and algorithms.