qq_33204081
默默Silence
采纳率100%
2016-02-25 07:03 阅读 1.5k
已采纳

邻接矩阵能进行深搜么。现在会邻接表的深搜,还用把邻接矩阵转化为邻接表吗

邻接矩阵如果能进行的话。麻烦大神给点代码啊。小白。。如题。。。。。。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

2条回答 默认 最新

  • 已采纳
    sysuzyc sysuzyc 2016-03-07 03:27

    这是用邻接矩阵求最小生成树的,题主看下能否帮的上忙,如果能帮的上,希望可以采纳

    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;

    int a[510][510] ;
    int n , maxedge;
    int longest ;
    int re[510] ;

    struct edge{
    int x , y ;
    int w ;
    }e[500001] ;

    bool cmp(edge a , edge b)
    {
    return a.w<b.w ;
    }

    int find(int i)
    {
    if(re[i]==i) return i ;
    else return find(re[i]) ;
    }

    int main()
    {
    int t ;
    cin>>t ;
    while(t--)
    {
    memset(re,0,sizeof(re)) ;
    cin>>n ;
    maxedge=0 ;
    for(int i=1 ; i<=n ; i++)
    {
    re[i]=i ;
    for(int j=1 ; j<=n ; j++)
    {
    cin>>a[i][j] ;
    if(j>i)
    {
    e[maxedge].x=i ;
    e[maxedge].y=j ;
    e[maxedge].w=a[i][j] ;
    maxedge++ ;
    }
    }
    }
    sort(e,e+maxedge,cmp) ;
    longest=e[0].w ;
    for(int i=0 ; i<maxedge ; i++)
    {
    int t1=find(e[i].x) ;
    int t2=find(e[i].y) ;
    if(t1!=t2)
    {
    re[t1]=t2 ;
    longest=(longest<e[i].w)?(e[i].w):longest ;
    }
    }
    cout<<longest<<endl;
    if(t) cout<<endl;
    }
    }

    点赞 评论 复制链接分享
  • u013596119 u52983610 2016-02-28 10:18

    void dfs(int i){
    visited[i]=1;
    for(int j=0;j<n;j++){
    if(G[i][j]==1&&visited[j]==0){
    dfs(j);
    }
    }
    }

    点赞 评论 复制链接分享

相关推荐