广度优先搜索BFS——图邻接表表示
BFS是图的另一个重要算法，下面是基于邻接表表示的BFS算法。
/*图邻接表表示BFSinput:17A 1 5B 2 4 3C 2 4 2D 3 6 5 2E 3 7 4 1F 1 4G 1 5output:A E D G B F C*/#include<iostream>#include<cstring>#include<queue>using namespace std;struct LinkNode{ //相邻结点 int vex; LinkNode *next;};struct Graph{ //图邻接表表示 char data; LinkNode *head;};void Create(Graph G[],int n){ //创建图的邻接表 int i,j,m; LinkNode *p; for(i=1; i<=n; i++){ cin>>G[i].data; G[i].head = NULL; cin>>m; for(j=1; j<=m;j++){ p = new LinkNode; cin>>p->vex; p->next = G[i].head; G[i].head = p; } }}void BFS(Graph G[],int vex,bool visited[]){ //图的邻接表表示BFS queue<int> q; LinkNode *p; q.push(vex); while(!q.empty()){ int temp = q.front(); q.pop(); if(!visited[temp]){ visited[temp] = true; cout<<G[temp].data<<' '; p = G[temp].head; while(p != NULL){ if(!visited[p->vex])q.push(p->vex); p = p->next; } } }}int main(){ int t,n; Graph *G = NULL; bool *visited = NULL; 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,visited); cout<<endl; } return 0;}