# Data Structures - Graph Data structure

Graph is:

- a collection of nodes called vertices and
- a collection of line segments connecting pairs of vertices. In short, Line segments are called lines or edges.

Graph is represented by two sets:

- a set of vertices V
- a set of edges E which link the vertices

G = (V, E)

Each edge is a pair of vertices (v, w), where v,w ∈ V.

Edges are also referred to as a arcs.

## Graph Applications

- Graphs are used to represent real life applications.
- Graph can be used to solve complex problems. For example: for designing and routing airline, to route messages over a computer network from one node to another and so on.

## Graph - How it differs from Tree

- It is a non-linear data structure. It is differ from tree data structure.
- In graph, each node may have multiple predecessors as well as multiple successors where as in tree, each node has a multiple successors but just one predecessor.

## Graph Properties

#### Adjacent Vertices(or) Neighbors

If there is an edge between two vertices, then these two vertices are said to be adjacent vetices. For example, from the above graph (Figure 2) **A** and **B** are adjacent vertices, but **A** and **D are not**.

#### Path

It is the sequence of vertices in which each vertex is adjacent to next one. For example, let us take the above graph (Figure 2) **A, B, C, E** is one path and **A, B, D, E** is another path.

#### Cycle

It is a path consisting of, at least 3 vertices that starts and ends with the same vertex.

#### Loop

It is a special case of cycle, in which a single arc begins and ends with same vertex.

#### Connected

If there is a path between two vertices, then we say that two vertices are connected

## Graph Variants

## Based on Directed or Undirected

### Directed Graph (or) Digraph

It is graph in which each edge has a direction to its successor.

### Undirected Graph

It is a graph in which there is no direction on the edges. The flow between two vertices can go in either direction.

## Based on Weighted or Unweighted

### Weighted Graph

If the graph has a some cost or weight on the edge, then we say that graph is said to be a weighted graph. Weight can be applied in both Directed and Undirected graph.

### Unweighted Graph

If there is no cost or weight on the edge, then we say that graph is an Unweighted Graph. For example, Figure 2 is the Unweighted Undirected graph

## Based on How Connected the Graph is

### Strongly Connected Graph

If there is a path from each vertex to every other vertex in the directed graph, then only we say that directed graph is said to be Strongly connected graph.

### Weakly Connected Graph

If there are at least two vertices that are not connected, then we say that directed graph is said to be weakly connected graph.

### Disjoint Graph

The graph is a disjoint, if it is not connected.

### Complete Graph

If there is an edge between every pair of vertices, then we say that graph is said to be complete graph.

## Acyclic Graph

A graph is acyclic if it has no cycles.

### Directed Acyclic Graph

A directed acyclic graph is directed graph without any directed cycles. Referred by its short name **DAG**

### PolyTree

PolyTree is a directed graph without any undirected cycles

### Forest

Forest is a undirected graph without any cycles

## Quantifying the Graph

### Degree of a Vertex

Degree of vertex is the number of lines associated with it. For example, let us consider the above graph(Figure 1). Degree of a vertex B is 4.

### Indegree of a Vertex

It is the number of arcs entering the vertex. For example, let us consider the above graph(Figure 1). Indegree of vertex B is 1.

### Outdegree of Vertex

It is the number of arcs leaving the vertex. For example, let us consider the above graph(Figure 1). Outdegree of vertex B is 3.

## Graph Representation

There are different ways to represent Graph

### Adjacency Matrix Representation

One simple way is to use **adjacency matrix** representation which uses a two-dimensional array. This means that vertices are adjacent to one another.

- If there is an edge between two vertices, then we set
**A[v**._{i}][v_{j}]=1 - Otherwise we set the entry in the array to 0.

For adjacency matrix, put **1** in the table if V_{i} and V_{j} have edge in the graph else put **0**.

Suppose, if the edge is associated with weight, then we can set **A[v _{i}][v_{j}]** equal to the weight. The memory space required for this adjacency matrix is O(|V|

^{2}).

For adjacency matrix, put the weightage in the table if V_{i} and V_{j} have edge with weightage else put some constant **C**. Here we take the constant as **∞**.The self ending weightage is **0**. If the graph is dense, an **adjacency matrix** is suitable representation.

## Adjacency List Representation

Suppose, if the graph is sparse, then an **adjacency list** is the better solution for graph representation. In **adjacency list representation**, for each vertex, we maintain a list of all adjacent vertices. If the edges have weights, then this extra information is also stored in the list cells. The memory space required for adjacency list is O(|E|+|V|).