【无标题】根据输入的图的邻接矩阵A，判断此图的连通分量的个数。

本文主要是介绍【无标题】根据输入的图的邻接矩阵A，判断此图的连通分量的个数。，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

【问题描述】
 根据输入的图的邻接矩阵A，判断此图的连通分量的个数。

【输入形式】
 第一行为图的结点个数n，之后的n行为邻接矩阵的内容，每行n个数表示。其中A[i][j]=1表示两个结点邻接，而A[i][j]=0表示两个结点无邻接关系。

【输出形式】
 输出此图连通分量的个数。

【样例输入】
 5
 0 1 1 0 0
 1 0 1 0 0
 1 1 0 0 0
 0 0 0 0 1
 0 0 0 1 0

【样例输出】
 2

【样例说明】
 邻接矩阵中对角线上的元素都用0表示。(单个独立结点，即与其它结点都没有边连接，也算一个连通分量)

【评分标准】
 要求必须使用图的广度或者深度优先遍历算法，否则不得分。

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

#define Length 20

int vertex[100];

int visited[100];

int a[100][100]={0};

int length;

int edge;

int List[100];

int start=0;

int head;

int tail;

void creatmatrix()

{

    int n,e;

    int m;

    int ma;

    int start,end;

    int clo,row;

    int i,j,k,l;

    //printf("请输入要输入的节点数量:\n");

    scanf("%d",&n);

    length=n;

    // printf("请输入邻接矩阵：\n");

      for(i=1;i<=length;i++)

        {

            for(j=1;j<=length;j++)

            {

                scanf("%d",&ma);

                a[i][j]=ma;

            }

        }

    for(k=1;k<=length;k++)

    {

        vertex[k]=k;

    }

}

void show()

{

    int i,j;

    for(i=1;i<=length;i++)

        {

             printf("%d ",vertex[i]);

        }

    printf("\n");

    for(i=1;i<=length;i++)

    {

        for(j=1;j<=length;j++)

        {

            printf("%d ",a[i][j]);

        }

        printf("\n");

    }

      printf("\n");

}

void BFS(int many)

{

    int i,j,n,m,b,cur;

    head=1;

    tail=1;

    //printf("广度优先开始遍历的图的顶点为%d：\n",many);

    List[tail]=many;

    tail++;

    visited[many]=1;  //标记1号顶点已访问

    while(head<tail && tail<=length)

    {

        cur=List[head];  //当前正在访问的顶点编号

        for(i=1;i<=length;i++)  //从1~n依次尝试

        {

            //判断从顶点cur到顶点i是否有边，并且顶点i没有被访问过，则将顶点i入队

            if(a[cur][i]==1&&visited[i]==0){

                               List[tail]=i;

                               tail++;

                               visited[i]=1;

                            //标记顶点i已访问

            }

            //如果tail大于n，则表明所有顶点都已经被访问过

            //if(tail>n)

           // {

            //    break;

            // }

         }

        head++;  //当一个顶点扩展结束后，执行head++才能继续往下扩展

     }

    //for(i=1;i<tail;i++)

    //    printf("%d ",List[i]);

    //printf("\n");

}

void detect()

{

    int i,j,num=0,m;

     for(j=1;j<=length;j++)

        {

             visited[j]=0;

        }

    for(i=1;i<=length;i++)

    {

        if(visited[i]==0)

        {

            BFS(i);

            num++;

        }

        //printf("\n");

    }

    printf("%d ",num);

}

int main()

{

    int m,n;

    creatmatrix();

    detect();

}

这篇关于【无标题】根据输入的图的邻接矩阵A，判断此图的连通分量的个数。的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！