C++计算图任意两点间的所有路径

问题描述：

给定一个无向图，每个节点之间存在多条路径。设计并实现一个C++程序，可以计算图中任意两个节点之间的所有路径。

解决方案：

为了解决这个问题，我们将使用深度优先搜索（DFS）算法来遍历图，并找到所有从起始节点到目标节点的路径。

首先，我们需要定义图的数据结构。我们可以使用邻接矩阵来表示图，其中矩阵元素的值表示两个节点之间是否存在边。我们可以通过二维数组来实现邻接矩阵：

const int MAX_NODES = 100;  // 最大节点数
int graph[MAX_NODES][MAX_NODES];  // 邻接矩阵

// 初始化邻接矩阵
void initGraph() {
    for (int i = 0; i < MAX_NODES; i++) {
        for (int j = 0; j < MAX_NODES; j++) {
            graph[i][j] = 0;  // 初始化所有元素为0
        }
    }
}

接下来，我们需要实现DFS算法来找到所有路径。我们可以使用递归来实现DFS：

bool visited[MAX_NODES];  // 标记节点是否已访问

// DFS函数
void dfs(int start, int target, vector& path, vector>& allPaths) {
    visited[start] = true;
    path.push_back(start);
    
    if (start == target) {
        // 已到达目标节点，将当前路径保存到结果集中
        allPaths.push_back(path);
    } else {
        // 继续遍历邻接节点
        for (int i = 0; i < MAX_NODES; i++) {
            if (graph[start][i] && !visited[i]) {
                dfs(i, target, path, allPaths);
            }
        }
    }
    
    path.pop_back();
    visited[start] = false;
}

最后，我们可以将以上代码组合起来，提供一个函数来计算任意两个节点之间的所有路径：

vector> findAllPaths(int start, int target) {
    vector path;  // 当前路径
    vector> allPaths;  // 所有路径
    
    // 初始化visited数组
    memset(visited, false, sizeof(visited));
    
    // 开始搜索路径
    dfs(start, target, path, allPaths);
    
    return allPaths;
}

总结：

通过使用深度优先搜索算法，我们可以找到图中任意两个节点之间的所有路径。首先，我们定义了一个邻接矩阵来表示图的结构，然后使用DFS算法来遍历图，找到所有从起始节点到目标节点的路径。最后，我们提供了一个函数来调用上述逻辑，并返回结果集。