本文介绍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、测试结果 
