Да
Допустим, у нас есть этот график, и мы хотим найти кратчайшие расстояния, начиная с A:
Вот простой *Интерфейс 1009 *, который учитывает операции, необходимые для обхода:
interface NodeCollection<E> {
void offer(E node);
E extract();
boolean isEmpty();
}
И реализации для очереди, стека и очереди приоритетов.Обратите внимание, что этот интерфейс и классы на самом деле не должны быть универсальными:
static class NodeQueue<E> implements NodeCollection<E> {
private final Queue<E> queue = new LinkedList<E>();
@Override public void offer(E node) { queue.offer(node); }
@Override public E extract() { return queue.poll(); }
@Override public boolean isEmpty() { return queue.isEmpty(); }
}
static class NodeStack<E> implements NodeCollection<E> {
private final Stack<E> stack = new Stack<E>();
@Override public void offer(E node) { stack.push(node); }
@Override public E extract() { return stack.pop(); }
@Override public boolean isEmpty() { return stack.isEmpty(); }
}
static class NodePriorityQueue<E> implements NodeCollection<E> {
private final PriorityQueue<E> pq = new PriorityQueue<E>();
@Override public void offer(E node) { pq.add(node); }
@Override public E extract() { return pq.poll(); }
@Override public boolean isEmpty() { return pq.isEmpty(); }
}
Обратите внимание, что для PriorityQueue, чтобы работать должным образом, класс Node должен обеспечивать метод compareTo(Node):
static class Node implements Comparable<Node> {
final String name;
Map<Node, Integer> neighbors;
int dist = Integer.MAX_VALUE;
Node prev = null;
char color = 'w';
Node(String name) {
this.name = name;
this.neighbors = Maps.newHashMap();
}
@Override public int compareTo(Node o) {
return ComparisonChain.start().compare(this.dist, o.dist).result();
}
}
Теперь вот класс Graph.Обратите внимание, что метод traverse принимает экземпляр NodeCollection, который будет использоваться для хранения узлов во время обхода.
static class Graph {
Map<String, Node> nodes = Maps.newHashMap();
void addEdge(String fromName, String toName, int weight) {
Node from = getOrCreate(fromName);
Node to = getOrCreate(toName);
from.neighbors.put(to, weight);
to.neighbors.put(from, weight);
}
Node getOrCreate(String name) {
if (!nodes.containsKey(name)) {
nodes.put(name, new Node(name));
}
return nodes.get(name);
}
/**
* Traverses this graph starting at the given node and returns a map of shortest paths from the start node to
* every node.
*
* @param startName start node
* @return shortest path for each node in the graph
*/
public Map<String, Integer> traverse(String startName, NodeCollection<Node> collection) {
assert collection.isEmpty();
resetNodes();
Node start = getOrCreate(startName);
start.dist = 0;
collection.offer(start);
while (!collection.isEmpty()) {
Node curr = collection.extract();
curr.color = 'g';
for (Node neighbor : curr.neighbors.keySet()) {
if (neighbor.color == 'w') {
int thisPathDistance = curr.dist + curr.neighbors.get(neighbor);
if (thisPathDistance < neighbor.dist) {
neighbor.dist = thisPathDistance;
neighbor.prev = curr;
}
collection.offer(neighbor);
}
}
curr.color = 'b';
}
Map<String, Integer> shortestDists = Maps.newTreeMap();
for (Node node : nodes.values()) {
shortestDists.put(node.name, node.dist);
}
return shortestDists;
}
private void resetNodes() {
for (Node node : nodes.values()) {
node.dist = Integer.MAX_VALUE;
node.prev = null;
node.color = 'w';
}
}
}
Наконец, вот метод main, который проходит один и тот же граф 3 раза,по одному разу с каждым из NodeCollection типов:
private static Graph initGraph() {
Graph graph = new Graph();
graph.addEdge("A", "B", 2);
graph.addEdge("B", "C", 2);
graph.addEdge("C", "D", 2);
graph.addEdge("D", "E", 2);
graph.addEdge("E", "F", 2);
graph.addEdge("F", "L", 2);
graph.addEdge("A", "G", 10);
graph.addEdge("G", "H", 10);
graph.addEdge("H", "I", 10);
graph.addEdge("I", "J", 10);
graph.addEdge("J", "K", 10);
graph.addEdge("K", "L", 10);
return graph;
}
public static void main(String[] args) {
Graph graph = initGraph();
System.out.println("Queue (BFS):\n" + graph.traverse("A", new NodeQueue<Node>()));
System.out.println("Stack (DFS):\n" + graph.traverse("A", new NodeStack<Node>()));
System.out.println("PriorityQueue (Dijkstra):\n" + graph.traverse("A", new NodePriorityQueue<Node>()));
}
И результаты!
Queue (BFS):
{A=0, B=2, C=4, D=6, E=8, F=10, G=10, H=20, I=30, J=40, K=22, L=12}
Stack (DFS):
{A=0, B=2, C=4, D=66, E=64, F=62, G=10, H=20, I=30, J=40, K=50, L=60}
PriorityQueue (Dijkstra):
{A=0, B=2, C=4, D=6, E=8, F=10, G=10, H=20, I=30, J=32, K=22, L=12}
Обратите внимание, что DFS иногда сначала берет верхнюю ветвь, давая разные, но симметричные результаты.1036 * Вот как выглядят результаты на графике: 