Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package dfs;
- import java.util.Arrays;
- import java.util.Scanner;
- public class Dfs {
- public static int[][] matrix;
- public static int[] visited;
- public static int[] parent;
- public static int maxNodeNumber;
- public static void dfsIteration(int startNode)
- {
- //System.out.println("Source " + startNode);
- visited[startNode] = 1;
- for (int i = 0; i <= maxNodeNumber; i++) {
- if(visited[i] == 0 && matrix[startNode][i] == 1)
- {
- parent[i] = startNode;
- dfsIteration(i);
- }
- }
- }
- public static void printParent()
- {
- for (int i = 0; i <= maxNodeNumber; i++) {
- System.out.println("Child: "+i+ " Parent "+ parent[i]);
- }
- }
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- System.out.println("maxNode : ");
- maxNodeNumber = in.nextInt();
- matrix = new int[maxNodeNumber+1][maxNodeNumber+1];
- visited = new int[maxNodeNumber+1];
- parent = new int[maxNodeNumber+1];
- Arrays.fill(parent, -1);
- System.out.println("Enter the adjacent matrix");
- for(int i=0; i<= maxNodeNumber; i++ )
- {
- for(int j = 0; j <= maxNodeNumber; j++)
- {
- matrix[i][j] = in.nextInt();
- }
- }
- System.out.println("Start Node: ");
- int startNode = in.nextInt();
- System.out.println("Starting DFS Traversing");
- dfsIteration(startNode);
- printParent();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement