Gráf szélességi bejárás

/* Gráf szélességi bejárás:
    A Gráfot mártixban tároljuk.
    Az szBejaras bemenő adatai:
        Egy csúcsmátrixban tárolt gráf (mx).
        Egy egyész szám (start). Ez azt adja meg, hogy melyik csúcsból indítjuk
        a szélességi bejárást.
        A start szám 6×6 os mátrix esetén (6 csúcsú gráf), 0 tól 5 ig terjed.
    Az szBejaras egy void függvény ami kiírja, hogy a start csúcstól melyik pont hány lépésre van.

    A kódban beégetett mátrixra és az 5 ös start pontra az értelmezés a következő:
    A gráf 6 os pontjából
        az 1. őt 3 lépésből éri el
        az 2. at 2 lépésből éri el
        az 3. at 2 lépésből éri el
        az 4. et 1 lépésből éri el
        az 5. et 1 lépésből éri el
        az 6. at 0 lépésből éri el.

    Ezután van kiíratva a pi tömb:
    A pi tömb az algoritnus végén egy fát tartalmaz. Ki kinek a szülője.
*/

import java.util.LinkedList;
import java.util.Queue;

public class SzelessegiBejaras {
    private int[][] mx = { {0,1,1,0,0,0}, {1,0,1,1,1,0}, {1,1,0,1,0,0},
                           {0,1,1,0,1,1}, {0,1,0,1,0,1}, {0,0,0,1,1,0}, };

    public void szBejaras(int[][] mx, int start) {
        System.out.println("Szélességi bejárás");

        // Tömbök létrehozása
        int n = mx.length;
        String[] szin = new String[n];
        int[] pi = new int[n];
        int[] d = new int[n];
        // Sor, amibe a csúcsokat fogjuk rakni.
        Queue<Integer> q = new LinkedList<Integer>();

        // Inicializálás
        for ( int i=0; i<n; i++) {
            szin[i] = "W";  // Fehérre állítjuk minden csúcs színét.
            pi[i] = 0;      // Kezdetben egy csúcsnak sincs szülője.
            d[i] = 0;       // A startból startba 0 hosszú út vezet
            szin[start] = "G";  // A kezdő csúcs színe szürke
        }

        // Az algoritmus
        q.add(start);
        int u;
        while ( !q.isEmpty() ) {
            u = q.poll();
            for ( int i=0; i<n; i++) {
                if ( mx[i][u] == 1 ) {
                    if ( szin[i] == "W" ) {
                        q.add(i);
                        d[i] = d[u] + 1;
                        pi[i] = u;
                        szin[i] = "G";  // gray
                    }
                }
            }
            szin[u] = "B";  // black
        }

        // A mátrix kiíratása
        System.out.println("A csúcsmátrix:");
        for (int i=0; i<n; i++) {
            for ( int j=0; j<n; j++) {
                System.out.print(mx[i][j] + " ");
            }
            System.out.println();
        }

        // A d és a pi tömb kiíratása
        System.out.println("A gráf csúcsai számozva, a d és a pi tömb:");
        for ( int k=1; k<=n; k++ ) {
            System.out.print(k);
        }
        System.out.println();
        for ( int k=0; k<n; k++ ) {
            System.out.print(d[k]);
        }
        System.out.println();
        for ( int k=0; k<n; k++ ) {
            System.out.print(pi[k] + 1);
        }
    }

    public static void main(String[] args) {
        SzelessegiBejaras bejar = new SzelessegiBejaras();
        // Ha hármassal hívjuk meg akkor az a gráf 4. pontja lesz a start.
        bejar.szBejaras(bejar.mx, 5);
    }
}