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

#region 图的创建
        /// <summary>
/// 图的创建
/// </summary>
/// <param></param>
        public MatrixGraph CreateMatrixGraph()
        {
            Console.WriteLine("请输入创建图的顶点个数，边个数，是否为无向图(0,1来表示)，已逗号隔开。");

var initData = Console.ReadLine().Split(',').Select(i => int.Parse(i)).ToList();

MatrixGraph graph = new MatrixGraph(initData[0], initData[1], initData[2]);

Console.WriteLine("请输入各顶点信息：");

for (int i = 0; i < graph.vertexNum; i++)
            {
                Console.Write("n第" + (i + 1) + "个顶点为:");

var single = Console.ReadLine();

//顶点信息加入集合中
                graph.vertex[i] = single;
            }

Console.WriteLine("n请输入构成两个顶点的边和权值，以逗号隔开。n");

for (int i = 0; i < graph.edgeNum; i++)
            {
                Console.Write("第" + (i + 1) + "条边:t");

initData = Console.ReadLine().Split(',').Select(j => int.Parse(j)).ToList();

int start = initData[0];
                int end = initData[1];
                int weight = initData[2];

//给矩阵指定坐标位置赋值
                graph.edges[start - 1, end - 1] = weight;

//如果是无向图，则数据呈“二，四”象限对称
                if (graph.graphType == 1)
                {
                    graph.edges[end - 1, start - 1] = weight;
                }
            }

return graph;
        }
        #endregion

<2>广度优先

针对下面的“图型结构”，我们如何广度优先呢？其实我们只要深刻理解"广搜“给我们定义的条条框框就行了。 为了避免同一个顶点在遍历时被多

次访问，可以将”顶点的下标”存放在sTrav[]的bool数组，用来标识是否已经访问过该节点。 

第一步：首先我们从isTrav数组中选出一个未被访问的节点，如V1。

第二步：访问V1的邻接点V2，V3，V5，并将这三个节点标记为true。

第三步：第二步结束后，我们开始访问V2的邻接点V1，V3，但是他们都是被访问过的。

第四步：我们从第二步结束的V3出发访问他的邻接点V2，V1，V5，V4，还好V4是未被访问的，此时标记一下。

第五步：我们访问V5的邻接点V1，V3，V4，不过都是已经访问过的。

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

复制代码 代码如下:

#region 广度优先
        /// <summary>
/// 广度优先
/// </summary>
/// <param></param>
        public void BFSTraverse(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])
                {
                    BFSM(ref graph, i);
                }
            }
        }

（编辑：焦作站长网）

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