C++达成树的广度搜索和深度搜索完整代码
发布时间：2021-11-22 09:24:49 所属栏目：PHP教程 来源：互联网
导读：C++实现树的广度搜索和深度搜索完整代码 #include iostream #include queue using namespace std; struct Node { //定义表结点 int adjvex; //该边所指向的顶点的位置 Node *next; //下一条边的指针 }; struct HeadNode{ // 定义头结点 int nodeName; // 顶
|
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; }  （编辑：应用网_丽江站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330468号