Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.File;
- import java.util.Arrays;
- import java.util.Scanner;
- public class DFS {
- public static int node;
- public static int time;
- public static int[] color;
- public static int[] f;
- public static int[] d;
- public static int[] d1;
- public static int[] parent;
- public static int start;
- public static char[] nodes={'u','v','w','x','y','z'};
- public static int[] vertices=new int[] {0,1,2,3,4,5,6,7};
- public static int[][] matrix;
- //public static int node;
- public static void main(String [] args) {
- try{
- Scanner scn=new Scanner(new File("H:\\DFS Graph.txt"));
- String[] splitA;
- String temp=scn.nextLine();
- node=Integer.parseInt(temp);
- // out.println(v);
- String temp2=scn.nextLine();
- int edge=Integer.parseInt(temp2);
- matrix=new int[node][node];
- while(scn.hasNext())
- {
- String line=scn.nextLine();
- splitA=line.split(",");
- int x=Integer.parseInt(splitA[0]);
- int y=Integer.parseInt(splitA[1]);
- matrix[x][y]=1;
- }
- //----------
- color=new int[node];
- d=new int[node];
- d1=new int[node];
- f=new int[node];
- parent=new int[node];
- start=0;
- //----------------------\\\
- //d[start]=0;
- //parent[start]=0;
- //3 1 6 7 5 4 2 0
- for(int i=0;i<node;i++) {
- color[i]=0;
- d[i]=0;
- f[i]=0;
- }
- time=0;
- //color[0]=1;
- //DFS_visit(3);
- for(int j=0;j<node;j++) {
- if(color[j]==0) {
- DFS_visit(j);
- }
- }
- print();
- printStart();
- }
- catch(Exception e) {
- e.printStackTrace();
- }
- }
- public static void DFS_visit(int u) {
- //System.out.print(u+"====>");
- color[u]=1;
- time++;
- d[u]=time;
- for(int c=0;c<node;c++) {
- if(matrix[u][c]==1) {
- if(color[c]==0) {
- parent[c]=u;
- DFS_visit(c);
- }
- }
- }
- color[u]=2;//black
- time=time+1;
- f[u]=time;
- System.out.print(nodes[u]+">");
- }
- public static void print() {
- System.out.println();
- System.out.println();
- for(int c=0;c<node;c++) {
- if(color[c]==2)
- System.out.print("Black"+",");
- else if(color[c]==1) {
- System.out.print("Gray"+",");
- }
- else {
- System.out.print("White"+",");
- }
- }
- System.out.println();
- System.out.println();
- System.out.println();
- }
- public static int findIndex(int arr[], int t)
- {
- // if array is Null
- if (arr == null) {
- return -1;
- }
- // find length of array
- int len = arr.length;
- int i = 0;
- // traverse in the array
- while (i < len) {
- // if the i-th element is t
- // then return the index
- if (arr[i] == t) {
- return i;
- }
- else {
- i = i + 1;
- }
- }
- return -1;
- }
- public static void printStart() {
- System.out.println("###-------START TIME---------###");
- System.out.println();
- for(int k=0;k<node;k++) {
- d1[k]=d[k];
- //System.out.println(d[k]);
- }
- Arrays.sort(d1);
- for(int j=0;j<node;j++) {
- int b=(d1[j]);
- //System.out.println(b);
- int ind=findIndex(d,b);
- System.out.print(nodes[ind]+"=>");
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement