C#实现图的深度优先遍历递归算法--详细代码

本文测试C#实现图的深度优先遍历递归算法–详细代码
1、代码如下：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 图的应用__深度优先搜索算法
{
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(“深度优先：”);
DFS_Traverse(G);
Console.ReadLine();
}

    /// <summary>
    /// 图的定义--邻接矩阵
    /// </summary>
    public struct MGraph
    {
        public VertexType[] vex;//顶点表数组
        public EdgeType[,] Edge;//临接矩阵、边表
        public int vexnum, arcnum;//图的当前顶点数和弧数
    }
    /// <summary>
    /// 图的定义--邻接表法
    /// </summary>
    public class ArcNode
    {//边表节点
        public int adjvex;
        public ArcNode next;
    }
    public class VNode
    {  //顶点表节点
        VertexType data;//顶点信息
        ArcNode first;//只想第一条依附改顶点的弧的指针
    }
    public class ALGraph
    {
        VNode[] vertices;   //邻接表
        int vexnum, arcnum;//图的顶点数和弧数
    }
    /// <summary>
    /// 深度优先搜索的递归实现
    /// </summary>
    /// <param name="G"></param>
    /// <param name="v"></param>
    /// <returns></returns>
    static void DFS_Traverse(MGraph G) {
        bool[] visited = new bool[MAxVertexNum];
        for (int i=0;i<G.vexnum;++i) {
            visited[i] = false;            }

        for (int v=0;v<G.vexnum;++v) {
            if (!visited[v]) {
                DFS(G,v,ref visited);
            }

        }

    }
    static void DFS(MGraph G,int v, ref bool[] visited) {
        visit(G,v);
        visited[v] = true;
        for (int w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)) {
            if (!visited[w]) {
                DFS(G, w, ref visited);
            }
          
        }
    }



    //控制台打印遍历点
    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;//返回下一个邻接点
    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

}
2、测试结果