# Introduction to Graphs

A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph is composed of a set of vertices( **V **) and a set of edges( **E **). The graph is denoted by **G(E, V).**

__Components of a Graph__

**Vertices:**Vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertex or nodes. Every node/vertex can be labeled or unlabelled.**Edges:**Edges are drawn or used to connect two nodes of the graph. It can be ordered pair of nodes in a directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be labeled/unlabelled.

__Types Of Graph__

__Types Of Graph__

#### 1. Null Graph

A graph is known as a null graph if there are no edges in the graph.

#### 2. Trivial Graph

Graph having only a single vertex, it is also the smallest graph possible.

#### 3. Undirected Graph

A graph in which edges do not have any direction. That is the nodes are unordered pairs in the definition of every edge.

#### 4. Directed Graph

A graph in which edge has direction. That is the nodes are ordered pairs in the definition of every edge.

#### 5. Connected Graph

The graph in which from one node we can visit any other node in the graph is known as a connected graph.

#### 6. Disconnected Graph

The graph in which at least one node is not reachable from a node is known as a disconnected graph.

#### 7. Regular Graph

The graph in which the degree of every vertex is equal to the other vertices of the graph. Let the degree of each vertex be **K** then the graph

#### 8. Complete Graph

The graph in which from each node there is an edge to each other node.

#### 9. Cycle Graph

The graph in which the graph is a cycle in itself, the degree of each vertex is 2.

#### 10. Cyclic Graph

A graph containing at least one cycle is known as a Cyclic graph.

#### 11. Directed Acyclic Graph

A Directed Graph that does not contain any cycle.

#### 12. Bipartite Graph

A graph in which vertex can be divided into two sets such that vertex in each set does not contain any edge between them.

**13. Weighted Graph**

- Weighted graphs can be further classified as directed weighted graphs and undirected weighted graphs.

** **

__Tree v/s Graph__

Trees are the restricted types of graphs, just with some more rules. Every tree will always be a graph but not all graphs will be trees. Linked List, Trees, and Heaps all are special cases of graphs.

__Representation of Graphs__

There are two ways to store a graph:

- Adjacency Matrix
- Adjacency List

__Adjacency Matrix__

In this method, the graph is stored in the form of the 2D matrix where rows and columns denote vertices. Each entry in the matrix represents the weight of the edge between those vertices.

__Adjacency List__

This graph is represented as a collection of linked lists. There is an array of pointer which points to the edges connected to that vertex.

__Comparison between Adjacency Matrix and Adjacency List__

When the graph contains a large number of edges then it is good to store it as a matrix because only some entries in the matrix will be empty. An algorithm such as Prim’s and Dijkstra adjacency matrix is used to have less complexity.

Action | Adjacency Matrix | Adjacency List |
---|---|---|

Adding Edge | O(1) | O(1) |

Removing and edge | O(1) | O(N) |

Initializing | O(N*N) | O(N) |

__Basic Operations on Graphs__

Below are the basic operations on the graph:

- Insertion of Nodes/Edges in the graph – Insert a node into the graph.
- Deletion of Nodes/Edges in the graph – Delete a node from the graph.
- Searching on Graphs – Search an entity in the graph.
- Traversal of Graphs – Traversing all the nodes in the graph.

__Usage of graphs__

- Maps can be represented using graphs and then can be used by computers to provide various services like the shortest path between two cities.
- When various tasks depend on each other then this situation can be represented using a Directed Acyclic graph and we can find the order in which tasks can be performed using topological sort.
- State Transition Diagram represents what can be the legal moves from current states. In-game of tic tac toe this can be used.