# DS – Introduction to Graphs

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