import java.io.*;
import java.util.*;

// Dybde-først og bredde-først traversering av graf.
//
// Bruker en enkel uvektet graf med nabomatrise, der data i nodene
// bare er en tekststreng (superklassen enkelGraf)
//
public class traverserGraf extends enkelGraf
{

    // Bruker en boolsk array til å merke av oppsøkte noder under
    // traversering
    boolean oppsokt[];


    // Konstruktør, leser inn en graf fra fil
    //
    public traverserGraf(String filNavn)
    {
	super(filNavn);
	oppsokt = new boolean[n];
    }


    // Dybde-først traversering med start i gitt node
    // Oppsøker hver node og skriver ut data i noden
    //
    public void DFS(int start)
    {
	// Markerer alle noder som ikke oppsøkte
	for (int i = 0; i < n; i++)
	    oppsokt[i] = false;

	// Kaller en intern rekursiv metode som gjør selve
	// traverseringen
	rDFS(start);

	System.out.println();
    }

    // Intern rekursiv dybde-først traversering med start i gitt node
    //
    private void rDFS(int x)
    {
	// Skriver ut innholdet i noden
	System.out.print(data[x] + " ");

	// Markerer at denne noden er oppsøkt
	oppsokt[x] = true;

	// Oppsøker rekursivt alle nodens naboer som ikke er oppsøkt
	// tidligere
	for (int y = 0; y < n; y++)
	    if (nabo[x][y] && !oppsokt[y])
		rDFS(y);
    }
    

    // Bredde-først traversering med start i gitt node
    //
    // Bruker kø-implementasjonen i java.util (der "enqueue"-metoden
    // heter "add" og "dequeue" heter "remove")
    //
    public void BFS(int start)
    {
	// Markerer alle noder som ikke oppsøkte
	for (int i = 0; i < n; i++)
	    oppsokt[i] = false;

	// Lager ny tom kø med heltall/nodenumre
	Queue<Integer> Q = new LinkedList<>();

	// Legger start-noden først i køen
	Q.add(new Integer(start));

	// Markerer at startnoden er lagret/oppsøkt, slik at den ikke
	// legges i kø en gang til senere
	oppsokt[start] = true;

	// Går i løkke inntil køen er tom og alle noder er oppsøkt
	while (!Q.isEmpty())
	{
	    // Tar ut første node fra køen og oppsøker/skriver ut
	    // denne
	    int x = Q.remove().intValue();
	    System.out.print(data[x] + " ");

	    // Legger alle uoppsøkte/ikke-lagrede naboer til nåværende
	    // node bakerst i køen
	    for (int y = 0; y < n; y++)
		if (nabo[x][y] && !oppsokt[y])
		{
		    Q.add(new Integer(y));
		    oppsokt[y] = true;
		}
	}
	System.out.println();
    }
 
    // Testprogram
    //
    public static void main(String args[])
    {
	// Leser navnet på en fil med grafdata som input fra
	// kommandolinjen
	String filNavn = " ";
	try
	{
	     if (args.length != 1)
		 throw new IOException("Mangler filnavn");
	     filNavn = args[0];
       	}
        catch (Exception e)
	{
	     System.err.println(e);
	     System.exit(1);
	}

	// Oppretter ny graf
	traverserGraf G = new traverserGraf(filNavn);

	// Dybde-først traversering en gang med start i hver node
	System.out.println("DFS:");
	for (int i = 0; i < G.antallNoder(); i++)
	    G.DFS(i);

	// Bredde-først traversering en gang med start i hver node
	System.out.println("\nBFS:");
	for (int i = 0; i < G.antallNoder(); i++)
	    G.BFS(i);
    }
}