c++ - 测试图是否是树

Question

在输入规范中，给出了 N 个节点数和 M 个边数。所以第一个简单的检查是 M 应该等于 N-1 否则它就不可能是一棵树。

我接下来做的只是一个 DFS，我在其中看到在 DFS 期间我们是否再次遇到一个访问过的节点(与父节点不同，父节点我指的是调用了下一个 dfs 的节点与它相邻的节点)那么这意味着我们有一个循环并且它不是一棵树。但显然我的解决方案不断得到错误的答案。我发布了代码，但只发布了重要的片段。我将图形存储为邻接列表，并发布函数 isTree() 来测试它是否是树？正确的逻辑是什么？

#include <iostream>
#include <list> 
using namespace std;

    // Graph class represents a directed graph using adjacency list representation
class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // Pointer to an array containing adjacency lists
    bool isTreeUtil(int v, bool visited[],int parent);
public:
    Graph(int V);   // Constructor
    void addEdge(int v, int w);   // function to add an edge to graph
    bool isTree();   // Tells whether the given graph is a tree or not
    void printGraph();
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V+1];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
    adj[w].push_back(v);
}

bool Graph::isTreeUtil(int v, bool visited[],int parent)
{
    //int s_v = v;
    visited[v] = true;
    list<int>::iterator i;
    for(i = adj[v].begin(); i != adj[v].end(); ++i) {
        if (!visited[*i])
            isTreeUtil(*i,visited,v);
        else {
            if (*i != parent && visited[*i])
                return false;
        }
    }

    return true;
 }

bool Graph::isTree() {
    bool *visited = new bool[V+1];
    for(int i = 1; i < V+1; i++)
        visited[i] = false;

    visited[1] = true;  // marking the first node as visited
    for(int i = 1; i < V+1; i++)
        visited[i] = false;
    int parent = -1;   // initially it has no parent
    //list<int> :: iterator i;
    //for (i = adj[v].begin(); i != adj[v].end(); ++i)
    return isTreeUtil(1, visited, parent);
}

void Graph::printGraph() {
    for (int i = 1;i <= this->V; i++) {
        cout << i << "->";
        list<int>::iterator j;
        for (j = adj[i].begin(); j != adj[i].end(); ++j) {
            cout << *j << "->";
        }
        cout << "\n";
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    Graph G(N);
    int v, w;
    int m = 0;
    while (m < M) {
        cin >> v >> w;
        G.addEdge(v,w);
        m++;
    }

    if (M != N-1) {
        cout << "NO\n";
    else if (G.isTree())
        cout << "YES\n";
    else
        cout << "NO\n"; 
}

Answer 1

我把你的代码编译好，然后在我的机器上运行了。实现图形时，需要考虑一些重要的规范。当您选择遵守规范时，通常最好在代码中强制执行该规范。

已经很清楚该图具有 2 向边，但具体提及这一点也无妨。

允许重复边吗？您的程序允许我制作边缘 (1,2)，然后制作另一条边缘 (1,2)，并将其计为 2 条边缘。这使您的条件 M != N-1 成为不充分的检查。要么禁止重复边，要么在你的算法中考虑它们(目前，重复边会导致你的算法错误地返回)。

self 边缘？您的图形是否允许顶点对自身有边？如果是这样，自路径是否应该使树无效(也许自循环是合法的，因为在树中，每个节点都可以访问自己)？目前，self edges 也会破坏你的算法。

为了帮助您，这里是我修改后的 addEdge() 实现，它不允许重复边并不允许自循环。作为奖励，它还检查数组边界；)请注意额外的包含和函数签名的更改(它现在返回一个 bool 值)。

#include <algorithm>

bool Graph::addEdge(int v, int w)
{
    // sanity check to keep us from seg faulting
    if (v < 1 || v > this->V || w < 1 || w > this->V) {
        return false;
    }
    // no self-edges
    if (w == v) {
        return false;
    }
    // no duplicate edges allowed either
    std::list<int>::iterator findV = std::find(adj[v].begin(), adj[v].end(), w);
    std::list<int>::iterator findW = std::find(adj[w].begin(), adj[w].end(), v);
    if (findV != adj[v].end() || findW != adj[w].end()) {
        return false;
    }

    adj[v].push_back(w); // Add w to v’s list.
    adj[w].push_back(v);
    return true;
}

希望对您有所帮助。如果这是一项作业，您应该复习这篇文章。如果您的实现是自动评分的，他们必须指定这些案例。正如@congusbongus 提到的，您的算法在节点断开连接的情况下也会失败。

请注意，您还必须修改 main() 方法才能使我的实现正常工作。更改这部分功能:

while (m < M) {
    cout << "Create Edge from x to y" << endl;
    cin >> v >> w;
    if (!G.addEdge(v,w)) {
        cout << ">>Invalid edge not added" << endl;
    } else {
        cout << ">>Successfully added edge" << endl;
        m++;
    }
}