Итак, мы уже рассмотрели первую часть вашего вопроса, но я повторю это здесь для тех, кто следует. Всякий раз, когда вы работаете с графами и матрицей смежности, вероятно, лучший способ инициализировать элементы в массиве - это «оба пути».
Вместо простого использования следующего, что потребует, чтобы указанная вершина c была указана первой для того, чтобы найти соседей:
adjMatrix[nodes.indexOf(src)][nodes.indexOf(dst)] = 1;
Используйте это, что приводит к поискам, которые агностичны c порядка вершин:
adjMatrix[nodes.indexOf(src)][nodes.indexOf(dst)] = 1;
adjMatrix[nodes.indexOf(dst)][nodes.indexOf(src)] = 1;
Теперь для упорядочения. Вы хотите, чтобы вершины выводились в порядке от «наименьшей» буквы к «наибольшей» букве. Мы рассмотрим каждую из ваших структур данных индивидуально.
В BFS (итеративно) вы используете Очередь. Очереди "первым пришел, первым вышел". Другими словами, элемент, который был добавлен в очередь наименьшим образом, будет выводиться первым при каждом вызове queue.poll(). Таким образом, вам нужно добавить ваши узлы от наименьшего к наибольшему.
В DFS (итеративном) вы используете стек. Стеки являются «последним, первым - первым». Другими словами, элемент, который был недавно добавлен в стек, будет выводиться первым при каждом вызове stack.pop(). Таким образом, вам нужно добавить ваши узлы от наибольшего к наименьшему.
В DFS (рекурсивном) вы используете List. Списки не имеют упорядочения «in-out» как такового, так как мы можем опрашивать их в любом порядке, который мы хотим, но проще всего было бы просто отсортировать Список от наименьшего к наибольшему и вывести их по порядку.
Имея это в виду, нам нужно ввести протокол для сортировки графа. Все три протокола используют getNeighbors(), поэтому мы отсортируем выведенный список сразу после вызова этой функции. Списки можно упорядочить с помощью функции Collections.sort(List l) из java.utils.Collections, но сначала нам нужно изменить класс узлов, чтобы Java знал, как сортировать узлы. Для дальнейшего изучения деталей того, что я делаю, вы можете посмотреть здесь , но этот пост становится намного длиннее, чем я предполагал, поэтому я просто покажу код здесь и позвольте заинтересованные исследуют сами ссылки.
Сначала необходимо настроить класс Node, реализовав Comparable<Node> и добавив функцию compareTo().
static class Node implements Comparable<Node>{
public char label;
public boolean visited = false;
public Node(char label) {
this.label = label;
}
@Override
public int compareTo(Node that) {
return Character.compare(this.label, that.label);
}
}
Затем в тех случаях, когда мы хотим чтобы упорядочить список от наименьшего к наибольшему, мы можем использовать Collections.sort(neighbors). Когда мы хотим от наименьшего к меньшему, мы можем использовать Collections.sort(neighbors, Collections.reverseOrder()). Наш окончательный код будет выглядеть так:
// BFS traversal (iterative version)
public void bfs() {
Queue<Node> queue = new LinkedList<Node>();
queue.add(rootNode);
while(!queue.isEmpty()) {
Node node = queue.poll();
printNode(node);
node.visited = true;
List<Node> neighbors = getNeighbors(node);
//NEW CODE: Sort our neighbors List!
Collections.sort(neighbors);
for ( int i = 0; i < neighbors.size(); i ++) {
Node n = neighbors.get(i);
if (n != null && n.visited != true) {
queue.add(n);
n.visited = true;
}
}
}
}
// DFS traversal (iterative version)
public void dfs() {
Stack<Node> stack = new Stack<Node>();
stack.add(rootNode);
while(!stack.isEmpty()){
Node node = stack.pop();
if(node.visited != true) {
printNode(node);
node.visited = true;
}
List<Node> neighbors = getNeighbors(node);
//NEW CODE: Sort our neighbors List in reverse order!
Collections.sort(neighbors, Collections.reverseOrder());
for (int i = 0; i < neighbors.size(); i++) {
Node n = neighbors.get(i);
if(n != null && n.visited != true) {
stack.add(n);
}
}
}
}
// DFS traversal (recursive version)
public void dfs(Node n) {
printNode(n);
n.visited = true;
List<Node> neighbors = getNeighbors(n);
//NEW CODE: Sort our neighbors List!
Collections.sort(neighbors);
for (int i = 0; i < neighbors.size(); i ++) {
Node node = neighbors.get(i);
if(node != null && node.visited != true) {
dfs(node);
}
}
}