Oui
Supposons que nous avons ce graphe, et voulons trouver les distances les plus courtes en partant de A:
![Graphe]()
Voici une interface simple NodeCollection qui permet les opérations nécessaires pour le parcours :
interface NodeCollection {
void offer(E node);
E extract();
boolean isEmpty();
}
Et les implémentations pour la file, la pile et la file de priorité. Notez que cette interface et ces classes n'ont pas vraiment besoin d'être génériques :
static class NodeQueue implements NodeCollection {
private final Queue queue = new LinkedList();
@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 implements NodeCollection {
private final Stack stack = new Stack();
@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 implements NodeCollection {
private final PriorityQueue pq = new PriorityQueue();
@Override public void offer(E node) { pq.add(node); }
@Override public E extract() { return pq.poll(); }
@Override public boolean isEmpty() { return pq.isEmpty(); }
}
Notez que pour que la PriorityQueue fonctionne comme prévu, la classe Node doit fournir une méthode compareTo(Node) :
static class Node implements Comparable {
final String name;
Map 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();
}
}
Et voici enfin la classe Graph. Notez que la méthode traverse prend une instance de NodeCollection, qui sera utilisée pour stocker les nœuds lors du parcours.
static class Graph {
Map 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);
}
/**
* Parcourt ce graphe en commençant par le nœud donné et renvoie une map des chemins les plus courts depuis le nœud de départ
* vers chaque nœud.
*
* @param startName nœud de départ
* @return chemin le plus court pour chaque nœud du graphe
*/
public Map traverse(String startName, NodeCollection 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 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';
}
}
}
Enfin, voici la méthode main, qui parcourt le même graphe 3 fois, une fois avec chacun des types 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()));
System.out.println("Stack (DFS):\n" + graph.traverse("A", new NodeStack()));
System.out.println("PriorityQueue (Dijkstra):\n" + graph.traverse("A", new NodePriorityQueue()));
}
Et les résultats !
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}
Remarquez que DFS prend parfois la branche supérieure en premier, donnant des résultats différents mais symétriques.
Voici à quoi ressemblent les résultats sur le graphe :
![Résultats]()
