C++实现树的广度搜索和深度搜索完整代码
#include <iostream>
#include <queue>
using namespace std;
struct Node { //定义表结点
int adjvex; //该边所指向的顶点的位置
Node *next; //下一条边的指针
};
struct HeadNode{ // 定义头结点
int nodeName; // 顶点信息
bool visited; //表示该结点是否被访问过
Node *link; //指向第一条依附该顶点的边的指针
};
//添加从begin-1 -> end-1的弧
void addVertex(HeadNode *G, int begin, int end) {
// 创建新的结点插入链接表
Node *node = new Node;
node->adjvex = end - 1;
//插入链接表的第一个位置
node->next = G[begin-1].link;
G[begin-1].link = node;
}
//G表示指向头结点数组的第一个结点的指针
//nodeNum表示结点个数
//arcNum表示边的个数
void createGraph(HeadNode *G, int nodeNum, int arcNum) {
cout << "开始创建图(" << nodeNum << ", " << arcNum << ")" << endl;
//初始化头结点
for (int i = 0; i < nodeNum; i++) {
G[i].nodeName = i+1; //位置0上面存储的是结点v1,依次类推
G[i].link = NULL;
}
for (int j = 0; j < arcNum; j++) {
int v1, v2;
cout << "请依次输入 边1 边2: ";
cin >> v1 >> v2;
addVertex(G, v1, v2);
addVertex(G, v2, v1);
}
}
//从标号start-1的结点开始深度搜索: 递归实现
void DFS(HeadNode *G, int start) {
G[start-1].visited = true;
Node *node = G[start-1].link;
cout << "v" << start << " ";
while (node) {
if (!G[node->adjvex].visited) {
DFS(G, node->adjvex + 1);
}
node = node->next;
}
}
//从标号start-1的结点开始广度搜索: 非递归实现
void BFS(HeadNode *G, int start) {
queue<int> q;
q.push(start);
while (!q.empty()) {
int current = q.front(); q.pop();
cout << "v" << current << " ";
G[current-1].visited = true;
Node *node = G[current-1].link;
while (node && !G[node->adjvex].visited) {
q.push(node->adjvex + 1);
node = node -> next;
}
}
}
// 初始化结点
void initVisted(HeadNode *G, int nodeNum) {
for (int i = 0; i < nodeNum; ++i) {
G[i].visited = false;
}
}
int main() {
HeadNode *G;
int nodeNum, arcNum;
cout << "请输入顶点个数，边长个数: ";
cin >> nodeNum >> arcNum;
G = new HeadNode[nodeNum];
createGraph(G, nodeNum, arcNum);
//深度搜索算法
initVisted(G, nodeNum);
cout << "深度搜索遍历序列为: ";
DFS(G, 1);
cout << endl;
//广度搜索算法
initVisted(G, nodeNum);
cout << "广度搜索遍历序列为: ";
BFS(G, 1);
cout << endl;
return 1;
}