Number of Islands and Flood-Fill Algorithm (code in JAVA)
import java.util.*;
public class graph {
// Function to return Breadth First Traversal of given graph.
public static ArrayList<Integer> bfsOfGraph(int numNodes, ArrayList<ArrayList<Integer>> adj) {
ArrayList < Integer > bfs = new ArrayList < > (); // stores ans
boolean vis[] = new boolean[numNodes + 1];
Queue < Integer > q = new LinkedList < > ();
// keep any node from where you want to start your bfs
q.add(1); // keep value of node here, if your node has 0 then you should keep it
vis[1] = true;
while (!q.isEmpty()) {
int levelSize = q.size(); // Number of nodes at the current level
for (int i = 0; i < levelSize; i++) {
Integer node = q.poll();
bfs.add(node);
for (Integer it : adj.get(node)) {
if (!vis[it]) {
vis[it] = true;
q.add(it);
}
}
}
bfs.add(-1); // Add a marker (-1) to separate levels
}
return bfs;
}
// Function to return a list containing the DFS traversal of the graph.
public static void dfs(int node, boolean vis[], ArrayList<ArrayList<Integer>> adj,
ArrayList<Integer> ls) {
//marking current node as visited
vis[node] = true;
ls.add(node);
//getting neighbour nodes
for(Integer it: adj.get(node)) {
if(vis[it] == false) {
dfs(it, vis, adj, ls);
}
}
}
public static ArrayList<Integer> dfsOfGraph(int numNodes, ArrayList<ArrayList<Integer>> adj) {
//boolean array to keep track of visited vertices
boolean vis[] = new boolean[numNodes+1];
vis[1] = true;
ArrayList<Integer> ls = new ArrayList<>();
dfs(1, vis, adj, ls);
return ls;
}
// Total number of provinces in given graph
public static void dfs(int node,
ArrayList<ArrayList<Integer>> adjLs ,
int vis[]) {
vis[node] = 1;
for(Integer it: adjLs.get(node)) {
if(vis[it] == 0) {
dfs(it, adjLs, vis);
}
}
}
public static int numProvinces(ArrayList<ArrayList<Integer>> adj, int V) {
int vis[] = new int[V + 1]; // +1
int cnt = 0;
for (int i = 1; i < V+1; i++) { // Start from vertex 1 (assuming 1-based indexing)
if (vis[i] == 0) {
cnt++;
dfs(i, adj, vis);
}
}
return cnt;
}
// Count number of islands
public static class Pair {
public int first;
public int second;
public Pair(int first, int second) {
this.first = first;
this.second = second;
}
}
public static void bfs(int ro, int co, int[][] vis, char[][] grid) {
vis[ro][co] = 1;
Queue<Pair> q = new LinkedList<Pair>();
q.add(new Pair(ro, co));
int n = grid.length;
int m = grid[0].length;
// until the queue becomes empty
while(!q.isEmpty()) {
int row = q.peek().first;
int col = q.peek().second;
q.remove();
// traverse in the neighbours and mark them if its a land
for(int delrow = -1; delrow<=1;delrow++) {
for(int delcol = -1; delcol <= 1; delcol++) {
int nrow = row + delrow;
int ncol = col + delcol;
// check if neighbour row and column is valid, and is an unvisited land
if(nrow >= 0 && nrow < n && ncol >= 0 && ncol < m
&& grid[nrow][ncol] == '1' && vis[nrow][ncol] == 0) {
vis[nrow][ncol] = 1;
q.add(new Pair(nrow, ncol));
}
}
}
}
}
// Function to find the number of islands.
public static int numIslands(char[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] vis = new int[n][m];
int cnt = 0;
for(int row = 0; row < n ; row++) {
for(int col = 0; col < m ;col++) {
// if not visited and is a land
if(vis[row][col] == 0 && grid[row][col] == '1') {
cnt++;
bfs(row, col, vis, grid);
}
}
}
return cnt;
}
// Flood-Fill Algorithm
public static void dfs_floodfill(int row, int col,
int[][] ans,
int[][] image,
int newColor, int delRow[], int delCol[],
int iniColor) {
// color with new color
ans[row][col] = newColor;
int n = image.length;
int m = image[0].length;
// there are exactly 4 neighbours
for(int i = 0;i<4;i++) {
int nrow = row + delRow[i];
int ncol = col + delCol[i];
// check for valid coordinate
// then check for same initial color and unvisited pixel
if(nrow>=0 && nrow<n && ncol>=0 && ncol < m &&
image[nrow][ncol] == iniColor && ans[nrow][ncol] != newColor) {
dfs_floodfill(nrow, ncol, ans, image, newColor, delRow, delCol, iniColor);
}
}
}
public static int[][] floodFill(int[][] image, int sr, int sc, int newColor)
{
// get initial color
int iniColor = image[sr][sc];
int[][] ans = image;
// delta row and delta column for neighbours
int delRow[] = {-1, 0, +1, 0};
int delCol[] = {0, +1, 0, -1};
dfs_floodfill(sr, sc, ans, image, newColor, delRow, delCol, iniColor);
return ans;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Input the number of nodes.
System.out.print("Enter the number of nodes: ");
int numNodes = scanner.nextInt();
// Create an adjacency list.
ArrayList<ArrayList<Integer>> adjList = new ArrayList<>(numNodes);
for (int i = 0; i < numNodes + 1; i++) { // numNodes + 2 only if remove empty zero index
adjList.add(new ArrayList<>());
}
// Input the number of edges.
System.out.print("Enter the number of edges: ");
int numEdges = scanner.nextInt();
// Input the edges (connections between nodes).
System.out.println("Enter the edges (startNode endNode):");
for (int i = 0; i < numEdges; i++) {
int startNode = scanner.nextInt();
int endNode = scanner.nextInt();
// Add an edge from startNode to endNode (for directed graph).
adjList.get(startNode).add(endNode);
// For undirected graph, add the reverse edge as well.
adjList.get(endNode).add(startNode); // Uncomment this line for an undirected graph.
}
// Print the adjacency list.
System.out.println("Adjacency List:");
for (int i = 1; i < numNodes + 1; i++) { // if start from zero then empty list will also be seen
System.out.print(i + " -> ");
for (int neighbor : adjList.get(i)) {
System.out.print(neighbor + " ");
}
System.out.println();
}
// BFS of graph
System.out.println("The bfs of the given graph is:");
ArrayList<Integer> bfsResult = bfsOfGraph(numNodes, adjList);
for (Integer node : bfsResult) {
if (node == -1) {
System.out.println(); // Print a newline for each level
} else {
System.out.print(node + " ");
}
}
// DFS of graph
System.out.println("The dfs of the given graph is:");
System.out.println(dfsOfGraph(numNodes, adjList));
// number of provinces
System.out.println("The total number of provinces in your graph is: "+numProvinces(adjList, numNodes));
// count number of islands from the given graph(grid)--> 2D Matrix
char[][] grid = {
{'0', '1', '1', '1', '0', '0', '0'},
{'0', '0', '1', '1', '0', '1', '0'}
};
System.out.println("The total number of island in the grid is: "+numIslands(grid));
// Flood Fill algorithm
System.out.println("The matix after flood fill is below:");
int[][] image = {
{1,1,1},
{1,1,0},
{1,0,1}
};
// sr = 1, sc = 1, newColor = 2
int[][] ans = floodFill(image, 1, 1, 2);
for(int i = 0; i < ans.length; i++){
for(int j = 0; j < ans[i].length; j++)
System.out.print(ans[i][j] + " ");
System.out.println();
}
scanner.close();
}
}
No comments:
Post a Comment