Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  • Types of Graphs
  • Operations of the Graphs in data structure
  1. Data Structure

Graphs

PreviousTreesNextHeap Sort

Last updated 1 year ago

A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More formally, a Graph is composed of a set of vertices (V) and a set of edges (E). The graph is denoted by G (E, V).

image

Types of Graphs

There are several types of graphs in data structures:

  1. Undirected Graphs: Edges have no direction, i.e., the edges do not have arrows indicating the direction of traversal.

  2. Directed Graphs: Edges have a direction, i.e., the edges have arrows indicating the direction of traversal.

  3. Weighted Graphs: Edges have weights or costs associated with them.

  4. Unweighted Graphs: Edges have no weights or costs associated with them.

  5. Complete Graphs: Each vertex is connected to every other vertex.

  6. Bipartite Graphs: The vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set.

  7. Trees: A connected graph with no cycles.

  8. Cycles: A graph with at least one cycle.

  9. Sparse Graphs: A graph with relatively few edges compared to the number of vertices.

  10. Dense Graphs: A graph with many edges compared to the number of vertices.

  11. Finite Graphs: A graph with a finite number of vertices and edges.

  12. Infinite Graphs: A graph with an infinite number of vertices and edges.

  13. Trivial Graph: A graph with only one vertex and no edges.

  14. Multi Graph: A graph which may have multiple edges (also called parallel edges), i.e., edges that have the same end nodes. Thus, two vertices may be connected by more than one edge.

  15. Null Graph: A graph is known as a null graph if there are no edges in the graph.

Operations of the Graphs in data structure

There are several operations that can be performed on graphs in data structures:

  • Add Vertex: This operation adds a vertex to the graph.

  • Add Edge: This operation adds an edge between two vertices in the graph.

  • Remove Vertex: This operation removes a vertex from the graph.

  • Remove Edge: This operation removes an edge between two vertices in the graph.

  • Query: This operation checks if there is an edge between two vertices.

  • Neighbors: This operation lists all vertices connected to a given vertex.

  • Search: This operation searches for an entity in the graph.

  • Traversal: This operation traverses all the nodes in the graph.

Complexity Table

Operation
Adjacency Matrix
Adjacency List

Access

O(1)

**O(

Search

**O(

V

Insertion

**O(

V

Deletion

**O(

V

image