## Introduction

Everyone works hard to crack their dream company, prepare Data Structures and Algorithms, Computer Science Fundamentals, and solve interview problems.

**Source: giphy**

Graph is one of the important topics in Data Structures one should be well versed in.

Questions related to Graphs are asked in all the major product-based companies. Also, Graphs are used everywhere, and directed graphs are used in Google's page ranking algorithms. Social networking sites like Facebook and Linkedin use graphs to represent different users as vertices and edges to represent the connections between them. Therefore it's quite important to have a solid understanding of Graphs.

The first step to study Graphs is to know the basic terminologies related to graphs. You may refer to this article for more information. After knowing the basic terminologies, it’s time to implement your Graph. This article will discuss the **implementation of graphs in **__Python__. Before moving on to the implementation, it’s necessary to understand Graphs quickly.

Also see, __Merge Sort Python__

## A Brief Introduction to Graphs

A **graph** is a non-linear data structure that consists of nodes and edges. Formally, a graph can be defined as an ordered set G(V, E) where V represents the vertices and E represents the set of edges that are used to connect these vertices. (See Graph Representation)

In the above graph, the set of nodes are {1, 2, 3, 4, 5, 6} and the set of edges are {1-2, 1-5, 5-2, 2-3, 3-4, 4-5, 4-6}.

**Graphs may be directed or undirected graphs**. A directed graph is a set of vertices/nodes connected by edges, with each node having a direction associated with it. Edges are represented by arrows pointing to the direction in which the graph can be traversed. If there is an edge between vertex 0 and 1 with an arrow pointing towards 1, then the graph can be traversed (also see Traversal) from 0 to 1 and not from 1 to 0. In contrast, an undirected graph can be traversed in either direction. The edges are bidirectional. If there is an edge between vertex 0 and 1, then the graph can be traversed from 0 to 1 and from 1 to 0.

Some graphs have weights associated with edges between two vertices. These graphs are called **Weighted Graphs**.

Implementation of the Graph can be done by using either an **adjacency list** or an **adjacency matrix**. Each of the two representations has its pros and cons; the choice of a particular graph representation depends on the requirements.

**Also read: **__Application of graph data structure__