首页 > 其他 > 详细

利用二维矩阵求spanning tree

时间:2014-03-20 02:19:01      阅读:511      评论:0      收藏:0      [点我收藏+]

只做了9个节点的,无权值,使用了n-1个=8个循环,非常麻烦。一级一级判断是否连接,连接及记录所在节点,以后不再使用,确保无回路。

验证后无回路,但只试过几种情况。

代码如下:

bubuko.com,布布扣
#include<iostream>
using namespace std;



int w[9][9];
int e[9][9];
void Shuru()
{   
 

    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
    {cout<<"请输入节点"<<i+1<<"与节点"<<j+1<<"是否存在连通。yes=1;no=0"<<endl;
        cin>>w[i][j];
    }
    }
}

void Panduan()
{
    
    for(int p=0;p<9;p++)
        {for(int q=0;q<9;q++)
        {e[p][q]=0;}//赋值
    }
    int d[9];
    for(int k=0;k<9;k++)
    {d[k]=0;}
    d[0]=1;

    //判断部分
    for(int a1=0;a1<9;a1++)
    {
    if(w[0][a1]==1&&d[a1]==0)
    {e[0][a1]=1;    e[a1][0]=1;
    d[a1]=a1;
        for(int a2=1;a2<9;a2++)
        {
        if(w[a1][a2]==1&&d[a2]==0)
    {e[a1][a2]=1;
    e[a2][a1]=1;
    d[a2]=a2;
           for(int a3=1;a3<9;a3++)
           {
               if(w[a2][a3]==1&&d[a3]==0)
                  { e[a2][a3]=1;
                   e[a3][a2]=1;
                   d[a3]=a3;
                   for(int a4=1;a4<9;a4++)
                   {
                       if(w[a3][a4]==1&&d[a4]==0)
                        {   e[a3][a4]=1;
                           e[a4][a3]=1;
                           d[a4]=a4;
                           for(int a5=1;a5<9;a5++)
                           {
                               if(w[a4][a5]==1&&d[a5]==0)
                         {  e[a4][a5]=1;
                           e[a5][a4]=1;
                           d[a5]=a5;
                           for(int a6=1;a6<9;a6++)
                           {
                               if(w[a5][a6]==1&&d[a6]==0)
                          { e[a5][a6]=1;
                           e[a6][a5]=1;
                           d[a6]=a6;
                            for(int a7=1;a7<9;a7++)
                            {
                                if(w[a6][a7]==1&&d[a7]==0)
                           {e[a6][a7]=1;
                           e[a7][a6]=1;
                           d[a7]=a7;
                           for(int a8=1;a8<9;a8++)
                           {
                               if(w[a7][a8]==1&&d[a8]==0)
                           {e[a7][a8]=1;
                           e[a8][a7]=1;
                           d[a8]=a8;
                           }
                           }
                           }

                           }
                           }

                   }
           }

    }
    }
    }
    }
           }
        }
        }
    }
    }
}
void main()
{
    Shuru();
    Panduan();
    for(int z=0;z<9;z++)
    {
        {for(int x=0;x<9;x++)
        cout<<e[z][x]<<"\t";}
        cout<<endl;
    }
    
}
bubuko.com,布布扣

 

示例:

bubuko.com,布布扣

结果:

bubuko.com,布布扣

利用二维矩阵求spanning tree,布布扣,bubuko.com

利用二维矩阵求spanning tree

原文:http://www.cnblogs.com/cife/p/3612384.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!