C++实现广度优先遍历图

 void bfs(int start, int parent[], int dist[], int seen[], int visited[]) { std::queue  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(gra<strong style="color:transparent">来源gaodai#ma#com搞@代~码网</strong>ph[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  > (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; }