图的广度搜索完整实现（邻接表，队列，BFS）

//构造邻接表，队列，广度优先搜索
#include<iostream>
#include<malloc.h>
#define null NULL
using namespace std;
typedef struct nd
{
int key;
struct nd * next;
}node;
typedef struct ndl
{
int count;
node * first;
}nodelist;
typedef struct l
{
int a[100];
int top;
int bottom;
}mylist;
void init(mylist *ls)
{
ls->bottom=1;
ls->top=1;
}
int insert(mylist *ls ,int i)//从底部插入
{
if(ls->top-ls->bottom>99)
{
cout<<"list is full!"<<endl;
return 0;
}
else
{
for(int j=ls->top;j>ls->bottom;j--)
{
ls->a[j]=ls->a[j-1];
}
ls->a[ls->bottom]=i;
ls->top=ls->top+1;
return 0;
}
}
int remove(mylist *ls)//删除头部，并返回值
{
if(ls->bottom==ls->top)
return 0;
else
{
return ls->a[--ls->top];
}
}
bool isempty(mylist *ls)
{
if(ls->bottom==ls->top)
return true;
else
return false;
}
int n=6;
int main()
{
nodelist nl[10];
for(int i=1;i<=n;i++)
{
nl[i].count=0;
}
//构造邻接表
nl[1].count=2;
node * n12=(node *)malloc(sizeof(node));
n12->key=2;
n12->next=null;
node *n14=(node *)malloc(sizeof(node));
n14->key=4;
n14->next=null;
nl[2].count=5;
node *n25=(node *)malloc(sizeof(node));
n25->key=5;
n25->next=null;
nl[3].count=2;
node *n36=(node *)malloc(sizeof(node));
n36->key=6;
n36->next=null;
node *n35=(node *)malloc(sizeof(node));
n35->key=5;
n35->next=null;
nl[4].count=1;
node *n42=(node *)malloc(sizeof(node));
n42->key=2;
n42->next=null;
nl[5].count=1;
node *n54=(node *)malloc(sizeof(node));
n54->key=4;
n54->next=null;
nl[6].count=1;
node *n66=(node *)malloc(sizeof(node));
n66->key=6;
n66->next=null;
nl[1].first=n12;
n12->next=n14;
nl[2].first=n25;
nl[3].first=n36;
n36->next=n35;
nl[4].first=n42;
nl[5].first=n54;
nl[6].first=n66;
//队列
mylist ls;
init(&ls);
int p[10]={0};
int color[10]={0};//0=white,1=gray,2=black
int d[10]={100};
color[1]=1;
d[1]=0;
cout<<1<<' ';
insert(&ls,1);
while(!isempty(&ls))
{
int u=remove(&ls);
node *q=nl[u].first;
while(q!=null)
{
if(!color[q->key])
{
color[q->key]=1;
d[q->key]=d[u]+1;
p[q->key]=u;
cout<<q->key<<' ';
insert(&ls,q->key);
}
q=q->next;
}
color[u]=2;
}
cout<<endl;
return 0;
}

最后

以上就是彪壮白羊为你收集整理的图的广度搜索完整实现（邻接表，队列，BFS）的全部内容，希望文章能够帮你解决图的广度搜索完整实现（邻接表，队列，BFS）所遇到的程序开发问题。

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