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.
Table of Content
- What is adjacency matrix
- How to initialize adjacency matrix
- Depth first search (DFS) in adjacency matrix
- Breadth first search (BFS) in adjacency matrix
- Free download
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
import java.util.*; public class GraphAsMatrix<T> { private T[][] adj; private int rows, columns; T blockValue; //Constructor, set both input and block value, Time O(V^2) Space O(V^2) @SuppressWarnings("unchecked") public GraphAsMatrix(T[][] input, T value) { rows = input.length; columns = input[0].length; blockValue = value; adj = (T[][]) new Object[rows][columns]; for (int i = 0; i < input.length; i++) { adj[i] = Arrays.copyOf(input[i], input[i].length); } } } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class GraphAsMatrix { //Constructor, set both input and block value, Time O(V^2) Space O(V^2) //m is number of rows, n is number of columns constructor(input, blockValue) { this.rows = input.length; this.columns = input[0].length; this.block = blockValue; this.adj = []; for (let i = 0; i < this.rows; i++) { this.adj[i] = []; for (let j = 0; j < this.columns; j++) { this.adj[i][j] = input[i][j]; } } } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class GraphAsMatrix : #Constructor, set both input and block value, Time O(V^2) Space O(V^2) #m is number of rows, n is number of columns def __init__(self, input, blockValue) : self.rows = len(input) self.columns = len(input[0]) self.block = blockValue self.adj = [[0 for i in range(self.columns)] for j in range(self.rows)] for i in range (0, self.rows): for j in range(0, self.columns): self.adj[i][j] = input[i][j] |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
//Check whether there is path from src(x,y) to dest (x, y) //DFS wraper, Time O(V^2), Space O(V^2) public boolean hasPathDfs( int sx, int sy, int dx, int dy) { boolean[][] visited = new boolean[rows][columns]; dfs(sx,sy, visited); if(!visited[dx][dy]) { return false; } return true; } //DFS + memoization, Time O(V^2), Space O(V^2) private void dfs(int i, int j, boolean[][] visited) { if(i < 0 || i >= rows || j < 0 || j >= columns || adj[i][j] == blockValue || visited[i][j]) { return; } visited[i][j] = true; dfs(i-1, j, visited); // Move left dfs(i+1, j, visited); // Move Right dfs(i, j-1, visited); //Move top dfs(i, j+1, visited); //Move bottom } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
//Check whether there is path from src(x,y) to dest (x, y) //DFS wraper, Time O(V^2), Space O(V^2) hasPathDfs(sx, sy, dx, dy) { var visited = []; for (let i = 0; i < this.rows; i++) { visited[i] = new Array(this.columns).fill(false); } this.dfs(sx, sy, visited); if(!visited[dx][dy]) { return false; } return true; } //DFS + memoization, Time O(V^2), Space O(V^2) dfs(i, j, visited) { if (i < 0 || i >= this.rows || j < 0 || j >= this.columns || this.adj[i][j] == this.block|| visited[i][j]) { return; } visited[i][j] = true; this.dfs(i-1, j, visited); // Move left this.dfs(i+1, j, visited); // Move Right this.dfs(i, j-1, visited); //Move top this.dfs(i, j+1, visited); //Move bottom } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#Check whether there is path from src(x,y) to dest (x, y) #DFS wraper, Time O(V^2), Space O(V^2) def hasPathDfs(self, sx, sy, dx, dy) : visited = [[False for i in range(self.columns)] for j in range(self.rows)] self.dfs(sx, sy, visited) if visited[dx][dy] == False: return False return True #DFS + memoization, Time O(V^2), Space O(V^2) def dfs(self, i, j, visited) : if i < 0 or i >= self.rows or j < 0 or j >= self.columns or self.adj[i][j] == self.block or visited[i][j] : return visited[i][j] = True self.dfs(i-1, j, visited) # Move left self.dfs(i+1, j, visited) # Move Right self.dfs(i, j-1, visited) # Move top self.dfs(i, j+1, visited) # Move bottom |
Doodle
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
//BFS + memorization, Time O(V^2), Space O(V^2) public boolean hasPathBfs(int sx, int sy, int dx, int dy) { boolean[][] visited = new boolean[rows][columns]; //memo int[][] dirs={{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; //4 neighbors Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{sx, sy}); //source visited[sx][sy] = true; while (!queue.isEmpty()) { int[] cur = queue.poll(); if (cur[0] == dx && cur[1] == dy) { //reach dest return true; } for (int[] dir: dirs) { //check all 4 directions int nx = cur[0], ny = cur[1]; while (nx >= 0 && nx < rows && ny >= 0 && ny < columns && adj[nx][ny] != blockValue) { nx += dir[0]; //continue moving to neighbors if there is no blocks ny += dir[1]; } nx -= dir[0]; //move back to last movable spot ny -= dir[1]; if (!visited[nx][ny]) { //(x,y) in the path visited[nx][ny] = true; queue.offer(new int[]{nx, ny}); } } } return false; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
//BFS + memorization, Time O(V^2), Space O(V^2) hasPathBfs(sx, sy, dx, dy) { var visited = []; for (let i = 0; i < this.rows; i++) { visited[i] = new Array(this.columns).fill(false); } var dirs=[[0, 1], [0, -1], [-1, 0], [1, 0]]; //4 neighbors var queue = []; queue.push([sx, sy]); //source visited[sx][sy] = true; while (queue.length != 0) { let cur = queue.shift(); if (cur[0] == dx && cur[1] == dy) { //reach dest return true; } for (let dir of dirs) { //check all 4 directions let nx = cur[0]; let ny = cur[1]; while (nx >= 0 && nx < this.rows && ny >= 0 && ny < this.columns && this.adj[nx][ny] != this.block) { nx += dir[0]; //continue moving to neighbors if there is no blocks ny += dir[1]; } nx -= dir[0]; //move back to last movable spot ny -= dir[1]; if (!visited[nx][ny]) { //(x,y) in the path visited[nx][ny] = true; queue.push([nx, ny]); } } } return false; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#BFS + memorization, Time O(V^2), Space O(V^2) def hasPathBfs(self, sx, sy, dx, dy) : visited = [[False for i in range(self.columns)] for j in range(self.rows)] dirs = [[0, 1], [0, -1], [-1, 0], [1, 0]]; #4 neighbors queue = [] queue.append([sx, sy]) #source visited[sx][sy] = True while len(queue) != 0 : cur = queue.pop(0) if cur[0] == dx and cur[1] == dy: #reach dest return True for dir in dirs: #check all 4 directions nx = cur[0] ny = cur[1] while nx >= 0 and nx < self.rows and ny >= 0 and ny < self.columns and self.adj[nx][ny] != self.block: nx += dir[0]; #continue moving to neighbors if there is no blocks ny += dir[1] nx -= dir[0]; #move back to last movable spot ny -= dir[1]; if visited[nx][ny] == False : #(x,y) in the path visited[nx][ny] = True queue.append([nx, ny]) return False |
Doodle
Free download
Download graph as adjacency matrix in Java, JavaScript and Python
Data structures introduction PDF