无标题.png
捕获.PNG
如图用数组保存该无向图，输入时需要输入双向。与之前的dfs不同，单纯地遍历该图不需要找到最短路，也就不需要恢复标记
用数组保存图，数组中1表示可以连通，max表示不能，0表示本身
dfs：
book[1] = 1; //这一步很重要，否则会发生循环
void dfs(int cur){//cur是当前所在点
pritnf("%d", cur);//打印该点
sum++;
if(sum == n) return ;
for(int i = 1; i <- n; i++){
if(e[cur][i] == 1 && book[i] == 0){
book[i] = 1;//标记i而非e[cur][i] 标记i后不会再走回e[i][x]，因为每个元素只需遍历到一次，若用二维数组则需标记正反 i x ， x i， 且会发生重复遍历，比如3-->2-->4-->3
dfs(i);
}
}
return ;
}
遍历的顺序： 1 2 3 5 4（因为4是2的枝节，需要回溯后才能遍历到）
bfs：
void bfs(){
queue<int>q;
q.push(1);
book[1] = 1;
while(!q.empty()){
for(int i = 1; i <= n; i++){
if(e[q.front()][i] == 1 && book[i] == 0){
q.push(i);
sum++;
book[i];
}
}
if(sum == n) break;
q.pop(); //一般将出队放在最后
}
}
遍历的顺序： 1 2 3 5 4
