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.
A node in the graph is also called vertex. A line between two nodes is edge. Two nodes are adjacent (or neighbors) if they are connected to each other through an edge. Path represents a sequence of edges between the two nodes.
In a directed graph, all of the edges represent a one-way relationship. In an undirected graph, all edges are bi-directional.
If the edges in the graph have weights, the graph is said to be a weighted graph. If the edges do not have weights, the graph is said to be unweighted.
Graph can be presented as adjacent list or adjacent matrix. An adjacent list is an array of edges or nodes. Adjacency list is used for representation of the sparse graphs. An adjacent matrix is a square matrix with dimensions equivalent to the number of nodes in the graph. Adjacent matrix is preferred when the graph is dense.
An adjacency matrix is a 2D array in which the elements indicate whether an edge is present between two nodes. If a graph has N nodes, the adjacency matrix is NxN array.
Part 1 – unweighted, directed/undirected graph, represented as adjacent list.
Part 2 – weighted, directed/undirected graph, represented as adjacent list.
Part 3 – weighted/unweighted, directed/undirected graph, represented as adjacent matrix
Table of Content
Define class and initialize
This is to initialize the graph from an input matrix. The nodes are the indices for both rows and columns. An edge between two nodes is indicated at the cell [r][c]. The value can be a number, character or object. If it is a number and the number is not 0, it indicates the weight of the edge.
If a graph is directed, the value will be assigned at cell [r][c]. If a graph is undirected, the value will be assigned at cell[c][r] as well.
If two nodes have no connections, the cell will be marked with different values. Note in this implementation, the input parameter blockValue is to specify this value, meaning the cell is blocked or cannot pass through.
After initialization, the number of rows and number of columns are defined. The value of elements in the matrix are assigned.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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(m*n) Space O(m*n) @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 17 |
class GraphAsMatrix { //Constructor, set both input and block value, Time O(m*n) Space O(m*n) //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(m*n) Space O(m*n) #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] |
Search in graph as adjacency matrix
The same as graph as adjacent list, find path from source to destination in matrix can be done using depth first search (DFS) and breadth first search (BFS).
Depth First Search 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 [r][c], the adjacent cells are [r-1][c] , [r+1][c], [r][c-1], [r][c+1], which means up, down, left and right.
To avoid visiting the same cell repeatedly, a 2D boolean variable visited is used. It is to track whether the cell has been visited. If a cell has been visited, it should not be visited again. This will keep the time complexity down to O(m*n). This technique is called memoization.
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(m*n), Space O(m*n) 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(m*n), Space O(m*n) 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(m*n), Space O(m*n) 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(m*n), Space O(m*n) 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(m*n), Space O(m*n) 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(m*n), Space O(m*n) 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
Breadth First Search starts from the source node, and explores all its adjacent nodes before going to the next level adjacent nodes. A queue is used to keep track the sequence to visit.
The same as DFS, 4 adjacent cells are accessed by increasing and decreasing index, ie [r-1][c] , [r+1][c], [r][c-1], [r][c+1]. The 2D boolean variable visited are functioning the same way as DFS.
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(m*n), Space O(m*n) 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(m*n), Space O(m*n) 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(m*n), Space O(m*n) 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
Print
Print is to print all values in the matrix. This method is used for debugging purpose.
Java
|
1 2 3 4 5 6 7 8 |
//Print matrix, Time O(m*n), Space O(1) public void printMatrix() { for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j ++) System.out.print( adj[i][j] + " "); System.out.println(); } } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 |
//Print matrix, Time O(m*n), Space O(1) printMatrix() { for (let i = 0; i < this.rows; i++) { var s = ''; for (let j = 0; j < this.columns; j ++) { s += this.adj[i][j] + ' '; } console.log(s); } } |
Python
|
1 2 3 4 5 6 7 |
#Print matrix, Time O(m*n), Space O(1) def printMatrix(self) : for i in range(0, self.rows) : s = '' for j in range (0, self.columns): s += str(self.adj[i][j]) + ' ' print(s) |
Download Java, JavaScript and Python code
Graph represented as matrix animated visual
Data structures and Java collections