算法系列15天速成 第十四天 图【上】

/// <summary>
/// 广度遍历具体算法
/// </summary>
/// <param></param>
        public void BFSM(ref MatrixGraph graph, int vertex)
        {
            //这里就用系统的队列
            Queue<int> queue = new Queue<int>();

//先把顶点入队
            queue.Enqueue(vertex);

//标记此顶点已经被访问
            graph.isTrav[vertex] = true;

//输出顶点
            Console.Write(" ->" + graph.vertex[vertex]);

//广度遍历顶点的邻接点
            while (queue.Count != 0)
            {
                var temp = queue.Dequeue();

//遍历矩阵的横坐标
                for (int i = 0; i < graph.vertexNum; i++)
                {
                    if (!graph.isTrav[i] && graph.edges[temp, i] != 0)
                    {
                        graph.isTrav[i] = true;

queue.Enqueue(i);

//输出未被访问的顶点
                        Console.Write(" ->" + graph.vertex[i]);
                    }
                }
            }
        }
        #endregion

<3> 深度优先

同样是这个图，大家看看如何实现深度优先，深度优先就像铁骨铮铮的好汉，遵循“能进则进，不进则退”的原则。

第一步：同样也是从isTrav数组中选出一个未被访问的节点，如V1。

第二步：然后一直访问V1的邻接点，一直到走头无路的时候“回溯”，路线为V1,V2,V3,V4,V5，到V5的时候访问邻接点V1，发现V1是访问过的，

此时一直回溯的访问直到V1。

第三步： 同样有的图中通过一个顶点的“深度优先”不能遍历所有的顶点，此时我们重复（1-2）的步骤就可以最终完成深度优先遍历。

复制代码 代码如下:

#region 深度优先
        /// <summary>
/// 深度优先
/// </summary>
/// <param></param>
        public void DFSTraverse(MatrixGraph graph)
        {
            //访问标记默认初始化
            for (int i = 0; i < graph.vertexNum; i++)
            {
                graph.isTrav[i] = false;
            }

//遍历每个顶点
            for (int i = 0; i < graph.vertexNum; i++)
            {
                //广度遍历未访问过的顶点
                if (!graph.isTrav[i])
                {
                    DFSM(ref graph, i);
                }
            }
        }

（编辑：焦作站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!