请编写以下子函数,并在主函数中分别调用。请统一提交一个cpp文件。 子函数1:邻接矩阵法建立无向图 子函数2:邻接矩阵法建立有向图 子函数3:邻接表法建立无向图 子函数4:邻接表法建立有向图 子函数5:深度优先遍历图(递归方法) 子函数6:广度优先遍历图(必须使用队列辅助)
时间: 2024-12-09 21:25:44 浏览: 13
```cpp
#include <iostream>
#include <vector>
#include <queue>
// 子函数1:邻接矩阵法建立无向图
void createAdjMatrixUndirectedGraph(int numVertices, std::vector<std::vector<int>>& adjMatrix) {
for (int i = 0; i < numVertices; ++i) {
for (int j = 0; j < numVertices; ++j) {
if (i != j) {
adjMatrix[i][j] = adjMatrix[j][i] = 0; // 初始化为0表示无边
}
}
}
// 添加边的功能需根据具体需求实现
}
// 子函数2:邻接矩阵法建立有向图
void createAdjMatrixDirectedGraph(int numVertices, std::vector<std::vector<int>>& adjMatrix) {
for (int i = 0; i < numVertices; ++i) {
for (int j = 0; j < numVertices; ++j) {
adjMatrix[i][j] = 0; // 初始化为0表示无从i到j的边
}
}
// 根据需要添加从i到j的边
}
// 子函数3:邻接表法建立无向图
void createAdjListUndirectedGraph(std::vector<std::list<int>>& adjList, int numVertices) {
for (int i = 0; i < numVertices; ++i) {
adjList[i].clear(); // 清空列表
}
// 添加边时将两端节点都加入对方的邻接列表
}
// 子函数4:邻接表法建立有向图
void createAdjListDirectedGraph(std::vector<std::list<int>>& adjList, int numVertices) {
for (int i = 0; i < numVertices; ++i) {
adjList[i].clear();
}
// 只需在源节点添加目标节点即可
}
// 子函数5:深度优先遍历图(递归方法)
bool dfsRecursion(const int& startNode, const std::vector<bool>& visited, const std::vector<std::vector<int>>& adjMatrix) {
// 实现DFS递归代码...
}
// 子函数6:广度优先遍历图(必须使用队列辅助)
bool bfsQueue(const int& startNode, const std::vector<bool>& visited, std::vector<std::list<int>>& adjList) {
// 实现BFS队列代码...
}
// 主函数
int main() {
int vertices;
std::cout << "请输入顶点数:";
std::cin >> vertices;
// 创建相应的数据结构
std::vector<std::vector<int>> adjMatrixUndirected;
std::vector<std::vector<int>> adjMatrixDirected;
std::vector<std::list<int>> adjListUndirected(vertices);
std::vector<std::list<int>> adjListDirected(vertices);
// 调用子函数构建图
createAdjMatrixUndirectedGraph(vertices, adjMatrixUndirected);
createAdjMatrixDirectedGraph(vertices, adjMatrixDirected);
createAdjListUndirectedGraph(adjListUndirected, vertices);
createAdjListDirectedGraph(adjListDirected, vertices);
// 调用遍历函数
bool result = dfsRecursion(0, {false} * vertices, adjMatrixUndirected); // 示例:无向图DFS
result |= bfsQueue(0, {false} * vertices, adjListDirected); // 示例:有向图BFS
return 0;
}
```
在这个示例中,我提供了一些基本的函数声明和部分主函数实现。你需要完成`dfsRecursion`和`bfsQueue`函数的具体实现,以及在主函数中调用它们的部分。记得根据实际需求修改邻接结构体的创建以及遍历函数的内容。
阅读全文