-2

我有一个大学练习，我必须编写一个 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;

}

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

4

1 回答 1

2

我不熟悉 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
          ---------------------
于 2015-12-09T04:30:07.790 回答