Sicily 图的广度优先搜索

本文主要是介绍Sicily 图的广度优先搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Source:

http://soj.sysu.edu.cn/show_problem.php?pid=1000&cid=2104

Description

读入图的邻接矩阵以及一个顶点的编号（图中顶点的编号为从1开始的连续正整数。顶点在邻接矩阵的行和列上按编号递增的顺序排列。邻接矩阵中元素值为1，表示对应顶点间有一条边，元素值为0，表示对应顶点间没有边），输出从该顶点开始进行广度优先搜索（Breadth-First Search, BFS）的顶点访问序列。假设顶点数目<=100，并且，对于同一顶点的多个邻接顶点，按照顶点编号从小到大的顺序进行搜索。

Sample Input

第一行为两个整数n和s (0

4 3
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

Sample Output

一行（行末没有换行符），表示从顶点s开始进行BFS的顶点访问序列，相邻顶点间用一个空格间隔。

3 1 2 4

Caution:

水题。

示例代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include <vector>using namespace std;int g[101][101],vis[101];
int n, s;void bfs()
{vis[s] = 1;queue<int> q;q.push(s);while (!q.empty()){for (int i = 1; i <= n; ++i)if (g[q.front()][i] == 1 && !vis[i]){q.push(i);vis[i] = 1;}cout << q.front() << " ";q.pop();}
}int main()
{cin >> n >> s;for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)cin >> g[i][j];bfs();return 0;
}     

这篇关于Sicily 图的广度优先搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---