C#实现基于广度优先BFS求解无权图最短路径----完整程序展示

本文介绍C#实现基于广度优先BFS求解无权图最短路径----完整程序展示

1、代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 图的应用__基于BFS算法求解的那元最短路径
{
using VertexType = System.Char;//顶点数据类型别名声明
using EdgeType = System.Int16;//带权图中边上权值的数据类型别名声明
class Program
{
public const int MAxVertexNum = 100;//顶点数目的最大值
public const int MAXSize = 100;
static void Main(string[] args)
{
MGraph G = new MGraph();
int u;
int[] d = new int[MAxVertexNum];
G.vexnum = 8;
G.arcnum = 8;
G.vex = new VertexType[MAxVertexNum];
G.Edge = new EdgeType[MAxVertexNum, MAxVertexNum];
for (int i = 0; i < MAxVertexNum; ++i)
{
for (int j = 0; j < MAxVertexNum; ++j)
{
G.Edge[i, j] = 0;
}
}
//图的赋值
G.vex[0] = ‘a’; G.vex[1] = ‘b’; G.vex[2] = ‘c’; G.vex[3] = ‘d’; G.vex[4] = ‘e’; G.vex[5] = ‘f’;
G.vex[6] = ‘g’; G.vex[7] = ‘h’;
G.Edge[0, 1] = 1; G.Edge[0, 2] = 1;
G.Edge[1, 0] = 1; G.Edge[1, 3] = 1; G.Edge[1, 4] = 1;
G.Edge[2, 0] = 1; G.Edge[2, 5] = 1; G.Edge[2, 6] = 1;
G.Edge[3, 1] = 1;
G.Edge[4, 1] = 1; G.Edge[4, 7] = 1;
G.Edge[5, 2] = 1;
G.Edge[6, 2] = 1;
G.Edge[7, 4] = 1;
//广度优先
Console.WriteLine(“广度优先：”);
BFSTraverse(G);
u = 3;
Console.WriteLine();
Console.WriteLine(“顶点”+G.vex[u]+“到各点最短路径：”);
BFS_MIN_Distance(G,u,ref d);
for (int i=0;i
= 0; w = NextNeighbor(G, v, w)) { if (!visited[w]) { visit(G, w); //访问顶点w visited[w] = true;//对w做已访问标记 EnQueue(ref Q, w); } } } } //控制台打印遍历点 static void visit(MGraph G, int v) { Console.Write(G.vex[v] + " "); } //查找G中，V顶点的首个邻接点 static int FirstNeighbor(MGraph G, int v) { int b = -1; for (int i = 0; i < G.vexnum; ++i) { if (G.Edge[v, i] == 1) { b = i; break; }; } return b;//返回首个邻接点 } //查找G中，V顶点的W邻节点后的下一个邻接点 static int NextNeighbor(MGraph G, int v, int w) { int b = -1; for (int i = w + 1; i < G.vexnum; ++i) { if (G.Edge[v, i] == 1) { b = i; break; }; } return b;//返回下一个邻接点 } //求单源最短路径,即u到各顶点的最短路径长度 static void BFS_MIN_Distance(MGraph G,int u,ref int[] d) { bool[] visited = new bool[MAxVertexNum];//访问标记数组 SqQueue Q = new SqQueue(); InitQueue(ref Q); Q.data = new int[MAxVertexNum]; for (int i=0;i=0;w=NextNeighbor(G,u,w)) { if (!visited[w]) { d[w] = d[u] + 1; visited[w] = true; EnQueue(ref Q, w); } } } } /// /// 队列结构体定义 /// public struct SqQueue { public int[] data;//队列存放的元素 public int front, real;//队头和队尾指针 } /// /// 队列初始化 /// /// static void InitQueue(ref SqQueue Q) { Q.real = Q.front = 0; } /// /// 判断队列是否为空 /// /// /// static bool isEmpty(SqQueue Q) { if (Q.front == Q.real) { return true; } else return false; } /// /// 入队 /// /// /// /// static bool EnQueue(ref SqQueue Q, int x) { if ((Q.real + 1) % MAXSize == Q.front) { return false; } Q.data[Q.real] = x; Q.real = (Q.real + 1) % MAXSize; return true; } static bool DeQueue(ref SqQueue Q, ref int x) { if (Q.real == Q.front) { return false; } x = Q.data[Q.front]; Q.front = (Q.front + 1) % MAXSize; return true; } }

}
2、测试结果