Graph data structure is represented using following representations...

- Adjacency Matrix
- Incidence Matrix
- Adjacency List

**Adjacency Matrix**

In this representation, graph can be represented using a matrix of size total number of vertices by total number of vertices. That means if a graph with 4 vertices can be represented using a matrix of 4X4 class. In this matrix, rows and columns both represents vertices. This matrix is filled with either 1 or 0. Here, 1 represents there is an edge from row vertex to column vertex and 0 represents there is no edge from row vertex to column vertex.

For example, consider the following undirected graph representation...

Directed graph representation...

**Incidence Matrix**

In this representation, graph can be represented using a matrix of size total number of vertices by total number of edges. That means if a graph with 4 vertices and 6 edges can be represented using a matrix of 4X6 class. In this matrix, rows represents vertices and columns represents edges. This matrix is filled with either 0 or 1 or -1. Here, 0 represents row edge is not connected to column vertex, 1 represents row edge is connected as outgoing edge to column vertex and -1 represents row edge is connected as incoming edge to column vertex.

For example, consider the following directed graph representation...

**Adjacency List**

In this representation, every vertex of graph contains list of its adjacent vertices.

For example, consider the following directed graph representation implemented using linked list...

This representation can also be implemented using array as follows..

- Graph Representation
- Depth First Search (DFS) - Graph Traversal
- Breadth First Search (BFS) - Graph Traversal

- Kruskal’s Minimum Spanning Tree Algorithm
- Prim’s Minimum Spanning Tree
- Dijkstra’s shortest path algorithm
- Huffman Coding

## No comments:

## Post a Comment