Nadesłany przez mephisto, 08 kwietnia 2013 12:22
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.Pobierz pełne rozwiązanie.
Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
Paths.java:
/** * Sprawdzanie istnienia sciezek za pomoca algorytmow DFS i BFS dla grafow * nieskierowanych oraz skierowanych. * * UWAGA: Jesli ktos potrzebuje czyste algorytmy, to wystarczy usunac pole @{code edgeTo} i wszelkie jego uzycia. * * @author mephisto */ import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; // GRAFY NIESKIEROWANE class Graph { // liczba krawedzi private int e; // liczba wierzcholkow private int v; // tablica list sasiedztwa danego wierzcholka private List<Integer>[] adjacencyList; /** * * @param v * ilosc wierzcholkow w grafie */ @SuppressWarnings("unchecked") public Graph(int v) { this.v = v; this.e = 0; adjacencyList = (List<Integer>[]) new List[v]; for (int i = 0; i < v; i++) { adjacencyList[i] = new ArrayList<Integer>(); } } /** * Dodaje krawedz v-w do grafu nieskierowanego. * * @param v * jeden z wierzcholkow krawedzi * @param w * drugi z wierzcholkow krawedzi */ public void addEdge(int v, int w) { adjacencyList[v].add(w); adjacencyList[w].add(v); e++; } /** * * @return liczbe krawedzi */ public int getNumberOfEdges() { return e; } /** * @return liczbe wierzcholkow */ public int getNumberOfVertices() { return v; } /** * Zwraca liste sasiedztwa danego wierzcholka. * * @param v * indeks wierzcholka skierowanego * @return zwraca iterowalna kolekcje wierzcholkow sasiadujacych */ public Iterable<Integer> getAdjacencyList(int v) { return adjacencyList[v]; } /** * @return opis grafu. */ public String toString() { StringBuilder s = new StringBuilder(); String newLine = System.getProperty("line.separator"); s.append("wierzcholki: ").append(v).append("; krawedzie: ").append(e) .append(newLine); for (int i = 0; i < v; i++) { s.append(i).append(": "); for (int w : adjacencyList[i]) { s.append(w).append(" "); } s.append(newLine); } return s.toString(); } } class DFSPaths { // tablica krawedzi ktora jest // przechowuje wierzcholki z ktorych mozna sie dostac do biezacego // okreslonego indeksem tablicy private int[] edgeTo; // tablica odwiedzonych wierzcholkow private boolean[] marked; // wierzcholek zrodlowy, z ktorego rozpoczynamy przeszukiwanie private final int source; public DFSPaths(Graph graph, int source) { this.source = source; edgeTo = new int[graph.getNumberOfVertices()]; marked = new boolean[graph.getNumberOfVertices()]; dfs(graph, source); } /** * * @param vertex * indeks wierzcholka dla ktorego ma byc sprawdzenie istnienia * sciezki * @return true jesli istnieje sciezka z wierzcholka zrodlowego danego w * konstruktorze do wierzcholka {@code vertex} */ public boolean hasPathTo(int vertex) { return marked[vertex]; } /** * * @param vertex * docelowy wierzcholek * @return stos wierzcholkow prowadzacych ze zrodal {@code source} do celu * {@code vertex} jesli sciezka nie istnieje zwracana jest pusta * kolekcja */ public Iterable<Integer> getPathTo(int vertex) { Deque<Integer> path = new ArrayDeque<Integer>(); // jesli nie istnieje sciezka zwroc pusta sciezke if (!hasPathTo(vertex)) { return path; } // dopoki istnieje wierzcholek dodawaj go do stosu for (int w = vertex; w != source; w = edgeTo[w]) { path.push(w); } // dodaj na koniec krawedz zrodlowa path.push(source); return path; } private void dfs(Graph graph, int vertex) { // oznaczamy wierzcholek jako odwiedzony marked[vertex] = true; // dla kazdego sasiedniego wierzcholka jesli nie jest oznaczony // wywolujemy rekurencyjnie metode dfs, ktora odwiedzi wierzchoki i // zapisze trase for (int w : graph.getAdjacencyList(vertex)) { if (!marked[w]) { edgeTo[w] = vertex; dfs(graph, w); } } } } class BFSPaths { // tablica krawedzi ktora jest // przechowuje wierzcholki z ktorych mozna sie dostac do biezacego // okreslonego indeksem tablicy private int[] edgeTo; // tablica odwiedzonych wierzcholkow private boolean[] marked; // wierzcholek zrodlowy, z ktorego rozpoczynamy przeszukiwanie private final int source; private Queue<Integer> priorityQueue; public BFSPaths(Graph graph, int source) { this.source = source; edgeTo = new int[graph.getNumberOfVertices()]; marked = new boolean[graph.getNumberOfVertices()]; priorityQueue = new PriorityQueue<Integer>(graph.getNumberOfVertices()); priorityQueue.offer(source); bfs(graph, source); } /** * * @param vertex * indeks wierzcholka dla ktorego ma byc sprawdzenie istnienia * sciezki * @return true jesli istnieje sciezka z wierzcholka zrodlowego danego w * konstruktorze do wierzcholka {@code vertex} */ public boolean hasPathTo(int vertex) { return marked[vertex]; } /** * * @param vertex * docelowy wierzcholek * @return stos wierzcholkow prowadzacych ze zrodal {@code source} do celu * {@code vertex} jesli sciezka nie istnieje zwracana jest pusta * kolekcja */ public Iterable<Integer> getPathTo(int vertex) { Deque<Integer> path = new ArrayDeque<Integer>(); // jesli nie istnieje sciezka zwroc pusta sciezke if (!hasPathTo(vertex)) { return path; } // dopoki istnieje wierzcholek dodawaj go do stosu for (int w = vertex; w != source; w = edgeTo[w]) { path.push(w); } // dodaj na koniec krawedz zrodlowa path.push(source); return path; } private void bfs(Graph graph, int vertex) { // oznaczamy wierzcholek jako odwiedzony marked[vertex] = true; // dodajemy wierzcholek zrodlowy do kolejki priorityQueue.offer(vertex); // dopoki kolejka nie jest pusta, wybieramy krawedz o najnizszym // priorytecie // i oznaczamy jako odwiedzone wierzcholki z listy sasiedztwa usuwanego // wierzcholka // oraz dodajemy wierzcholki z listy sasiedztwa do kolejki while (!priorityQueue.isEmpty()) { int v = priorityQueue.remove(); for (int w : graph.getAdjacencyList(v)) { if (!marked[w]) { edgeTo[w] = v; marked[w] = true; priorityQueue.offer(w); } } } } } // GRAFY SKIEROWANE class DirectedGraph { // liczba krawedzi private int e; // liczba wierzcholkow private int v; // tablica list sasiedztwa danego wierzcholka private List<Integer>[] adjacencyList; /** * * @param v * ilosc wierzcholkow w grafie */ @SuppressWarnings("unchecked") public DirectedGraph(int v) { this.v = v; this.e = 0; adjacencyList = (List<Integer>[]) new List[v]; for (int i = 0; i < v; i++) { adjacencyList[i] = new ArrayList<Integer>(); } } /** * Dodaje krawedz v-w do grafu skierowanego. * * @param v * wierzcholek poczatkowy * @param w * wierzcholek koncowy */ public void addEdge(int v, int w) { adjacencyList[v].add(w); e++; } /** * * @return liczbe krawedzi */ public int getNumberOfEdges() { return e; } /** * @return liczbe wierzcholkow */ public int getNumberOfVertices() { return v; } /** * Zwraca liste sasiedztwa danego wierzcholka. * * @param v * indeks wierzcholka skierowanego * @return zwraca iterowalna kolekcje wierzcholkow sasiadujacych */ public Iterable<Integer> getAdjacencyList(int v) { return adjacencyList[v]; } /** * @return opis grafu. */ public String toString() { StringBuilder s = new StringBuilder(); String newLine = System.getProperty("line.separator"); s.append("wierzcholki: ").append(v).append("; krawedzie: ").append(e) .append(newLine); for (int i = 0; i < v; i++) { s.append(i).append(": "); for (int w : adjacencyList[i]) { s.append(w).append(" "); } s.append(newLine); } return s.toString(); } } class DFSDirectedPaths { // tablica krawedzi ktora jest // przechowuje wierzcholki z ktorych mozna sie dostac do biezacego // okreslonego indeksem tablicy private int[] edgeTo; // tablica odwiedzonych wierzcholkow private boolean[] marked; // wierzcholek zrodlowy, z ktorego rozpoczynamy przeszukiwanie private final int source; public DFSDirectedPaths(DirectedGraph graph, int source) { this.source = source; edgeTo = new int[graph.getNumberOfVertices()]; marked = new boolean[graph.getNumberOfVertices()]; dfs(graph, source); } /** * * @param vertex * indeks wierzcholka dla ktorego ma byc sprawdzenie istnienia * sciezki * @return true jesli istnieje sciezka z wierzcholka zrodlowego danego w * konstruktorze do wierzcholka {@code vertex} */ public boolean hasPathTo(int vertex) { return marked[vertex]; } /** * * @param vertex * docelowy wierzcholek * @return stos wierzcholkow prowadzacych ze zrodal {@code source} do celu * {@code vertex} jesli sciezka nie istnieje zwracana jest pusta * kolekcja */ public Iterable<Integer> getPathTo(int vertex) { Deque<Integer> path = new ArrayDeque<Integer>(); // jesli nie istnieje sciezka zwroc pusta sciezke if (!hasPathTo(vertex)) { return path; } // dopoki istnieje wierzcholek dodawaj go do stosu for (int w = vertex; w != source; w = edgeTo[w]) { path.push(w); } // dodaj na koniec krawedz zrodlowa path.push(source); return path; } private void dfs(DirectedGraph graph, int vertex) { // oznaczamy wierzcholek jako odwiedzony marked[vertex] = true; // dla kazdego sasiedniego wierzcholka jesli nie jest oznaczony // wywolujemy rekurencyjnie metode dfs, ktora odwiedzi wierzchoki i // zapisze trase for (int w : graph.getAdjacencyList(vertex)) { if (!marked[w]) { edgeTo[w] = vertex; dfs(graph, w); } } } } class BFSDirectedPaths { // tablica krawedzi ktora jest // przechowuje wierzcholki z ktorych mozna sie dostac do biezacego // okreslonego indeksem tablicy private int[] edgeTo; // tablica odwiedzonych wierzcholkow private boolean[] marked; // wierzcholek zrodlowy, z ktorego rozpoczynamy przeszukiwanie private final int source; private Queue<Integer> priorityQueue; public BFSDirectedPaths(DirectedGraph graph, int source) { this.source = source; edgeTo = new int[graph.getNumberOfVertices()]; marked = new boolean[graph.getNumberOfVertices()]; priorityQueue = new PriorityQueue<Integer>(graph.getNumberOfVertices()); priorityQueue.offer(source); bfs(graph, source); } /** * * @param vertex * indeks wierzcholka dla ktorego ma byc sprawdzenie istnienia * sciezki * @return true jesli istnieje sciezka z wierzcholka zrodlowego danego w * konstruktorze do wierzcholka {@code vertex} */ public boolean hasPathTo(int vertex) { return marked[vertex]; } /** * * @param vertex * docelowy wierzcholek * @return stos wierzcholkow prowadzacych ze zrodal {@code source} do celu * {@code vertex} jesli sciezka nie istnieje zwracana jest pusta * kolekcja */ public Iterable<Integer> getPathTo(int vertex) { Deque<Integer> path = new ArrayDeque<Integer>(); // jesli nie istnieje sciezka zwroc pusta sciezke if (!hasPathTo(vertex)) { return path; } // dopoki istnieje wierzcholek dodawaj go do stosu for (int w = vertex; w != source; w = edgeTo[w]) { path.push(w); } // dodaj na koniec krawedz zrodlowa path.push(source); return path; } private void bfs(DirectedGraph graph, int vertex) { // oznaczamy wierzcholek jako odwiedzony marked[vertex] = true; // dodajemy wierzcholek zrodlowy do kolejki priorityQueue.offer(vertex); // dopoki kolejka nie jest pusta, wybieramy krawedz o najnizszym // priorytecie // i oznaczamy jako odwiedzone wierzcholki z listy sasiedztwa usuwanego // wierzcholka // oraz dodajemy wierzcholki z listy sasiedztwa do kolejki while (!priorityQueue.isEmpty()) { int v = priorityQueue.remove(); for (int w : graph.getAdjacencyList(v)) { if (!marked[w]) { edgeTo[w] = v; marked[w] = true; priorityQueue.offer(w); } } } } } public class Paths { public static void main(String[] args) { // Przyklad ze strony http://www.algorytm.org/algorytmy-grafowe/przeszukiwanie-grafu-wszerz-bfs-i-w-glab-dfs.html // UWAGA: graf skierowany zostal przerobiony na graf nieskierowany // stan na dzien 2013-04-08 // grafy nieskierowane Graph graph = new Graph(6); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 4); graph.addEdge(2, 3); graph.addEdge(2, 5); graph.addEdge(3, 0); graph.addEdge(4, 3); System.out.println("Graf nieskierowany: " + graph); System.out.println("\nDFS - sciezki nieskierowane"); // droga z 1 do 5 DFSPaths dfs1 = new DFSPaths(graph, 0); for (int it : dfs1.getPathTo(4)) { System.out.print(it + " "); } System.out.println("\n----------"); // droga z 5 do 1 DFSPaths dfs2 = new DFSPaths(graph, 4); for (int it : dfs2.getPathTo(0)) { System.out.print(it + " "); } System.out.println("\nBFS - sciezki nieskierowane"); // droga z 1 do 5 BFSPaths bfs1 = new BFSPaths(graph, 0); for (int it : bfs1.getPathTo(4)) { System.out.print(it + " "); } System.out.println("\n----------"); // droga z 5 do 1 BFSPaths bfs2 = new BFSPaths(graph, 4); for (int it : bfs2.getPathTo(0)) { System.out.print(it + " "); } // -------------------------------------------- // grafy skierowane DirectedGraph digraph = new DirectedGraph(6); digraph.addEdge(0, 1); digraph.addEdge(0, 2); digraph.addEdge(1, 4); digraph.addEdge(2, 3); digraph.addEdge(2, 5); digraph.addEdge(3, 0); digraph.addEdge(4, 3); // Przyklad ze strony http://www.algorytm.org/algorytmy-grafowe/przeszukiwanie-grafu-wszerz-bfs-i-w-glab-dfs.html // stan na dzien 2013-04-08 System.out.println("\n\nGraf skierowany: " + digraph); System.out.println("\nDFS - sciezki skierowane"); // droga z 1 do 5 DFSDirectedPaths dfs3 = new DFSDirectedPaths(digraph, 0); for (int it : dfs3.getPathTo(4)) { System.out.print(it + " "); } System.out.println("\n----------"); // droga z 5 do 1 DFSDirectedPaths dfs4 = new DFSDirectedPaths(digraph, 4); for (int it : dfs4.getPathTo(0)) { System.out.print(it + " "); } System.out.println("\nBFS - sciezki skierowane"); // droga z 1 do 5 BFSDirectedPaths bfs3 = new BFSDirectedPaths(digraph, 0); for (int it : bfs3.getPathTo(4)) { System.out.print(it + " "); } System.out.println("\n----------"); // droga z 5 do 1 BFSDirectedPaths bfs4 = new BFSDirectedPaths(digraph, 4); for (int it : bfs4.getPathTo(0)) { System.out.print(it + " "); } } }