Graph Data Structure
A graph data structure consists of nodes (vertices) that hold data and are connected by edges (relationships).
Example: Facebook
On Facebook, everything is a node: User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note, etc. Relationships such as posting a photo, joining a group, or liking a page create edges between these nodes.
Explanation Using Facebook
- Nodes: Represent users, groups, pages, events, etc.
- Edges: Represent relationships like friendships, group memberships, page likes.
Facebook is essentially a large graph, composed of these nodes and edges, utilizing a graph data structure to store and manage its data.
Graph Definition
A graph is defined as ( G = (V, E) ) where:
- V: A collection of vertices (nodes).
- E: A collection of edges, represented as ordered pairs of vertices (u, v).
Example Graph
- Vertices: ( V = {0, 1, 2, 3} )
- Edges: ( E = {(0,1), (0,2), (0,3), (1,2)} )
- Graph: ( G = {V, E} )
Graph Terminology
- Adjacency: Two vertices are adjacent if there is an edge between them. For example, vertices 2 and 3 are not adjacent because there is no edge between them.
- Path: A sequence of edges that allows travel from one vertex to another. For example, 0-1, 1-2, and 0-2 are paths from vertex 0 to vertex 2.
- Directed Graph: A graph where an edge (u, v) does not necessarily mean there is an edge (v, u). Edges are shown with arrows indicating direction.
Graph Representation
Graphs can be represented in two common ways:
1. Adjacency Matrix
An adjacency matrix is a 2D array of ( V \times V ) vertices. Each row and column represent a vertex. If element ( a[i][j] ) is 1, there is an edge between vertices ( i ) and ( j ).
Example Adjacency Matrix for the Given Graph:
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 2 | 1 | 1 | 0 | 0 |
| 3 | 1 | 0 | 0 | 0 |
Since it is an undirected graph, for edge (0,2), we also mark edge (2,0), making the matrix symmetric about the diagonal.
Advantages: Fast edge lookup.
Disadvantages: Requires more space (( V \times V )).
2. Adjacency List
An adjacency list represents a graph as an array of linked lists. The index of the array represents a vertex, and each element in its linked list represents the vertices connected by edges.
Example Adjacency List for the Given Graph:
- 0: 1 -> 2 -> 3
- 1: 0 -> 2
- 2: 0 -> 1
- 3: 0
Advantages: Efficient storage.
Disadvantages: Slower edge lookup compared to adjacency matrix.
Graph Operations
Common operations on graphs include:
- Check Presence: Determine if a vertex or edge is present in the graph.
- Graph Traversal: Explore the vertices and edges of the graph (e.g., Depth-First Search, Breadth-First Search).
- Add Elements: Insert new vertices or edges.
- Find Path: Determine a path from one vertex to another.
Read More …
How to teach Math With Coding – https://kamleshsingad.com/how-to-teach-math-with-coding/
Introduction to Trees: Data Structure and Algorithm Tutorial – https://kamleshsingad.com/introduction-to-trees-data-structure-and-algorithm-tutorial/
What is a Stack? – https://kamleshsingad.com/what-is-a-stack/
