注:下面是以无权的图为基础的
广度优先搜索:http://blog.csdn.net/u012763794/article/details/51081830
1.问题描述
输入:
输入n个顶点,m条边, 起点的编号
跟着再输入边x,y
输出:
该起点到达各个顶点最少经过几条边(按编号从小打大输出,包括自己哦)
样例:
输入:
5 5 2
1 2
2 3
2 4
3 4
3 5
1 2
2 3
2 4
3 4
3 5
输出:
1
0
1
1
2
0
1
1
2
2.解题思路
我一开始就是觉得用广度优先搜索,结果在广度优先搜索的循环里不断改,怎么样也没成功,到了第2层就被shutdown。后来就想到用一个成员变量deep数组指针来记录他们的层数,起点就是第0层,想到了这个,刚开始还是不怎么指导如何解决,过了一天,在睡觉的时候想到了,就是当前这个节点的deep(深度,或者层数),就是上一个节点层数+1,具体看代码你就明白
3.代码实现
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
class Graph{
private:
int n;
bool *visited;
int *deep;
vector<int> *edges;
public:
Graph(int input_n){
n = input_n;
edges = new vector<int>[n];
visited = new bool[n];
memset(visited, 0, n);
deep = new int[n];
memset(deep, 0, sizeof(int)*n);
}
~Graph(){
delete[] edges;
delete[] visited;
delete[] deep;
}
void insert(int x, int y){
edges[x].push_back(y);
edges[y].push_back(x);
}
void bfs(int start_vertex){
queue<int> bfs_queue;
bfs_queue.push(start_vertex);
visited[start_vertex] = true;
while (!bfs_queue.empty()) {
//获取队首元素的编号
int vertex = bfs_queue.front();
cout<<vertex<<endl;
bfs_queue.pop();
for (vector<int>::iterator it = edges[vertex].begin(); it != edges[vertex].end(); it++ ) {
if (!visited[*it]) {
visited[*it] = true;
bfs_queue.push(*it);
}
}
}
}
void getLength(int start_vertex){
int length = 0;
bool tmp = false;
queue<int> bfs_queue;
bfs_queue.push(start_vertex);
visited[start_vertex] = true;
deep[start_vertex] = 0;
while (!bfs_queue.empty()) {
int vertex = bfs_queue.front();
bfs_queue.pop();
for (vector<int>::iterator it = edges[vertex].begin(); it != edges[vertex].end(); it++ ) {
if (!visited[*it]) {
visited[*it] = true;
deep[*it] = deep[vertex] + 1;
bfs_queue.push(*it);
}
}
tmp = false;
}
}
int getDeep(int vertex){
return deep[vertex];
}
};
int main(){
int n, m, k;
int x, y;
cin >> n >> m >> k;
Graph g(n);
for (int i = 0; i < m; ++i) {
cin >> x >> y;
g.insert(x-1, y-1);
}
g.getLength(k-1);
for (int j = 0; j < n; j++) {
cout<<g.getDeep(j)<<endl;
}
return 0;
}