DFS на неориентированном графе
У меня есть упражнение для университета, где я должен написать алгоритм DFS для работы на неориентированном графе. Я также должен заставить программу суммировать значения всех узлов, показывающих порядок посещения узлов.
Вот данная структура:
#include <iostream>
#include <cassert>
using namespace std;
struct node {
// DATA STRUCTURE NODES
};
int dfs_sum(/* FUNCTION ARGUMENTS */) {
// DEPTH FIRST SEARCH ALGORITHM
}
void node_init(/* FUNCTION ARGUMENTS */) {
// INITIALIZATION OF NODE WITH LABEL "value" AND NEIGHBOR "num_adjacent"}
void edge_init(/* FUNCTION ARGUMENTS */) {
// INITIALIZATION OF EDGE BETWEEN TWO NODES
}
void node_delete(/* FUNCTION ARGUMENTS */) {
// DE-ALLOCATE MEMORY THAT WAS ALLOCATED IN "node_init"}
void init_nodes(node *nodes) {
node_init(&nodes[0], 1, 1);
node_init(&nodes[1], 2, 4);
node_init(&nodes[2], 3, 1);
node_init(&nodes[3], 4, 4);
node_init(&nodes[4], 5, 4);
node_init(&nodes[5], 6, 2);
node_init(&nodes[6], 7, 5);
node_init(&nodes[7], 8, 3);
node_init(&nodes[8], 9, 2);
node_init(&nodes[9], 10, 2);
node_init(&nodes[10], 11, 4);
node_init(&nodes[11], 12, 2);
edge_init(&nodes[0], &nodes[1]);
edge_init(&nodes[1], &nodes[4]);
edge_init(&nodes[1], &nodes[6]);
edge_init(&nodes[1], &nodes[7]);
edge_init(&nodes[2], &nodes[3]);
edge_init(&nodes[3], &nodes[6]);
edge_init(&nodes[3], &nodes[7]);
edge_init(&nodes[3], &nodes[11]);
edge_init(&nodes[4], &nodes[5]);
edge_init(&nodes[4], &nodes[8]);
edge_init(&nodes[4], &nodes[9]);
edge_init(&nodes[5], &nodes[6]);
edge_init(&nodes[6], &nodes[9]);
edge_init(&nodes[6], &nodes[10]);
edge_init(&nodes[7], &nodes[10]);
edge_init(&nodes[8], &nodes[10]);
edge_init(&nodes[10], &nodes[11]);
}
void delete_nodes(node *nodes) {
for (int i = 0; i < 12; ++i) {
node_delete(&nodes[i]);
}
}
int main() {
node *nodes= new node[12];
init_nodes(nodes);
int sum_dfs = dfs_sum(&nodes[0]);
cout << endl;
int sum_loop = 0;
for (int i = 0; i < 12; ++i) {
sum_loop += nodes[i].value;
}
cout << "sum_dfs = " << sum_dfs << " sum_loop = " << sum_loop << endl;
delete_nodes(nodes);
delete [] nodes;
return 0;
}
Я не знаю, как начать это упражнение
Решение
Я не знаком с c ++ (думаю, это то, что вы использовали), но реализация в любом случае та же самая, поэтому я могу дать вам псевдокод того, как должен выглядеть алгоритм.
create a stack where object will be stored
all nodes are not visited when we begin
push source in the stack and mark it as visited
while the stack is not empty;
go to the first adjacent node to source and if it has not been visited
mark as visited and move to its next unvisited node and so on
if at any point you reach a node that cannot visited any other unvisited node
pop the stack until you can visited an unvisited node.
Do this until the stack is empty
Ниже приведена простая реализация с использованием матрицы смежности.
void dfs(int adjacency_matrix[][], int source){
Stack<Integer> stack = new Stack<>();
int numNodes = adjacency_matrix[source].length -1;
boolean [] visited = new boolean[numNodes +1];
visited[source] = true;
stack.add(source);
while(!stack.isEmpty()){
int current = stack.peek(); // don't remove the element but get it
System.out.println("Current node being visited is "+current);
for(int x = 0; x <= numNodes; x++){
if(adjacency_matrix[current][x] == 1 && visited[x] == false){
visited[x] = true;
stack.push(x);
break;
}else if(x == numNodes){
stack.pop();
}
}
}
}
Вы можете проверить с графиком, как это
0 --- 1-------5----6--8
| \ \ | / /
| \ \ | / /
| \ \ | / /
2 3----4---7---9
0 1 2 3 4 5 6 7 8 9
---------------------
0 | 0 1 1 1 0 0 0 0 0 0
1 | 1 0 0 0 1 1 0 0 0 0
2 | 1 0 0 0 0 0 0 0 0 0
3 | 1 0 0 0 1 0 0 0 0 0
4 | 0 1 0 1 0 0 0 1 0 0
5 | 0 1 0 0 0 0 1 1 0 0
6 | 0 0 0 0 0 1 0 1 1 0
7 | 0 0 0 0 1 1 1 0 0 1
8 | 0 0 0 0 0 0 1 0 0 1
9 | 0 0 0 0 0 0 0 1 1 0
---------------------
Другие решения
Других решений пока нет …