广度优先搜索BFS——图邻接矩阵表示
这个是基于邻接矩阵的BFS图算法。
/*图邻接矩阵表示DFSinput:17A 0 0 0 0 1 0 0B 0 0 1 1 0 0 0C 0 1 0 1 0 0 0D 0 1 0 0 1 1 0E 1 0 0 1 0 0 1F 0 0 0 1 0 0 0G 0 0 0 0 1 0 0output:A E D G B F C*/#include<iostream>#include<cstring>#include<queue>using namespace std;struct Graph{ //图邻接矩阵表示 char data; bool *adjacency;};void Create(Graph G[],int n){ //创建图邻接矩阵表示 int i,j; for(i=1; i<=n; i++){ cin>>G[i].data; G[i].adjacency = new bool[n]; for(j=1; j<=n; j++)cin>>G[i].adjacency[j]; }}void BFS(Graph G[],int vex,int n,bool visited[]){ //图邻接矩阵BFS queue<int> q; int temp,i; q.push(vex); while(!q.empty()){ temp = q.front(); q.pop(); if(!visited[temp]){ visited[temp] = true; cout<<G[temp].data<<' '; for(i=1; i<=n; i++){ if(!visited[i] && G[temp].adjacency[i]) q.push(i); } } }}int main(){ Graph *G; bool *visited; int t,n; cin>>t; while(t--){ cin>>n; G = new Graph[n]; visited = new bool[n]; memset(visited,0,sizeof(visited)); Create(G,n); BFS(G,1,n,visited); cout<<endl; } return 0;}