A graph is a data structure that consists of a set of  nodes connected by edges. Graphs are used to simulate many real-world problems, such as paths in cities, circuit networks, and social networks. This is graph implementation part 3 – graph as adjacency matrix.

directed graph as matrix

undirected graph as matrix

Table of Content


What is adjacency matrix?

An adjacency matrix is one presentation of a graph data structure. It is a square matrix with dimensions equivalent to the number of nodes in the graph. Adjacency matrix is preferred when the graph is dense.


How to define and initialize an adjacency matrix?

The nodes in a graph are the indices for both rows and columns. If there is an edge between node i and j, there is value at cell[i][j]. Otherwise, the cell’s value is 0 or blockValue. If a graph is undirected, the value will be assigned at [j][i] as well.

Java

Javascript

Python


DFS in adjacency matrix

DFS starts from the source node, and explores all adjacent cells with recursion. The adjacent cells can be accessed by increasing or decreasing the index of the row and column. For example if the current position is [i][j], the adjacent cells are [i-1][j] , [i+1][j], [i][j-1], [i][j+1], which means up, down, left and right.

Java

Javascript

Python

Doodle

Graph as matrix dfs


BFS in adjacency matrix

BFS starts from the source cell. It visits its adjacent cells that have value of 1 and keeps going in the same direction if there is a passable path. It stops when the next adjacency cell is 0 or the cell is next to the matrix’s edge. Saves the end cells’ [row, column] to the queue. Repeat the process by taking out the first item in the queue and visit its adjacent cells. If the first item matches with the destination, the program returns.

Both DFS and BFS use a variable visited to track which cell has been visited. This guarantees each cell is visited once. Both algorithms take O(V^2) time to finish. V is the number of vertices.

Java

Javascript

Python

Doodle

Graph as matrix bfs


Free download

Download graph as adjacency matrix in Java, JavaScript and Python
Data structures introduction PDF