C++实现树的广度搜索和深度搜索完整代码.doc

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.03M 资料格式：doc 举报版权申诉

laizhenghong2012-7404333-4744300845368228686.doc.pdf-第1页.png

第1页 / 共3页

laizhenghong2012-7404333-4744300845368228686.doc.pdf-第2页.png

第2页 / 共3页

laizhenghong2012-7404333-4744300845368228686.doc.pdf-第3页.png

第3页 / 共3页

C++实现树的广度搜索和深度搜索完整代码

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

C++实现树的广度搜索和深度搜索完整代码 } } //从标号 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 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; 2

C++实现树的广度搜索和深度搜索完整代码 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; } 3

分享到：

赞收藏

资料库

C++实现树的广度搜索和深度搜索完整代码.doc

相关推荐

开发技术

热门标签

最新资料