Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- public class Graph
- {
- int V;
- LinkedList<Integer> list[];
- Graph(int V){
- this.V=V;
- list=new LinkedList[V];
- for(int i=0;i<V;i++){
- list[i]=new LinkedList<Integer>();
- }
- }
- public void addedge(int x,int y)
- {
- list[x].addFirst(y);
- }
- public void printgraph(){
- for (int i = 0; i <V ; i++) {
- LinkedList<Integer> nlist = list[i];
- if(nlist.isEmpty()==false) {
- System.out.print("source = " + i + " => ");
- for (int j = 0; j < nlist.size(); j++) {
- System.out.print(" " + nlist.get(j));
- }
- }
- System.out.println();
- }
- }
- public void DFSrec(){
- boolean visited[] = new boolean [V];
- for(int i=0;i<V;i++)
- {
- if(!visited[i]){
- dfs(i,visited);
- }
- }
- }
- public void dfs(int v, boolean visited[])
- {
- visited[v] = true;
- System.out.print(v+" ");
- for(int i=0;i<list[v].size();i++)
- {
- int V = list[v].get(i);
- if(!visited[V])
- dfs(V,visited);
- }
- }
- public static void main(String [] args){
- Graph g = new Graph(7);
- g.addedge(1,3);
- g.addedge(2,3);
- g.addedge(0,4);
- g.addedge(4,5);
- g.addedge(5,6);
- g.printgraph();
- g.DFSrec();
- }
- }
- /* solution */
- /*
- Finished in 60 ms
- source = 0 => 4
- source = 1 => 3
- source = 2 => 3
- source = 4 => 5
- source = 5 => 6
- 0 4 5 6 1 3 2
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement