Graph Representations

Graph data structure is represented using following representations...

1. Adjacency Matrix
2. Incidence Matrix
3. Adjacency List

Adjacency Matrix

• A matrix of size total number of vertices by total number of vertices can be used to represent a graph in this way. 
• That is, if a graph with four vertices can be represented by a 4X4 matrix.
• Rows and columns both represent vertices in this matrix. This matrix has either a 1 or a 0 in it. 
• There is an edge from row vertex to column vertex in this case, while there is no edge from row vertex to column vertex in this case.

For example, consider the following undirected graph representation.

Directed graph representation...

Incidence Matrix

• A matrix of size total number of vertices by total number of edges can be used to represent a graph in this way. That is, if a graph with four vertices and six edges can be represented by a 4X6 matrix. Rows represent vertices, and columns represent edges in this matrix.
• This matrix is filled with 0s, 1s, and -1s. Here, 0 indicates that the row edge is not connected to the column vertex, 1 indicates that the row edge is connected to the column vertex as an outgoing edge, and -1 indicates that the row edge is connected to the column vertex as an incoming edge.

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..