package javaCodes;
import java.util.Arrays;
import java.util.Scanner;
class dfs_algorithm
{
void dfs_traversal(int graph[][], int source, boolean visited[], int total_vertices)
{
System.out.print(source+" ");
visited[source] = true;
for(int i=0; i<total_vertices; i++)
{
if(graph[source][i] == 1 && !visited[i])
{
dfs_traversal(graph, i, visited, total_vertices);
}
}
}
}
public class DFS {
public static void main(String args[])
{
int total_vertices, edges, left_node, right_node;
Scanner sc = new Scanner(System.in);
System.out.println("Enter total number of vertices and esges : ");
total_vertices = sc.nextInt();
edges = sc.nextInt();
boolean visited[] = new boolean[total_vertices+1];
Arrays.fill(visited, false);
int g[][] = new int[total_vertices+1][total_vertices+1];
System.out.println("Enter values of nodes according to each edge : ");
for(int i=0; i<edges; i++)
{
left_node = sc.nextInt();
right_node = sc.nextInt();
g[left_node][right_node] = 1;
g[right_node][left_node] = 1;
}
int source;
System.out.print("Enter source : ");
source = sc.nextInt();
dfs_algorithm dfs = new dfs_algorithm();
dfs.dfs_traversal(g, source, visited, total_vertices);
}
}