It is used in places like: BFS, DFS, Dijkstra's Algorithm etc. Sometimes it is also used in network flows.Īdjacency List: Adjacency List is a space efficient method for graph representation and can replace adjacency matrix almost everywhere if algorithm doesn't require it explicitly. It can also be used in DFS (Depth First Search) and BFS (Breadth First Search) but list is more efficient there. ApplicationĪdjacency Matrix: Adjacency matrix is used where information about each and every possible edge is required for the proper working of an algorithm like :- Floyd-Warshall Algorithm where shortest path from each vertex to each every other vertex is calculated (if it exists). Note: Dense Graph are those which has large number of edges and sparse graphs are those which has small number of edges. It is recommended that we should use Adjacency Matrix for representing Dense Graphs and Adjacency List for representing Sparse Graphs. N denotes the number of nodes/ vertices and M denotes the number of edgesĭegree(V) denotes the number of edges from node V Adjacency Matrix ComplexityĬheck if there is an edge between nodes U and V: O(1)įind all edges from a node: O(N) Adjacency List ComplexityĬheck if there is an edge between nodes U and V: O(degree(V))įind all edges from a node V: O(degree(V)) Where to use?Īs we have seen in complexity comparisions both representation have their pros and cons and implementation of both representation is simple. In an adjacency matrix, 0 implies that no relationship between nodes exists and 1 implies that a relationship between nodes exists. A graph is a set of vertices (nodes) associated with edges. After above loop Adjcency List is ready. An adjacency matrix is a two-dimensional matrix used to map the relationship between the nodes of a graph.

where n is number of vertices and m is number of edgesĪ.push_back(u) // In case of directed graph this statement is removed. This code is for constructing adjacency list for undirected graph, with minor change it will also work for directed graph. Also, If graph is undirected append u to the v th list of array A. Iterate each given edge of the form (u,v) and append v to the u th list of array A. Intially each list is empty so each array element is initialise with empty list. Create an array A of size N and type of array must be list of vertices. If a graph has n number of vertices, then the adjacency matrix of that graph is n x n, and each entry of the matrix represents the number of.

In graph theory, if we can go to node B from. For example, your neighbors are adjacent to you.

Adjacent means 'next to or adjoining something else' or to be beside something. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. It is the 2D matrix that is used to map the association between the graph nodes. An adjacency matrix is a square matrix used to represent a finite graph. The pseudocode for constructing Adjacency Matrix is as follows:ġ. In graph theory, an adjacency matrix is a dense way of describing the finite graph structure. Adjacency List for Undirected Graph: (For FIG: UD.1) Pseudocode