Matematické Fórum

Dobrý den.
Vůbec si nevím rady se samostatnou prací. Zkoušel jsem jí odevzdávat a validátor mně ji ne a ne zvalidovat. Jen si říkám, kde mám chyby.

Zadání:
Naprogramujte v Javě prohledávání grafu (tj. orientovaného i neorientovaného) do hloubky (DFS) a do šířky (BFS) pro jeho reprezentace seznamem sousednosti (S) a maticí sousednosti (M). Úkolem je pouze průchod grafu ze zadaného vrcholu s výpisem objevených vrcholů. Prohledávání tedy nepokračuje, i když nebyly ze zadaného vrcholu objeveny všechny vrcholy grafu!
Doporučená struktura programu
Vytvořte jediného klienta (obsahujícího metodu main()) a čtyři samostatné soubory (*.java) pro:
▪ reprezentaci grafu seznamem sousednosti a prohledáváním do šířky (SBFS)
▪ reprezentaci grafu seznamem sousednosti a prohledáváním do hloubky (SDFS)
▪ reprezentaci grafu maticí sousednosti a prohledáváním do šířky (MBFS)
▪ reprezentaci grafu maticí sousednosti a prohledáváním do hloubky (MDFS)
Každý soubor by měl obsahovat třídu Vrchol (reprezentace vrcholu), třídu Graf (reprezentace grafu), metody pro vytvoření grafu a průchod grafem. Dále je nutno implementovat metody umožňující volitelný vstup dat z klávesnice nebo z textového souboru a volitelný výstup dat na obrazovku či do textového souboru.
Přepokládejte vstup zadání grafu v následující závazné struktuře (zcela shodné pro vstup z klávesnice i vstup ze souboru). Nejprve bude na samostatné řádce zadána varianta implementace (SBFS, SDFS, MBFS, MDFS), na další řádce pak hodnota v(0<v<20), reprezentující počet vrcholů grafu. Následovat bude v řádek s názvy vrcholů (názvem může být nezáporné číslo, písmeno anglické abecedy, řetězec tvořený znaky anglické abecedy - včetně mezer). Na další řádce je zadána hodnota h(0≤h), která reprezentuje počet hran. Na dalších h řádkách budou zadány jednotlivé hrany (každá na samostatné řádce). Pro neorientovanou hranu použijte znak '-', pro orientovanou hranu znak '>' (směr orientace). Na poslední řádce bude zadán název vrcholu, ze kterého se bude graf prohledávat.
Např.: SBFS
4
A
B
C
D
5
A-B
C-A
D>A
B-C
D>C
B
Tvar výstupu je rovněž závazný. První tři velká písmena udávají zkratku způsobu prohledávání, následovanou v kulatých závorkách označením zadaného vrcholu, ze kterého se graf prochází, odděleným znakem dvojtečka ':' po němž následuje výpis postupně objevených vrcholů, ve tvaru "mezera" a označení vrcholu oddělené od následujících vrcholů znakem čárka ','. Za posledním vrcholem čárka nesmí být!
Např.: BFS(B): B, C, A či DFS(D): D, C, B, A
- 2 -
Výstup výsledků bude v zadaném tvaru výstupu proveden buď na obrazovku, nebo do textového souboru (viz dále - Ovládání programu).
Ovládání programu
Program bude možné spouštět se zadáním parametru, nebo bez zadání parametru programu.
Bude-li zadán parametr, bude představovat název vstupního textového souboru, který obsahuje vstupní data v závazné struktuře. V tomto případě bude proveden výstup požadovaných výsledků pouze do textového souboru, který bude mít závazný název vysledky.txt (podmínka úspěšné validace).
Nebude-li zadán parametr, budou všechna vstupní data v závazné struktuře načtena z klávesnice a výstup výsledků proveden pouze na obrazovku.
Další pokyny
Program vytvářejte strukturovaně s použitím metod. Všechny metody i jednotlivé třídy důsledně okomentujte Javadoc komentáři, ve kterých bude uveden @author. Nebude vyžadována žádná další dokumentace.
Odevzdání a validace
Samostatnou práci odevzdejte na portál do bloku Samostatná práce vložením pouze jediného zdrojového souboru, jelikož validátor nedokáže zpracovat více než jeden soubor. To znamená, že soubory všech tříd je nutno spojit do jednoho souboru s názvem Ppa2_SP.java, který je závazný z důvodu automatické kontroly (validace). V tomto souboru, který tak obsahuje více tříd, může být označena specifikátorem public pouze třída obsahující metodu main(), tj. soubor s klientem, který je pojmenován dle stanovených pravidel (Ppa2_SP.java). V případě použití Eclipsu nezapomeňte též před odevzdáním odstranit package. Můžete předpokládat, že vstupní soubor s daty bude zadán na validátoru správně.


Můj zdrojový kód:

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

/**
* @author Martin Prokeš
*/
  public class Ppa2_SP {
public class Graf
{

    public Vrchol[] vrcholy= new Vrchol[1000];;
    static int[][] maticeSousednosti = new int[1000][1000];
   /**
    * @author Martin Prokeš
    */
    public static class Vrchol
    {
        int data;
        int vzdalenost;
        char barva = 'B';
        int predchudce;
       
        public Vrchol(int data)
        {
            this.data = data;
        }

        public LinkedList<Integer> sousedi()
        {
            LinkedList<Integer> f = new LinkedList<Integer>();
            for (int i=1; i<1000; i++)
            {
                if (maticeSousednosti[data][i] == 1)
                f.add(i);
           
            }
            return f;
       
        }
       
        /**
        * @author Martin Prokeš
        */
        public void print()
        {
            System.out.print(data);
            System.out.print(" ");
        }
    }
   
    void Graf() {
   
    }
   
    /**
    * @author Martin Prokeš
    */
    void hrana(int z, int kam)
    {
        maticeSousednosti[z][kam] = 1;
    }

   
    /**
    * @author Martin Prokeš
    */
    void BFS(int s)
    {
        System.out.print("BFS(");
        System.out.print(s);
        System.out.print("): ");
   
        LinkedList<Integer> f = new LinkedList<Integer>();
        vrcholy[s].barva = 'S';
        vrcholy[s].vzdalenost = 0;
        f.add(s);
        while(!f.isEmpty()) {
            int u = f.removeFirst();
            for (int v: vrcholy[u].sousedi())
            {
                if (vrcholy[v].barva == 'B')
                {
                    vrcholy[v].barva = 'S';
                    vrcholy[v].print();
                    vrcholy[v].vzdalenost = vrcholy[u].vzdalenost+1;
                    vrcholy[v].predchudce = u;
                    f.add(v);
                }
            }
            vrcholy[u].barva = 'C';
        }
    }
   
    /**
    * @author Martin Prokeš
    */
    public static void nastavVystupDoSouboru()
    {
        try
        {
              FileOutputStream fout= new FileOutputStream("vystup.txt");
              PrintStream stdout= new PrintStream(fout);
              System.setOut(stdout);
        }
        catch (FileNotFoundException ex)
        {
        }   
    }

    /**
    * @author Martin Prokeš
    */
    public static void main(String[] args)
    {
        Graf graf = new Graf();
        Scanner keyboard = new Scanner(System.in);
        System.out.println("Zadej 1 - orientovany graf, 2 - neorientovany graf");
        int typGrafu = keyboard.nextInt();
        keyboard.nextLine();
        System.out.println("Zadej 1 - vstup z klavesnice, 2 - vstup ze souboru vstup.txt");
        int typVstupu = keyboard.nextInt();
        keyboard.nextLine();
       
        String cisla="";
        if (typVstupu == 2)
        {
            try
            {
                File jmenoSouboru = new File("vstup.txt");
                Scanner vstupni = new Scanner(jmenoSouboru);
                cisla = vstupni.nextLine();
            }
            catch (FileNotFoundException ex)
            {
            }
           
        } else
        {
            System.out.println("Zadej mezerou oddelena dvojice cisel vrcholu spojene pomlckou (napr.: 1-2 1-3 3-4)");
            cisla = keyboard.nextLine();
        }
        String res[] = cisla.split(" ");
        System.out.print("Zadej cislo pocatecniho vrcholu: ");
        int cislo = keyboard.nextInt();
        keyboard.nextLine();
        System.out.println("Zadej 1 - vystup na obrazovku, 2 - vystup do souboru vystup.txt");
        int typVystupu = keyboard.nextInt();
        if (typVystupu == 2) nastavVystupDoSouboru();
        int prvni;
        int druhy;
        int pocitadloVrcholu=0;
        for (int i=0;i<res.length;i++)
        {
             prvni = Integer.parseInt(res[i].split("-")[0]);
             druhy = Integer.parseInt(res[i].split("-")[1]);
             if (graf.vrcholy[prvni]==null) {graf.vrcholy[prvni] = new Vrchol(prvni);pocitadloVrcholu++;}
             if (graf.vrcholy[druhy]==null) {graf.vrcholy[druhy] = new Vrchol(druhy);pocitadloVrcholu++;}
             if (typGrafu == 2) graf.hrana(druhy, prvni);
             graf.hrana(prvni, druhy);
        }
        graf.BFS(cislo);
        System.out.println();

    }
}

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

/**
* @author Martin Prokeš
*/
public class Graf
{

    public Vrchol[] vrcholy= new Vrchol[1000];;
    static int[][] maticeSousednosti = new int[1000][1000];
   /**
    * @author Martin Prokeš
    */
    public static class Vrchol
    {
        int data;
        int vzdalenost;
        char barva = 'B';
        int predchudce;
       
        public Vrchol(int data)
        {
            this.data = data;
        }

        public LinkedList<Integer> sousedi()
        {
            LinkedList<Integer> f = new LinkedList<Integer>();
            for (int i=1; i<1000; i++)
            {
                if (maticeSousednosti[data][i] == 1)
                f.add(i);
           
            }
            return f;
       
        }
       
        /**
        * @author Martin Prokeš
        */
        public void print()
        {
            System.out.print(data);
            System.out.print(" ");
        }
    }
   
    void Graf() {
   
    }
   
    /**
    * @author Martin Prokeš
    */
    void hrana(int z, int kam)
    {
        maticeSousednosti[z][kam] = 1;
    }

   
    /**
    * @author Martin Prokeš
    */

    void DFS (int u)
    {
        vrcholy[u].barva = 'S';
        for (int v: vrcholy[u].sousedi())
        {
            if (vrcholy[v].barva == 'B')
            {
                vrcholy[v].predchudce = u;
                vrcholy[v].print();
                DFS(v);
            }
        }
        vrcholy[u].barva = 'C';
    }
   
    /**
    * @author Martin Prokeš
    */
    public static void nastavVystupDoSouboru()
    {
        try
        {
              FileOutputStream fout= new FileOutputStream("vystup.txt");
              PrintStream stdout= new PrintStream(fout);
              System.setOut(stdout);
        }
        catch (FileNotFoundException ex)
        {
        }   
    }

    /**
    * @author Martin Prokeš
    */
    public static void main(String[] args)
    {
        Graf graf = new Graf();
        Scanner keyboard = new Scanner(System.in);
        System.out.println("Zadej 1 - orientovany graf, 2 - neorientovany graf");
        int typGrafu = keyboard.nextInt();
        keyboard.nextLine();
        System.out.println("Zadej 1 - vstup z klavesnice, 2 - vstup ze souboru vstup.txt");
        int typVstupu = keyboard.nextInt();
        keyboard.nextLine();
       
        String cisla="";
        if (typVstupu == 2)
        {
            try
            {
                File jmenoSouboru = new File("vstup.txt");
                Scanner vstupni = new Scanner(jmenoSouboru);
                cisla = vstupni.nextLine();
            }
            catch (FileNotFoundException ex)
            {
            }
           
        } else
        {
            System.out.println("Zadej mezerou oddelena dvojice cisel vrcholu spojene pomlckou (napr.: 1-2 1-3 3-4)");
            cisla = keyboard.nextLine();
        }
        String res[] = cisla.split(" ");
        System.out.print("Zadej cislo pocatecniho vrcholu: ");
        int cislo = keyboard.nextInt();
        keyboard.nextLine();
        System.out.println("Zadej 1 - vystup na obrazovku, 2 - vystup do souboru vystup.txt");
        int typVystupu = keyboard.nextInt();
        if (typVystupu == 2) nastavVystupDoSouboru();
        int prvni;
        int druhy;
        int pocitadloVrcholu=0;
        for (int i=0;i<res.length;i++)
        {
             prvni = Integer.parseInt(res[i].split("-")[0]);
             druhy = Integer.parseInt(res[i].split("-")[1]);
             if (graf.vrcholy[prvni]==null) {graf.vrcholy[prvni] = new Vrchol(prvni);pocitadloVrcholu++;}
             if (graf.vrcholy[druhy]==null) {graf.vrcholy[druhy] = new Vrchol(druhy);pocitadloVrcholu++;}
             if (typGrafu == 2) graf.hrana(druhy, prvni);
             graf.hrana(prvni, druhy);
        }
        System.out.print("DFS(");
        System.out.print(cislo);
        System.out.print("): ");
        graf.DFS(cislo);
        System.out.println();

    }
}

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

/**
* @author Martin Prokeš
*/
public class Graf
{

    Vrchol[] vrcholy= new Vrchol[1000];;
   
   /**
    * @author Martin Prokeš
    */
    public static class Vrchol
    {
        int data;
        int vzdalenost;
        LinkedList<Integer> sousedi = new LinkedList<Integer>();
        char barva = 'B';
        int predchudce;
       
        public Vrchol(int data)
        {
            this.data = data;
        }
       
        /**
        * @author Martin Prokeš
        */
        public void print()
        {
            System.out.print(data);
            System.out.print(" ");
        }
    }
   
    void Graf() {
   
    }
   
    /**
    * @author Martin Prokeš
    */
    void hrana(int z, int kam)
    {
        vrcholy[z].sousedi.add(kam);
    }

   
    /**
    * @author Martin Prokeš
    */
    void BFS(int s)
    {
        System.out.print("BFS(");
        System.out.print(s);
        System.out.print("): ");
   
        LinkedList<Integer> f = new LinkedList<Integer>();
        vrcholy[s].barva = 'S';
        vrcholy[s].vzdalenost = 0;
        f.add(s);
        while(!f.isEmpty()) {
            int u = f.removeFirst();
            for (int v: vrcholy[u].sousedi)
            {
                if (vrcholy[v].barva == 'B')
                {
                    vrcholy[v].barva = 'S';
                    vrcholy[v].print();
                    vrcholy[v].vzdalenost = vrcholy[u].vzdalenost+1;
                    vrcholy[v].predchudce = u;
                    f.add(v);
                }
            }
            vrcholy[u].barva = 'C';
        }
    }
   
    /**
    * @author Martin Prokeš
    */
    public static void nastavVystupDoSouboru()
    {
        try
        {
              FileOutputStream fout= new FileOutputStream("vystup.txt");
              PrintStream stdout= new PrintStream(fout);
              System.setOut(stdout);
        }
        catch (FileNotFoundException ex)
        {
        }   
    }

    /**
    * @author Martin Prokeš
    */
    public static void main(String[] args)
    {
        Graf graf = new Graf();
        Scanner keyboard = new Scanner(System.in);
        System.out.println("Zadej 1 - orientovany graf, 2 - neorientovany graf");
        int typGrafu = keyboard.nextInt();
        keyboard.nextLine();
        System.out.println("Zadej 1 - vstup z klavesnice, 2 - vstup ze souboru vstup.txt");
        int typVstupu = keyboard.nextInt();
        keyboard.nextLine();
       
        String cisla="";
        if (typVstupu == 2)
        {
            try
            {
                File jmenoSouboru = new File("vstup.txt");
                Scanner vstupni = new Scanner(jmenoSouboru);
                cisla = vstupni.nextLine();
            }
            catch (FileNotFoundException ex)
            {
            }
           
        } else
        {
            System.out.println("Zadej mezerou oddelena dvojice cisel vrcholu spojene pomlckou (napr.: 1-2 1-3 3-4)");
            cisla = keyboard.nextLine();
        }
        String res[] = cisla.split(" ");
        System.out.print("Zadej cislo pocatecniho vrcholu: ");
        int cislo = keyboard.nextInt();
        keyboard.nextLine();
        System.out.println("Zadej 1 - vystup na obrazovku, 2 - vystup do souboru vystup.txt");
        int typVystupu = keyboard.nextInt();
        if (typVystupu == 2) nastavVystupDoSouboru();

        int prvni;
        int druhy;
        for (int i=0;i<res.length;i++)
        {
             prvni = Integer.parseInt(res[i].split("-")[0]);
             druhy = Integer.parseInt(res[i].split("-")[1]);
             if (graf.vrcholy[prvni]==null) graf.vrcholy[prvni] = new Vrchol(prvni);
             if (graf.vrcholy[druhy]==null) graf.vrcholy[druhy] = new Vrchol(druhy);
             if (typGrafu == 2) graf.hrana(druhy, prvni);
             graf.hrana(prvni, druhy);
        }
        graf.BFS(cislo);
        System.out.println();

    }
}

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


/**
* @author Martin Prokeš
*/
public class Graf
{

    Vrchol[] vrcholy= new Vrchol[1000];;
   
    /**
    * @author Martin Prokeš
    */
    public static class Vrchol
    {
        int data;
        int objeven;
        LinkedList<Integer> sousedi = new LinkedList<Integer>();
        char barva = 'B';
        int predchudce;
       
        /**
        * @author Martin Prokeš
        */
        public Vrchol(int data)
        {
            this.data = data;
        }
       
        /**
        * @author Martin Prokeš
        */
        public void print()
        {
            System.out.print(data);
            System.out.print(" ");
        }
    }
   
    void Graf() {
   
    }
   
    void hrana(int z, int kam) {
        vrcholy[z].sousedi.add(kam);
    }

    /**
    * @author Martin Prokeš
    */
    void DFS (int u) {
        vrcholy[u].barva = 'S';
        //cas = cas + 1;
        //vrcholy[u].objeven = cas;
        for (int v: vrcholy[u].sousedi)
        {
            if (vrcholy[v].barva == 'B')
            {
                vrcholy[v].predchudce = u;
                vrcholy[v].print();
                DFS(v);
            }
        }
        vrcholy[u].barva = 'C';
        //vrcholy[u].dokoncen = cas = cas + 1;
    }

    /**
    * @author Martin Prokeš
    */
    public static void nastavVystupDoSouboru()
    {
        try
        {
              FileOutputStream fout= new FileOutputStream("vystup.txt");
              PrintStream stdout= new PrintStream(fout);
              System.setOut(stdout);
        }
        catch (FileNotFoundException ex)
        {
        }   
    }

    /**
    * @author Martin Prokeš
    */
    public static void main(String[] args)
    {
        Graf graf = new Graf();
        Scanner keyboard = new Scanner(System.in);
        System.out.println("Zadej 1 - orientovany graf, 2 - neorientovany graf");
        int typGrafu = keyboard.nextInt();
        keyboard.nextLine();
        System.out.println("Zadej 1 - vstup z klavesnice, 2 - vstup ze souboru vstup.txt");
        int typVstupu = keyboard.nextInt();
        keyboard.nextLine();
       
        String cisla="";
        if (typVstupu == 2)
        {
            try
            {
                File jmenoSouboru = new File("vstup.txt");
                Scanner vstupni = new Scanner(jmenoSouboru);
                cisla = vstupni.nextLine();
            }
            catch (FileNotFoundException ex)
            {
            }
           
        } else
        {
            System.out.println("Zadej mezerou oddelena dvojice cisel vrcholu spojene pomlckou (napr.: 1-2 1-3 3-4)");
            cisla = keyboard.nextLine();
        }
        String res[] = cisla.split(" ");
        System.out.print("Zadej cislo pocatecniho vrcholu: ");
        int cislo = keyboard.nextInt();
        keyboard.nextLine();
        System.out.println("Zadej 1 - vystup na obrazovku, 2 - vystup do souboru vystup.txt");
        int typVystupu = keyboard.nextInt();
        if (typVystupu == 2) nastavVystupDoSouboru();

        int prvni;
        int druhy;
        for (int i=0;i<res.length;i++)
        {
             prvni = Integer.parseInt(res[i].split("-")[0]);
             druhy = Integer.parseInt(res[i].split("-")[1]);
             if (graf.vrcholy[prvni]==null) graf.vrcholy[prvni] = new Vrchol(prvni);
             if (graf.vrcholy[druhy]==null) graf.vrcholy[druhy] = new Vrchol(druhy);
             if (typGrafu == 2) graf.hrana(druhy, prvni);
             graf.hrana(prvni, druhy);
        }
        System.out.print("DFS(");
        System.out.print(cislo);
        System.out.print("): ");

        graf.DFS(cislo);
        System.out.println();

    }
}
}

}
}