Zdrojový kód z prednášky 17.4.2012

import java.util.*;
import sk.upjs.paz.*;

public class Grafy {

        /**
         * Realizuje prehladavanie do sirky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Boolean> bfs(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

                // Vytvorime rad pre navstivene vrcholy, ktorych susedov sme zatial
                // neskusali navstivit
                Queue<Vertex> rad = new LinkedList<Vertex>();

                // Na zaciatku je navstiveny iba startovaci vrchol
                navstiveny.put(start, true);
                rad.offer(start);

                // Kym rad nie je prazdny
                while (!rad.isEmpty()) {
                        // Vyberieme prvy vrchol v rade
                        Vertex v = rad.poll();

                        // Postupne vsetkych nenavstivenych susedov vrcholu v oznacime ako
                        // navstivenych a pridame ich do radu
                        for (Vertex sused : v.getOutNeighbours())
                                if (!navstiveny.get(sused)) {
                                        navstiveny.put(sused, true);
                                        rad.offer(sused);
                                }
                }

                return navstiveny;
        }

        /**
         * Realizuje rekurzivne prehladavanie do hlbky
         *
         * @param v
         *            vrchol, ktory ideme navstivit
         * @param navstiveny
         *            mapa, v ktorej mame informaciu o tom, ktore vrcholi boli
         *            navstivene
         */
        public static void dfs(Vertex v, Map<Vertex, Boolean> navstiveny) {
                navstiveny.put(v, true);

                // Navstivime vsetkych nenavstivenych susedov
                for (Vertex sused : v.getOutNeighbours())
                        if (!navstiveny.get(sused))
                                dfs(sused, navstiveny);
        }

        /**
         * Realizuje (spusti) rekurzivne prehladavanie do hlbky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Boolean> dfsRekurzivne(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

                // Spustime vyhladavanie z aktualneho vrchola
                dfs(start, navstiveny);
                return navstiveny;
        }

        /**
         * Realizuje nerekurzivne prehladavanie do hlbky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Boolean> dfsNerekurzivne(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

                // Vytvorime zasobnik na vrcholy, ktore treba navstivit
                Stack<Vertex> zasobnik = new Stack<Vertex>();

                // Na zaciatku je navstiveny iba startovaci vrchol
                navstiveny.put(start, true);
                zasobnik.push(start);

                while (!zasobnik.isEmpty()) {
                        // Vyberieme vrchol z vrchu zasobnika
                        Vertex v = zasobnik.pop();

                        // Postupne vsetkych nenavstivenych susedov vrcholu v oznacime ako
                        // navstivenych a pridame ich na vrch zasobnika
                        for (Vertex sused : v.getOutNeighbours())
                                if (!navstiveny.get(sused)) {
                                        navstiveny.put(sused, true);
                                        zasobnik.push(sused);
                                }
                }

                return navstiveny;
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                // Vytvorime graf
                Graph fb = new Graph();
                // Nacitame zoznam hran zo suboru
                fb.loadFromFile("graf.txt");

                // Spustime rekurzivne dfs
                bfs(fb, fb.getVertex("A"));
        }
}

import java.util.*;

import sk.upjs.paz.*;

public class TopSort {

        /**
         * @param args
         */
        public static void main(String[] args) {
                // Vytvorime graf
                Graph g = new Graph();
                // Nastavime, ze to ma byt orientovany graf
                g.setDirected(true);
                // Nacitame hrany zo suboru
                g.loadFromFile("aktivity.txt");

                // Zoznam hran
                List<String> topsort = new ArrayList<String>();

                // Kym mame v grafe nejake vrcholy
                while (g.getVertices().size() > 0) {

                        // Najdeme nejaky vrchol bez predchodcov
                        Vertex bezPredchodcov = null;
                        for (Vertex v : g.getVertices())
                                if (v.getInEdges().size() == 0) {
                                        bezPredchodcov = v;
                                        break;
                                }

                        // Ak sme nasli vrchol bez predchodcov, tak ho pridame do
                        // zoznamu a vyhodime ho z grafu
                        // Ak vrcholu bez predchodcov niet, tak sa neda graf utriedit
                        if (bezPredchodcov != null) {
                                topsort.add(bezPredchodcov.getLabel());
                                bezPredchodcov.remove();
                        } else {
                                System.out
                                                .println("Vrcholy grafu nie je mozne topologicky utriedit.");
                                break;
                        }
                }

                // Ak sme skoncili s prazdnym grafom, tak mame utriedene vrcholy
                if (g.getVertices().size() == 0)
                        System.out.println(topsort);
        }

}