Discussion :

[Mus54Ep]

Bonjour,
Je suis débutant.
J'ai trouvé sur le net un code Java que je dois améliorer pour pouvoir terminer mon TP.
Ce programme affiche les tous les chemins possibles entre deux points d'un graphe.
Ce que je veux savoir, c'est l'utilité de chacune des bibliothèques utilisées dans ce programme. Je sais qu'elles sont utilisées pour l'appel de fonctions prédéfinies, mais je ne sais pas exactement ce que fait chaque fonction.
Voilà donc le code source :
Les bibliothèques utilisées :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

Classe graph.java :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Graph {
    private Map<String, LinkedHashSet<String>> map = new HashMap();
 
    public void addEdge(String node1, String node2) {
        LinkedHashSet<String> adjacent = map.get(node1);
        if(adjacent==null) {
            adjacent = new LinkedHashSet();
            map.put(node1, adjacent);
        }
        adjacent.add(node2);
    }
 
    public void addTwoWayVertex(String node1, String node2) {
        addEdge(node1, node2);
        addEdge(node2, node1);
    }
 
    public boolean isConnected(String node1, String node2) {
        Set adjacent = map.get(node1);
        if(adjacent==null) {
            return false;
        }
        return adjacent.contains(node2);
    }
 
    public LinkedList<String> adjacentNodes(String last) {
        LinkedHashSet<String> adjacent = map.get(last);
        if(adjacent==null) {
            return new LinkedList();
        }
        return new LinkedList<String>(adjacent);
    }
}

Classe Search.java :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class Search {
 
    private static final String START = "E";
    private static final String END = "B";
 
    public static void main(String[] args) {
        // this graph is directional
        Graph graph = new Graph();
        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "A");
        graph.addEdge("B", "D");
        graph.addEdge("B", "E"); // this is the only one-way connection
        graph.addEdge("B", "F");
        graph.addEdge("C", "A");
        graph.addEdge("C", "E");
        graph.addEdge("C", "F");
        graph.addEdge("D", "B");
        graph.addEdge("E", "C");
        graph.addEdge("E", "F");
        graph.addEdge("F", "B");
        graph.addEdge("F", "C");
        graph.addEdge("F", "E");
        LinkedList<String> visited = new LinkedList();
        visited.add(START);
        new Search().breadthFirst(graph, visited);
    }
 
    private void breadthFirst(Graph graph, LinkedList<String> visited) {
        LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
        // examine adjacent nodes
        for (String node : nodes) {
            if (visited.contains(node)) {
                continue;
            }
            if (node.equals(END)) {
                visited.add(node);
                printPath(visited);
                visited.removeLast();
                break;
            }
        }
        // in breadth-first, recursion needs to come after visiting adjacent nodes
        for (String node : nodes) {
            if (visited.contains(node) || node.equals(END)) {
                continue;
            }
            visited.addLast(node);
            breadthFirst(graph, visited);
            visited.removeLast();
        }
    }
 
    private void printPath(LinkedList<String> visited) {
        for (String node : visited) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }
}

Je ne pourrai pas le transformer en c++ si je ne comprends pas la méthode utilisée.
Je souhaite que quelqu'un pourrait m'aider afin de terminer mon TP.
Cordialement.

[tchize_]

Map => associe des clés à des valeurs
List => contient une liste d'élément, conserve l'ordre d'insertion
Set => Comme une liste, mais les éléments sont unique et l'ordre d'insertion n'est pas préservé
LinkedHashSet et LinkedList => implémentation respective de Set et List utilisant des listes chainées.

Pour le reste, tous les détails sont dans la javadoc desdites librairies.

[Mus54Ep]

Merci beaucoup,
Comme ça, je vais essayer de comprendre tout le reste.
Salut