首发于 算法入门笔记
切换模式
算法——广度优先搜索
刘昴星
建筑信息化
概念：
"广度优先搜索"是一种通过逐层遍历所有访问对象，从而找到通过最短节点数到达目标的算法。
学习准备：
学习前，需要先掌握图（Graph）、队列（queue）、栈（stack）的概念。还得了解“邻接矩阵”的用法。
示例：
在下图（graph）中，找到从A点到H点的最短距离。
广度优先算法的搜索方式：通过逐层遍历所有相邻节点，从而暴力的找出最短路径。如下图：
代码演示：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;//调用queue的时候需要该名称空间
namespace 广度优先搜索
{
class nodeClass
{
public string nodeName;
public bool isVisited;
public nodeClass(string name)//类的构造器
{
nodeName = name;
}
}
class Gragh
{
const int nodeNumMax = 10;
nodeClass[] nodes = new nodeClass[nodeNumMax];//节点数组
int[,] adjmatrix = new int[nodeNumMax, nodeNumMax];
int nodeNumNow = 0;//统计当前有几个节点数
public Gragh()//利用类构造器的优先机制，首先初始化图的关系矩阵
{
for (int i = 0; i < nodeNumMax; i++)
{
for (int j = 0; j < nodeNumMax; j++)
{
adjmatrix[i, j] = 0;
}
}
}
public void addNode(string newNodeName)
{
nodes[nodeNumNow] = new nodeClass(newNodeName);
nodeNumNow++;
}
public void addEdge(int nodeNum1, int nodeNum2)
{
adjmatrix[nodeNum1, nodeNum2] = 1;
}
public void displayNode(int nodePosition)
{
Console.WriteLine(nodes[nodePosition].nodeName);
}
public int visiteNode(int oneNode)//检查某节点是否还有未访问过的相邻节点。
{
for (int j = 0; j < nodeNumMax; j++)
{
if (adjmatrix[oneNode, j] == 1 && nodes[j].isVisited == false)
return j;
}
return -1;
}
public void 广度优先搜索()
{
//创建队列，以方便实现自动搜索。
Queue nodeQueue = new Queue();
//访问第一个节点
nodes[0].isVisited = true;
displayNode(0);
nodeQueue.Enqueue(0);
//访问之后的节点
int node1;
int node2;
while (nodeQueue.Count > 0 && nodes[nodeNumNow - 1].isVisited != true)//除了判断节点以外，新加了一个判断，当最后一个节点被访问了以后，整个循环就停止
{
node1 = (int)nodeQueue.Dequeue();//将队列中的第一个节点弹出，并记录。
node2 = visiteNode(node1);//寻找节点1指向的节点。
while (node2 != -1 && nodes[nodeNumNow - 1].isVisited != true)
{
Console.WriteLine(nodes[node1].nodeName + "=>" + nodes[node2].nodeName);//显示哪个节点指向哪个节点。
//广度优先搜索，首先就是把与第一个点相邻的点全部找出来，储存在queue里面。
nodeQueue.Enqueue(node2);
nodes[node2].isVisited = true;
displayNode(node2);
node2 = visiteNode(node1);
}
}
}
//重置所有被访问过的节点
public void resetNode()
{
for (int i = 0; i < nodeNumMax; i++)
{
nodes[i].isVisited = false;
}
}
}
class Program
{
static void Main(string[] args)
{
Gragh graphInstance = new Gragh();
//添加节点
graphInstance.addNode("A");//编号0
graphInstance.addNode("B");//编号1
graphInstance.addNode("C");//编号2
graphInstance.addNode("E");//编号3
graphInstance.addNode("D");//编号4
graphInstance.addNode("F");//编号5
graphInstance.addNode("G");//编号6
graphInstance.addNode("H");//编号7
//添加边
graphInstance.addEdge(0, 1);//A=>B
graphInstance.addEdge(0, 2);//A=>C
graphInstance.addEdge(1, 4);//B=>D
graphInstance.addEdge(4, 2);//D=>C
graphInstance.addEdge(2, 3);//C=>E
graphInstance.addEdge(4, 5);//D=>F
graphInstance.addEdge(3, 5);//E=>F
graphInstance.addEdge(5, 6);//F=>G
graphInstance.addEdge(0, 0);//G=>H
graphInstance.addEdge(2, 7);//C=>H
graphInstance.广度优先搜索();
}
}
}
编辑于 2019-03-23 11:09
算法与数据结构
文章被以下专栏收录
