建立一个有向图的邻接矩阵存储,然后在主函数中输出该二维矩阵(注意输出格式要为一个矩阵),以检验存储的正确性;再从0号顶点出发对该图进行深度优先搜索,按顺序输出所访问的顶点。
时间: 2025-01-04 07:38:24 浏览: 12
在计算机科学中,建立一个有向图的邻接矩阵是一种常见的数据结构表示法。邻接矩阵是一个二维数组,其中行代表起点,列代表终点,如果存在从某个节点i到节点j的边,则对应位置的值通常是1或者其他非零值(比如整数2、3等)。在C++中,可以这样做:
```cpp
#include <iostream>
using namespace std;
const int V = 5; // 图的顶点数
// 邻接矩阵存储,假设每个顶点最多连接V个其他顶点
bool adjMatrix[V][V] = {
{false, true, false, false, false}, // 0 -> 1 (存在)
{false, false, true, false, true}, // 1 -> 2 (存在), 1 -> 4 (存在)
{true, false, false, false, false}, // 2 -> 0 (存在)
{false, false, false, false, false}, // 3 -> ?
{false, true, false, true, false} // 4 -> 1 (存在), 4 -> 3 (存在)
};
void printAdjMatrix() {
for(int i=0; i<V; i++) {
for(int j=0; j<V; j++) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
void dfs(int vertex) {
cout << "Visiting vertex: " << vertex << endl;
// 检查并打印已访问过的顶点
// 这里只是一个示例,实际应用中需要记录并更新访问状态
for(int i=0; i<V; i++) {
if(adjMatrix[vertex][i]) {
dfs(i);
}
}
}
int main() {
printAdjMatrix(); // 输出邻接矩阵
cout << "Depth First Search starting from vertex 0:" << endl;
dfs(0);
return 0;
}
```
在这个例子中,`adjMatrix`初始化了一个5x5的邻接矩阵,并设置了几个存在的边。`printAdjMatrix`函数用于打印矩阵,`dfs`函数则实现了从0号顶点开始的深度优先搜索。运行`main`函数将首先验证邻接矩阵是否正确存储了图,然后按照顺序输出深度优先搜索过程中的顶点。
阅读全文