# What Is Graph and Its Types in Data Structure?

//

Larry Thompson

A graph is a non-linear data structure that represents a collection of interconnected nodes or vertices. It consists of a set of vertices and a set of edges that connect these vertices. Graphs are widely used in computer science and other fields to represent relationships between objects or entities.

## Types of Graphs:

### 1. Undirected Graph:

An undirected graph is a graph where the edges do not have any direction.

In other words, the relationship between two vertices is bidirectional. If there is an edge connecting vertex A to vertex B, then there is also an edge connecting vertex B to vertex A.

### 2. Directed Graph:

A directed graph, also known as a digraph, is a graph where the edges have a specific direction.

This means that the relationship between two vertices is unidirectional. If there is an edge connecting vertex A to vertex B, it does not imply that there is an edge connecting vertex B to vertex A.

### 3. Weighted Graph:

A weighted graph is a graph where each edge has an associated weight or cost. These weights can represent various properties such as distance, time, or cost between the connected vertices.

### 4. Unweighted Graph:

An unweighted graph is a graph where all edges have the same weight or do not have any associated weight at all.

## Graph Representation:

There are two common ways to represent graphs in computer science:

An adjacency matrix represents a graph as a two-dimensional array of size V x V, where V represents the number of vertices in the graph. Each cell in the matrix represents whether there exists an edge between two vertices.

Example:

```1  2  3
--------
1| 0  1  1
2| 1  0  0
3| 1  0  0
```

An adjacency list represents a graph as an array of linked lists or vectors. Each element of the array corresponds to a vertex, and the linked list/vector associated with each element stores its adjacent vertices.

Example:

```1: [2,3]
2: 
3: 
```

## Graph Operations:

Graphs support various operations, including: