算法系列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

#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);
                }
            }
        }

#region 深度递归的具体算法
        /// <summary>
/// 深度递归的具体算法
/// </summary>
/// <param></param>
/// <param></param>
        public void DFSM(ref MatrixGraph graph, int vertex)
        {
            Console.Write("->" + graph.vertex[vertex]);

//标记为已访问
            graph.isTrav[vertex] = true;

//要遍历的六个点
            for (int i = 0; i < graph.vertexNum; i++)
            {
                if (graph.isTrav[i] == false && graph.edges[vertex, i] != 0)
                {
                    //深度递归
                    DFSM(ref graph, i);
                }
            }
        }
        #endregion
        #endregion

}
}

代码中我们构建了如下的“图”。

（编辑：焦作站长网）

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