在Windows7 64位+VS2015上运行求解AOE网关键路径的算法,邻接表表示的AOE网提示网中有回路,邻接矩阵表示的AOE网显示正确的信息?使用的算法是一样的,两种方法的相关类的接口函数也一致,为什么会出现这种问题?

Question

百度云盘上的相关工程链接

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

这个问题是由于邻接矩阵和邻接表表示的网络在某些情况下可能会出现不匹配的情况。例如，在你的示例中，邻接矩阵表示的网络有一个回路（即边从节点A到节点B），而邻接表表示的网络没有回路。

解决这个问题的方法之一是在使用邻接矩阵时确保它是一个无环的图。你可以通过添加一个标记来识别环，并在计算关键路径时检查这些环的存在。另一种方法是只使用邻接表表示网络，因为邻接表不会包含任何回路。

以下是一个使用邻接矩阵的例子：

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int id;
    vector<Node*> neighbors;
};

class Graph {
public:
    Graph(int V) : vertices(V), adjacency_matrix(V, vector<int>(V, 0)) {}

    void addEdge(int u, int v) {
        adjacency_matrix[u][v] = 1; // Add an edge between node u and node v.
        adjacency_matrix[v][u] = 1; // And the same for the reverse direction.
    }

    bool isAcyclic() {
        int n = vertices;
        vector<bool> visited(n, false);
        vector<bool> recStack(n, false);

        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                if (!dfs(i, visited, recStack))
                    return false;
            }
        }

        return true;
    }

private:
    vector<Node> vertices;
    vector<vector<int>> adjacency_matrix;
};

bool dfs(int vertex, vector<bool>& visited, vector<bool>& recStack) {
    visited[vertex] = true;
    recStack[vertex] = true;

    for (Node* neighbor : vertices[vertex].neighbors) {
        if (neighbor->id == vertex) continue; // Skip self-loops.
        if (!visited[neighbor->id])
            if (!dfs(neighbor->id, visited, recStack)) return false;
        else if (recStack[neighbor->id]) return false; // Cycle detected.
    }

    recStack[vertex] = false;
    return true;
}

int main() {
    Graph graph(4); // Create a graph with 4 nodes.
    graph.addEdge(0, 1);
    graph.addEdge(1, 2);
    graph.addEdge(2, 0);
    graph.addEdge(2, 3);
    graph.addEdge(3, 3); // This is an invalid edge.

    if (graph.isAcyclic()) {
        cout << "Graph is acyclic." << endl;
    } else {
        cout << "Graph contains a cycle." << endl;
    }

    return 0;
}

在这个例子中，我们创建了一个具有四个顶点的图，并添加了两个错误的边以模拟循环。然后我们调用isAcyclic()函数来检查这个图是否是无环的。如果返回值为true，那么我们就知道这个图是无环的；否则，我们将输出“Graph contains a cycle。”的警告消息。

请注意，这个例子中的循环是通过添加一个无效边实现的。在实际应用中，你需要根据具体情况来决定如何处理这样的问题。