C语言实现图的广度遍历

2021年6月29日 1点热度 0条评论 来源: 平先森

广度优先:类似树的层序遍历,与树一样也需要使用队列配合,将一个结点的出度全部遍历一遍,然后换下个点,遍历过的点不便利,直到所有点遍历完成,广度优先遍历就是遍历结点的出度,和深度优先遍历一样,序列不唯一。
在这里插入代码片

//广度优先遍历 
void bfs_ergodic(Graph* gra) 
{ 
	int h=0;
	Queue* queue = creat_queue();
	bool flag[gra->size];
	for(int i=0;i<gra->size;i++) 
	flag[i] = false; 
	push_queue(queue,h); 
		while(!empty_queue(queue))
		{  
			int k = *head_queue(queue); 
			if(!flag[k])
			printf("%c ",gra->verter[k]); 
			flag[k] = true;
			for(int l=0;l<gra->size;l++)
			{ 
				if(gra->edge[k][l]&&!flag[l]) 
				push_queue(queue,l);
			} 
			pop_queue(queue);
        } 
		for(int i=0;i<gra->size;i++) 
		{  
        	if(!flag[i])
			{ 
				printf("%C ",gra->verter[i]);
			}
		}
}

将一个节点入队,然后将与其相连的所有节点入队,然后将这个节点出队并显示,并将他的flag置为true,防止重复遍历,然后将与队头相连的节点入队,将队头再次出队,遍历数组长度次

    原文作者:平先森
    原文地址: https://blog.csdn.net/weixin_43698703/article/details/98660839
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。