######运行中断,无法出结果
######bfs函数用c++的queue库来实现的
######有一组样例输入输出:【样例输入】
1
6 7 0
0 3
0 4
1 4
1 5
2 3
2 4
3 5
【样例输出】
0 3 4 2 5 1
(第一行是样例数,第二行是顶点数,边数和初始起点
然后每行是连成边的顶点)
#include<iostream>
#include<queue>
using namespace std;
class graphm
{
private:
int numv, nume;
int** matrix;
int* mark;
public:
graphm(int numn)
{
init(numn);
}
void init(int n)
{
int i;
numv = n;
nume = 0;
mark = new int[n];
for (int i = 0; i < n; i++)
mark[i] = 0;
matrix = new int* [numv];
for (int i = 0; i < n; i++)
matrix[i] = new int[numv];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
matrix[i][j] = 0;
}
int n() { return numv; }
int e() { return nume; }
int first(int v)
{
for (int i = 0; i < numv; i++)
if (matrix[v][i] != 0) return i;
return numv;
}
int next(int v1, int v2)
{
for (int i = v2 + 1; i < numv; i++)
if (matrix[v1][i] != 0) return i;
return numv;
}
void setedge(int v1, int v2)
{
if (matrix[v1][v2] == 0) matrix[v1][v2] = 1;
}
int getmark(int v) { return mark[v]; }
void setmark(int v, int val)
{
mark[v] = val;
}
};
void bfs(graphm g, int start,queue<int> * Q)
{
int v, w;
Q->push(start);
g.setmark(start, 1);
cout << start << " ";
while (Q->size()!= 0)
{
v = Q->back();
Q->pop();
for (w = g.first(v); w < g.n(); w = g.next(v, w))
{
if(g.getmark(w)==0)
{
g.setmark(w, 1);
cout << w << " ";
Q->push(w);
}
}
}
}
void graphtraverse(graphm g, int v)
{
queue<int>* osh=0;
for (int i = 0; i < g.n(); i++)
g.setmark(i, 0);
if (g.getmark(v) == 0)
{
bfs(g, v,osh);
}
}
int main()
{
int a;
int n, e, s;
int v1[5000], v2[5000];
cin >> a;
for (int i = 0; i < a; i++)
{
cin >> n >> e >> s;
graphm bbh(n);
for (int j = 0; j < e; j++)
{
cin >> v1[j] >> v2[j];
bbh.setedge(v1[j], v2[j]);
}
graphtraverse(bbh, s);
}
}