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);
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;
}