您当前的位置: 首页 >  c#

光怪陆离的节日

暂无认证

  • 4浏览

    0关注

    1003博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

C#实现图的深度优先遍历--非递归代码

光怪陆离的节日 发布时间:2022-06-30 16:41:17 ,浏览量:4

本文介绍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(); }

    /// 
    /// 图的定义--邻接矩阵
    /// 
    public struct MGraph
    {
        public VertexType[] vex;//顶点表数组
        public EdgeType[,] Edge;//临接矩阵、边表
        public int vexnum, arcnum;//图的当前顶点数和弧数
    }
    /// 
    /// 图的定义--邻接表法
    /// 
    public class ArcNode
    {//边表节点
        public int adjvex;
        public ArcNode next;
    }
    public class VNode
    {  //顶点表节点
        VertexType data;//顶点信息
        ArcNode first;//只想第一条依附改顶点的弧的指针
    }
    public class ALGraph
    {
        VNode[] vertices;   //邻接表
        int vexnum, arcnum;//图的顶点数和弧数
    }
    /// 
    /// 深度优先搜索的递归实现
    /// 
    /// 
    /// 
    /// 
    static void DFS_Traverse(MGraph G) {
        bool[] visited = new bool[MAxVertexNum];
        for (int i=0;i=0;w=NextNeighbor(G,v,w)) {
                if (!visited[w]) {
                    Push(ref S, 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;//返回下一个邻接点
    }

    /// 
    /// 栈定义
    /// 
    public struct SqStack
    {
        public int[] data;
        public int top;//栈顶

    }
    /// 
    /// 判断栈是否为空
    /// 
    /// 
    /// 
   static bool StackEmpty(SqStack S)
    {
        if (S.top == -1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    /// 
    /// 栈初始化
    /// 
    /// 
    static void InitStack(ref SqStack S)
    {
        S.top = -1;
    }
    /// 
    /// 压栈
    /// 
    /// 
    /// 
    static bool Push(ref SqStack S, int e)
    {
        if (S.top >= MAxVertexNum - 1)
        {
            return false;
        }
        S.top = S.top + 1;
        S.data[S.top] = e;//先加1,再进栈
        return true;
    }
    /// 
    /// 出栈
    /// 
    /// 
    /// 
    /// 
    static bool PoP(ref SqStack S, ref int e)
    {
        if (S.top == -1) { return false; }
        e = S.data[S.top--];//出栈
        return true;
    }
    /// 
    /// 
    ///读取栈顶元素
    /// 
    /// 
    /// 
    /// 
    bool GetTop(ref SqStack S, ref int e)
    {

        if (S.top == -1) { return false; }
        e = S.data[S.top];//读取元素
        return true;

    }



}

}

2、测试如下: 在这里插入图片描述 在这里插入图片描述 在这里插入图片描述

关注
打赏
1665731445
查看更多评论
立即登录/注册

微信扫码登录

0.3257s