bfs(无向不带长度且正向)
2018-03-08 本文已影响0人
laochonger
bfd适用于所有边的加权值相同的情况下
void dfs(int cur,int dis){
queue<int>q;
int road[100];
road[q.front()] = -1;
q.push(cur);
book[1] = 1;
int flag = 0;
while(!q.empty()){
for(int i = 1; i <= n; i++){
if(a[q.front()][i] == 1 && book[i] == 0){
q.push(i);
book[i] = 1;
road[i] = q.front();
}
if(q.back() == dis){//这里是back(),即新入队的
flag = 1;
break;
}
}
if(flag == 1) break;
q.pop();
}
for(int i = q.back(); road[i] != -1; i = road[i]){//链表(但是我不会双端所以倒序,可以用一个额外的数组进正序输出)
printf("%d<--");
}
printf("%d", cur);
}