DFS cu graful reprezentat prin liste de adiacenta

DFS-AdjLists.java

import java.util.Scanner;
/*
0 1
liste de adiacenta:

cap[]

1: 2, 3  cap[1]
2: 1, 5,4 cap[2]
3: 1, 5   cap[3]
4: 2, 6   cap[4]
5: 2, 3, 6  cap[5]
6: 5, 4    cap[6]
*/
public class GraphLinkedList {

       static class Node {

            int vecin;
            Node urmator;

            Node(int vecin) {

                 this.vecin = vecin;
                 this.urmator = null;
            }
       }


       private  final Node[] cap; //cap[i] cap[1] = null, cap[2] = null, cap[3] = null, cap[4] = null , cap[5] = null
       private  final boolean[] vizitat;
       private  final int n;//numarul de noduri ; varfuri

       public GraphLinkedList( int n ) {
          this.n = n;
          this.cap = new Node[ n ];
          this.vizitat = new boolean[ n ];
       }

       //1 3
       //1 2
       //1 5
       // 1: 3,2,5

       /*
u v
1 3
1 2  1 -> 2 -> 3
2 5  2 -> 5 -> 4
2 4
3 5  3->5
5 6  5 -> 6
4 6  4 -> 6
       */
       public void adaugaMuchie(int u, int v) {
              //inserare la inceputul listei O(1)
              Node nou = new Node( v );
              nou.urmator = cap[ u ];
              cap[ u ] = nou;
       }

       public void citeste() {
            Scanner sc = new Scanner(System.in);
            System.out.print("Numarul de muchii");
            int m = sc.nextInt();
            System.out.print("Introduceti muchiile");
            for(int i = 0; i < m; ++i) {

                int u = sc.nextInt() - 1;
                int v = sc.nextInt() - 1;

                adaugaMuchie(u, v);
                adaugaMuchie(v, u); //graful este neorientat
            }
       }

       public void DFS(int node) {

         vizitat[ node ] = true;

         System.out.print((node+1) + " ");

         for(Node ptr = cap[node]; ptr != null; ptr = ptr.urmator) {

              if(!vizitat[ptr.vecin]) {

                  DFS( ptr.vecin );
              }
         }

       }



       public static void main(String[] args) {

             Scanner sc = new Scanner(System.in);
             System.out.print("Numarul de noduri:");
             int n = sc.nextInt();

             GraphLinkedList g = new GraphLinkedList( n );

             g.citeste();

             System.out.print("Parcurgere DFS: ");

             for(int i = 0; i < n; ++i) {
                 if(!g.vizitat[i]) {
                     g.DFS(i);
                 }
             }

             System.out.println();

       }
}