算法系列15天速成——第十五天 图【下】（大结局）

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

#region prim算法获取最小生成树
        /// <summary>
/// prim算法获取最小生成树
/// </summary>
/// <param></param>
        public void Prim(MatrixGraph graph, out int sum)
        {
            //已访问过的标志
            int used = 0;

//非邻接顶点标志
            int noadj = -1;

//定义一个输出总权值的变量
            sum = 0;

//临时数组，用于保存邻接点的权值
            int[] weight = new int[graph.vertexNum];

//临时数组，用于保存顶点信息
            int[] tempvertex = new int[graph.vertexNum];

//取出邻接矩阵的第一行数据，也就是取出第一个顶点并将权和边信息保存于临时数据中
            for (int i = 1; i < graph.vertexNum; i++)
            {
                //保存于邻接点之间的权值
                weight[i] = graph.edges[0, i];

//等于0则说明V1与该邻接点没有边
                if (weight[i] == short.MaxValue)
                    tempvertex[i] = noadj;
                else
                    tempvertex[i] = int.Parse(graph.vertex[0]);
            }

//从集合V中取出V1节点，只需要将此节点设置为已访问过，weight为0集合
            var index = tempvertex[0] = used;
            var min = weight[0] = short.MaxValue;

//在V的邻接点中找权值最小的节点
            for (int i = 1; i < graph.vertexNum; i++)
            {
                index = i;
                min = short.MaxValue;

for (int j = 1; j < graph.vertexNum; j++)
                {
                    //用于找出当前节点的邻接点中权值最小的未访问点
                    if (weight[j] < min && tempvertex[j] != 0)
                    {
                        min = weight[j];
                        index = j;
                    }
                }
                //累加权值
                sum += min;

Console.Write("({0},{1})  ", tempvertex[index], graph.vertex[index]);

（编辑：焦作站长网）

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