C++实现树的广度搜索和深度搜索完整代码
C++实现树的广度搜索和深度搜索完整代码
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);
1
评论0