时间戳

首页 > 解决方案 > 如何计算图中所有节点的总和？

graph - 如何计算图中所有节点的总和？

问题描述

我是 DFS 的新手，在尝试在 DFS 上做某事时，我尝试自己编写一个程序。这个想法是计算以节点 1 为根的子树的所有节点的总和。这个想法是创建一个函数 dfs(node) 以便它存储以“节点”为根的子树的节点的值的总和. 当 parent==child 时，我确保循环停止（否则将出现无限递归）。

然而，该程序无法编译。

代码（Ideone：https ://ideone.com/ntS9AG ）：

#include<bits/stdc++.h>
using namespace std;
#define ff(i,ii,jj) for(int i=ii; i<=jj; i++)

    int n;
    int val[10000];
    vector<int> adj(10000); // adj.size() compiles correctly when adj[10000] is written; won't that create columns instead of rows?
    int sum[10000];
    bool visited[10000];

    void dfs(int node)
    {

        if (!visited[node])
        {
            sum[node]+=val[node];
            visited[node]=true;
            for (int i=0; i<adj[node].size(); i++)
            {
                if (!visited[adj[node][i]]) {visited[adj[node][i]]=true; dfs(adj[node][i]); sum[node]+=sum[adj[node][i]];}
            }
        }
    }

int main()
{
    memset(sum,0,sizeof(sum));
    memset(visited, false, sizeof(visited));
    cin>>n;
    for (int i=1; i<=n-1; i++) {int x,y; cin>>x>>y; adj[x].push_back[y]; adj[y].push_back[x];}
    for (int i=1; i<=n; i++) cin>>val[i];
    dfs(1);

    cout<<sum[1];
}

PS：这个程序只是在 DFS 上写一些东西，因此我尝试进行递归。我当然知道我可以只总结输入值。

标签： graph

解决方案

vector<int> v(n) 创建一个大小为 n 的向量。基本上你有一个向量。

但是，当您编写 vector<int> v[n] 时，它会生成n 个向量，这是您在尝试实现邻接列表时应该做的事情。

考虑这张图： 定向加夫

因此，为此，您的邻接列表看起来像 

0 -> 2,3  
1 -> 0  
2 -> 1  
3 -> 4  
4 -> 0

很明显，你可以看到你需要 5 个向量来使用邻接表来存储这个图。这就是为什么您需要以另一种方式定义图表的原因。（你在评论中写的方式）。

推荐阅读