无向图上的 DFS

Question

我有一个大学练习，我必须在无向图上为运行编写 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;

}

我不知道如何开始这个练习

Answer 1

我不熟悉 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
          ---------------------

无向图上的 DFS

DFS on undirected graph

c++

nodes

depth-first-search

undirected-graph