C++实现广度优先遍历图
本文实例为大家分享了C++实现广度优先遍历图的具体代码，供大家参考，具体内容如下
广度优先遍历
void bfs(int start, int parent[], int dist[], int seen[], int visited[]) {
std::queue <int> q;//建立数据队列q
int v;
q.push(start); //让开始序列入栈
parent[start] = start; // 开始节点的父节点是开始节点
dist[start] = 0; // 初始化距离向量为-1
seen[start] = 1;
while(!q.empty()) { //如果队列非空
v = q.front(); q.pop(); //令V是队列的最前端，并将其出栈
if(visited[v]) // 如果visited[v]=1, continue.
continue;
visited[v] = 1; //否则令visited[v]=1
std::cout << v << '\n';//输出显示当前节点
// 遍历v的所有相邻节点
for(int i = 0; i < graph[v].size(); i++) {
// 如果v的第i个相邻节点的i并没有访问过
if(!visited[graph[v][i]]) {
// 如果这个没有访问过的节点没有被看过
if(!seen[graph[v][i]]) {
//压入栈，距离+1，设置父节点
q.push(graph[v][i]);
dist[graph[v][i]] = 1 + dist[v];
parent[graph[v][i]] = v;
// 如果已经访问过，令seen=1.
seen[graph[v][i]] = 1;
}
}
else {
// 如果节点已经被访问了，选择距离最小的
if(dist[v] + 1 < dist[graph[v][i]]) {
dist[graph[v][i]] = 1 + dist[graph[v][i]];
parent[graph[v][i]] = v;
}
}
}
}
}
主函数
int main() {
int n = 8; // 图中的节点数
graph = std::vector <std::vector <int> > (n);
// 图的邻接表
graph[0] = {1, 2};
graph[1] = {0, 2, 3};
graph[2] = {0, 1, 5, 6};
graph[3] = {1, 2, 4};
graph[4] = {3};
graph[5] = {2};
graph[6] = {2, 7};
graph[7] = {6};
/* - parent[i] = parent of 'i' in BFS traversal.
- dist[i] = 从开始到I节点的最短距离shortest distance of 'i' from 'start'.
- If seen[i] == 1, 节点i已经进入过队列'i' has entered the queue once
- If visited[i] == 1, 节点i已经进入队列，并且所有相邻节点都已经进入过队列
*/
int parent[n+1], dist[n+1], seen[n+1], visited[n+1];
memset(parent, -1, sizeof(parent));//父节点初始化为-1
memset(dist, -1, sizeof(dist));//距离向量初始化为-1
memset(seen, 0, sizeof(seen));
memset(visited, 0, sizeof(visited));//seen用于判断该节点是否访问过
int start = 0; // 开始节点
bfs(start, parent, dist, seen, visited);
return 0;
}
