代码部分参考https://blog.csdn.net/qq_36525906/article/details/77387717
#include<iostream> #include<queue> using namespace std; int adj(int*visit, int**a, int n, int v)//获取相邻的点的下标，如果无相邻节点，或者已经访问了则返回-1 { for (int i = 0; i < n; i++) { if (a[v][i] == 1 && !visit[i]) return i; } return -1; } void Visit(int v,int*visit,int**a,int n) { cout << v << ' '; visit[v] = 1;//设置为已经访问 int Adj = adj(visit, a, n, v);//获取v的邻接点 while (Adj != -1)//如果可以找到 { Visit(Adj, visit, a, n);//不断递归，直到撞到“南墙” Adj = adj(visit,a,n,v);//如果撞到，则回溯，寻找当前节点的下一个邻接点 } } void DFS(int*visit, int n, int**a)//递归实现，visit数组存放是否访问，n为顶点数，a为邻接矩阵 { int i, j; for (i = 0; i < n; i++) { if (!visit[i]) Visit(i, visit, a, n); } } //------------------------以下为BFS算法 void Visit2(int v, int*visit, int**a, int n) { queue<int>que; cout << v << ' '; visit[v] = 1; que.push(v);//将已经遍历的数据放入队列 while (!que.empty()) { int temp = que.front(); int Adj=adj(visit,a,n,temp); que.pop();//每次将队首出列，遍历其相邻顶点 while (Adj != -1) { visit[Adj] = 1; que.push(Adj); cout << Adj << ' '; Adj = adj(visit, a, n, temp);//将该顶点的最近相邻顶点全部遍历，再遍历下一个节点 } } } void BFS(int*visit, int n, int**a) { for (int i = 0; i < n; i++) { if (!visit[i]) Visit2(i, visit, a, n); } } int main() { int n,i,j,x; cout << "input n verticles\n"; cin >> n; int**a = new int*[n]; for (i = 0; i < n; i++) a[i] = new int[n]; for (i = 0; i < n; i++)//用邻接表的方法创造图 { for (j = 0; j < n; j++) { cin >> a[i][j]; } } int*visit = new int[n]; memset(visit, 0, n*sizeof(visit));//默认为0，设置为未访问，并且由于是指针，需要用n乘 BFS(visit, n, a); }