DS – Introduction to Graphs


  • Graph is a non linear data structure.
  • graph is a collection of nodes(called vertices), and the connections between them, called edges.
  • Graph is either Undirected or directed.
  • When the edges in a graph have a direction, the graph is called a directed graph.
  • The edges are called directed edges or arcs.
  • Graphs are used to solve many real-life problems.
  • Graphs are used to represent networks.
  • The networks may include paths in a city or telephone network or circuit network.
  • Graphs are also used in social networks like linkedIn, Facebook. For example, in Facebook, each person is represented with a vertex (or node).
  • Each node is a structure and contains information like person id, name, gender, locale etc.
  • All of facebook is then a collection of these nodes and edges. This is because facebook uses a graph data structure to store its data.

Graph:  A graph is a data structure G = {V, E} that consists of

  • A collection of vertices V
  • A collection of edges E, represented as ordered pairs of vertices (u, v)

Graph Terminology

  1. Adjacency: A vertex is said to be adjacent to another vertex if there is an edge connecting them. Vertices 2 and 3 are not adjacent because there is no edge between them.
  2. Path: A sequence of edges that allows you to go from vertex A to vertex B is called a path. 

Graph representation as matrix called Adjacency matrix:

  • An adjacency matrix is a 2D array of V x V vertices. Each row and column represents a vertex.
  • If the value of any element a[i][j] is 1, it represents that there is an edge connecting vertex i and vertex j.

Traversal: We use weight graphs and directions to find the BFS, DFS.

Applications: Using the weighted graph we can understand “Shortest path” problem which is the application of Graph.

Scroll to Top