C ＃ realize solving the shortest path of unauthorized graph based on breadth first BFS -- complete program display

In this paper, C# Implementation based on breadth first BFS Solve the shortest path of the weighted graph ---- Complete program display

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

namespace The application of graph __ be based on BFS The shortest path of that element solved by the algorithm
{
using VertexType = System.Char;// Vertex data type alias declaration
using EdgeType = System.Int16;// Data type alias declaration of edge weight in weighted graph
class Program
{
public const int MAxVertexNum = 100;// The maximum number of vertices
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;
}
}
// Assignment of Graphs
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;
// breadth-first
Console.WriteLine(“ breadth-first ：”);
BFSTraverse(G);
u = 3;
Console.WriteLine();
Console.WriteLine(“ The vertices ”+G.vex[u]+“ The shortest path to each point ：”);
BFS_MIN_Distance(G,u,ref d);
for (int i=0;i<G.vexnum;++i) {
Console.Write(d[i]+" ");

        }



        Console.Read();
    }



    /// <summary>
    ///  Definition of graph -- Adjacency matrix 
    /// </summary>
    public struct MGraph
    {
        public VertexType[] vex;// Vertex table array 
        public EdgeType[,] Edge;// Adjacency matrix 、 Side table 
        public int vexnum, arcnum;// The current vertex and arc number of a graph 
    }
    /// <summary>
    ///  Definition of graph -- Adjacency table method 
    /// </summary>
    public class ArcNode
    {// Edge table node 
        public int adjvex;
        public ArcNode next;
    }
    public class VNode
    {  // Vertex table node 
        VertexType data;// Vertex information 
        ArcNode first;// Just think of the pointer to the first arc attached to the vertex 
    }
    public class ALGraph
    {
        VNode[] vertices;   // Adjacency list 
        int vexnum, arcnum;// The number of vertices and arcs of a graph 
    }
    /// <summary>
    ///  Pair graph G Breadth first traversal 
    /// </summary>
    static void BFSTraverse(MGraph G)
    {
        bool[] visited = new bool[MAxVertexNum];// Access tag array 
        for (int i = 0; i < G.vexnum; ++i)
            visited[i] = false;// Access tag array initialization 
        SqQueue Q = new SqQueue();
        Q.data = new int[MAxVertexNum];// The queue array needs to be new
        InitQueue(ref Q);// Queue initialization 
        for (int i = 0; i < G.vexnum; ++i)
        {
            if (!visited[i])
                BFS(G, i, ref visited, ref Q);

        }

    }

    static void BFS(MGraph G, int v, ref bool[] visited, ref SqQueue Q)
    {
        visit(G, v);// First access the initial vertex v
        visited[v] = true;// Yes v Mark visited 
        EnQueue(ref Q, v);// The vertices v Queue entry 
        while (!isEmpty(Q))
        {
            DeQueue(ref Q, ref v);// The vertices v Outgoing queue 
            for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
            {
                if (!visited[w])
                {
                    visit(G, w);   // Visit vertex w
                    visited[w] = true;// Yes w Mark visited 
                    EnQueue(ref Q, w);
                }


            }

        }

    }
    // The console prints traversal points 
    static void visit(MGraph G, int v)
    {
        Console.Write(G.vex[v] + " ");
    }
    // lookup G in ,V The first adjacent node of a vertex 
    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;// Return to the first adjacent contact 
    }
    // lookup G in ,V Vertex W The next adjacent node after the adjacent node 
    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;// Return to the next adjacent contact 
    }
    // Find the shortest path of a single source , namely u The shortest path length to each vertex 
    static void BFS_MIN_Distance(MGraph G,int u,ref int[] d) {
        bool[] visited = new bool[MAxVertexNum];// Access tag array 
        SqQueue Q = new SqQueue();
        InitQueue(ref Q);
        Q.data = new int[MAxVertexNum];
        for (int i=0;i<G.vexnum;++i) {
            visited[i] = false;
            d[i] = -1;// Initialization path length .-1 It means that there is no 
        }
        visited[u] = true;d[u] = 0;
        EnQueue(ref Q,u);
        while (!isEmpty(Q)) {
            DeQueue(ref Q, ref u);
            for (int w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)) {
                if (!visited[w]) {
                    d[w] = d[u] + 1;
                    visited[w] = true;
                    EnQueue(ref Q, w);
                }


            }

        }


    }




    /// <summary>
    ///  Queue structure definition 
    /// </summary>
    public struct SqQueue
    {
        public int[] data;// Queued elements 
        public int front, real;// Team leader and team leader 
    }
    /// <summary>
    ///  Queue initialization 
    /// </summary>
    /// <param name="Q"></param>
    static void InitQueue(ref SqQueue Q)
    {
        Q.real = Q.front = 0;
    }
    /// <summary>
    ///  Determines if the queue is empty 
    /// </summary>
    /// <param name="Q"></param>
    /// <returns></returns>
    static bool isEmpty(SqQueue Q)
    {
        if (Q.front == Q.real) { return true; }
        else return false;
    }
    /// <summary>
    ///  The team 
    /// </summary>
    /// <param name="Q"></param>
    /// <param name="x"></param>
    /// <returns></returns>
    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、 test result