广度优先搜索BFS——图邻接表表示

BFS是图的另一个重要算法，下面是基于邻接表表示的BFS算法。

/*
图邻接表表示BFS
input:
1
7
A 1 5
B 2 4 3
C 2 4 2
D 3 6 5 2
E 3 7 4 1
F 1 4
G 1 5
output:
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;
}

最后

以上就是阳光抽屉为你收集整理的广度优先搜索BFS——图邻接表表示的全部内容，希望文章能够帮你解决广度优先搜索BFS——图邻接表表示所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。