Representation of Graph Data Structure"😊

     "Representation of Graph Data Structure"😊


A graph data structure represents relationships between entities. It consists of:

  • Vertices (Nodes): entities

  • Edges (Links): connections between entities

There are several common ways to represent a graph, each with trade-offs.

1. Adjacency Matrix

A 2D array V × V where V is the number of vertices.

Example



👉Graph with vertices A, B, C:

    A B C
A   0 1 1
B   1 0 0
C   1 0 0

  • 1 indicates an edge, 0 indicates no edge

  • For weighted graphs, store weights instead of 1

Properties

  • Space: O(V²)

  • Edge lookup: O(1)

  • Best for: Dense graphs

2. Adjacency List

Each vertex stores a list of adjacent vertices.

Example

Properties

  • Space: O(V + E)

  • Edge lookup: O(deg(V))

  • Best for: Sparse graphs

3. Edge List

Graph is represented as a list of edges.

Example

(A, B)
(A, C)
(B, A)
(C, A)

Properties

  • Space: O(E)

  • Edge lookup: O(E)

  • Best for: Simple algorithms like Kruskal’s

4. Incidence Matrix

A matrix with rows as vertices and columns as edges.

Example

Properties

  • Space: O(V × E)

  • Used in: Mathematical graph theory

Comparison Table

RepresentationSpaceEdge CheckBest Use Case
Adjacency MatrixO(V²)O(1)Dense graphs
Adjacency ListO(V + E) O(deg V)Sparse graphs
Edge ListO(E)O(E)MST, simple input
Incidence MatrixO(V × E)O(E)Theoretical graphs

👉Directed vs Undirected

  • Undirected graph: edges are bidirectional

  • Directed graph: edges have direction (u → v).


👍Representation of Graph Data Structure (Short)

A graph is represented using vertices (nodes) and edges (connections). Common representations are:

  1. Adjacency Matrix

    • Uses a 2D array

    • 1 means edge exists, 0 means no edge

    • Best for dense graphs

  2. Adjacency List

    • Each vertex stores a list of connected vertices

    • Saves memory

    • Best for sparse graphs

  3. Edge List

    • Graph stored as a list of (u, v) pairs

    • Simple and easy to use

    • Used in Kruskal’s algorithm

  4. Incidence Matrix

    • Rows = vertices, columns = edges

    • Mainly used in theory

Comments

Post a Comment

Popular posts from this blog

Graph

Image
 Graph   👉 Introduction to Graph👇 A graph is a non-linear data structure used to represent relationships between different objects. It consists of a set of vertices (nodes) and a set of edges that connect pairs of vertices. Graphs are widely used in computer science to model real-world problems such as computer networks, social networks, transportation systems, and web page links. Formally, a graph G is defined as G = (V, E) , where: V is a finite set of vertices (nodes) E is a set of edges that connect the vertices  Definition of Graph 😀 A graph is a non-linear data structure that consists of a finite set of vertices (nodes) and a set of edges that connect pairs of vertices. Formally, a graph is defined as:
Read more

Graph Traversal :-"BFS"

Image
👉BFS (Breadth-First Search) – Introduction Breadth-First Search (BFS) is a fundamental graph traversal algorithm used to visit all vertices of a graph in a breadth-wise (level-by-level) manner. Starting from a given source vertex, BFS explores all its adjacent vertices first before moving on to vertices at the next level. BFS uses a queue data structure to keep track of vertices to be visited and a visited array to avoid revisiting the same vertex. It is especially useful for finding the shortest path in an unweighted graph and for level-order traversal.   Key Characteristics of BFS: Traversal Type:  Level-by-level (or layer-by-layer). Data Structure Used:  Queue (First In, First Out — FIFO). Time Complexity:  O(V + E), where V is the number of vertices and E is the number of edges. Space Complexity:  O(V), as it stores vertices in the queue. Applicable To:  Both graphs and trees. How BFS Works BFS uses a  queue  to store nodes to be explo...
Read more