本文主要是介绍广度优先搜索算法(Breadth-First Search , BFS)---解决最短路径问题算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言:广度优先搜索可回答两类问题,
- 从节点A触发,有前往节点B的路径吗?
- 从节点A触发,前往节点B的哪条路径最短?
如上图所示,我们需要从You的关系网找到海澜,我们先从一级关系网中搜索,如果一级没有再向外扩展一圈到二级,依次类推,直到搜索所有人或者搜到目标为止。
示例代码
using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;public class BreadthFirstSearchAlgorithm : MonoBehaviour
{private static Dictionary<string, string[]> graph = new Dictionary<string, string[]>();void Start(){graph.Add("You", new[] { "A0", "A1", "A2" });graph.Add("A1", new[] { "A3", "A4" });graph.Add("A0", new[] { "A4" });graph.Add("A2", new[] { "A5", "A6" });graph.Add("A3", Array.Empty<string>());graph.Add("A4", Array.Empty<string>());graph.Add("A5", Array.Empty<string>());graph.Add("A6", new[] { "A5", "海澜" });Search("You");}private static bool Search(string name){var searchQueue = new Queue<string>(graph[name]); //需要搜索的队列var searched = new List<string>(); //已经搜索过的人物列表,防止循环引用的搜索while (searchQueue.Any()) //如果列表不为空就一直搜索{var person = searchQueue.Dequeue();if (!searched.Contains(person)){if (PersonIsHaiLan(person)){Debug.Log($"{person} 是需要找到的人");return true;}else{var newSearchQueue = searchQueue.Concat(graph[person]); //将此人的所有直接联系人(一级)添加到待搜索的列表searchQueue = new Queue<string>(newSearchQueue);searched.Add(person); //已经搜索的人添加到列表中,防止循环引用搜索 }}}return false;}private static bool PersonIsHaiLan(string name){return name.Equals("海澜");}}
这篇关于广度优先搜索算法(Breadth-First Search , BFS)---解决最短路径问题算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!