Graph

 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:

    G = (V, E)

    where:

    • V is a set of vertices (nodes)

  • Simple Definition of Graph👉

    A graph is a collection of vertices (nodes) and edges that connect the vertices.

  • E is a set of edges connecting the vertices

  • 👉Types of Graph 👈

  • Graphs can be classified into different types based on their structure and properties:


    1. Undirected Graph
      A graph in which edges have no direction. The connection between vertices is bidirectional.
      Example: Friendship network.



    1. Directed Graph (Digraph)
      A graph in which edges have a direction, represented by arrows.
      Example: One-way roads, web page links.


    2. Weighted Graph
      A graph in which each edge is assigned a weight or cost.
      Example: Distance between cities.


    3. Unweighted Graph
      A graph in which edges do not have weights; all edges are treated equally.


    4. Simple Graph
      A graph with no self-loops and no multiple edges between the same pair of vertices.


    5. Multigraph
      A graph that allows multiple edges between the same pair of vertices.

    6. Complete Graph
      A graph in which every vertex is connected to every other vertex.


    7. Connected Graph
      A graph in which there is a path between every pair of vertices.


    8. Disconnected Graph
      A graph in which at least one vertex is not connected to others.



    👉 Types of Graph (Short ):-👇

  1. Undirected Graph – Edges have no direction.

  2. Directed Graph – Edges have direction.

  3. Weighted Graph – Edges have weights or costs.

  4. Unweighted Graph – Edges have no weights.

  5. Simple Graph – No loops or multiple edges.

  6. Complete Graph – Every vertex is connected to all others.

  7. Connected Graph – Path exists between every pair of vertices.

  8. Disconnected Graph – Some vertices are not connected.

  9. Cyclic Graph – Contains at least one cycle.


Example of Cyclic Graph


  1. Directed Acyclic Graph – Contains no cycles.

    Example of Directed Acyclic Graph 


   

Comments

Post a Comment

Popular posts from this blog

Representation of Graph Data Structure"😊

Image
      "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 alg...
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