基于 BFS 的无向图连通分量

BFS 可用于查找无向图的连通分量。我们还可以找到给定图是否连接。我们随后的讨论假设我们正在处理无向图。连通图的定义是：

如果每对顶点之间存在路径，则连接图形。

以下是连接图。

以下图表未连接且具有 2 个连接组件：

1. 连接组件 1：{a，b，c，d，e}
2. 连接组件 2：{f}

BFS 是图遍历算法。因此，从随机源节点开始，如果在算法终止时，访问所有节点，则连接图形，否则它不连接。

伪算法的算法。

boolean isConnected(Graph g)
{     
 BFS(v)//v is a random source node.
 if(allVisited(g))
 {
  return true;
 }
 else return false;
}

用于查找无向图是否连接的 C 实现：

#include<stdio.h>
#include<stdlib.h>
#define MAXVERTICES 100    

void enqueue(int);
int deque();
int isConnected(char **graph,int noOfVertices);
void BFS(char **graph,int vertex,int noOfVertices);    
int count = 0;
//Queue node depicts a single Queue element
//It is NOT a graph node.
struct node
{
    int v;
    struct node *next;
};

typedef struct node Node;
typedef struct node *Nodeptr;

Nodeptr Qfront = NULL;
Nodeptr Qrear = NULL;
char *visited;//array that keeps track of visited vertices.

int main()
{
    int n,e;//n is number of vertices, e is number of edges.
    int i,j;
    char **graph;//adjacency matrix

    printf("Enter number of vertices:");
    scanf("%d",&n);

    if(n < 0 || n > MAXVERTICES)
    {
     fprintf(stderr, "Please enter a valid positive integer from 1 to %d",MAXVERTICES);
     return -1;
    }

    graph = malloc(n * sizeof(char *));
    visited = malloc(n*sizeof(char));

    for(i = 0;i < n;++i)
    {
        graph[i] = malloc(n*sizeof(int));
        visited[i] = 'N';//initially all vertices are not visited.
        for(j = 0;j < n;++j)
            graph[i][j] = 0;
    }

    printf("enter number of edges and then enter them in pairs:");
    scanf("%d",&e);

    for(i = 0;i < e;++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        graph[u-1][v-1] = 1;
        graph[v-1][u-1] = 1;
    }    
    
    if(isConnected(graph,n))
        printf("The graph is connected");
    else printf("The graph is NOT connected\n");       
}

void enqueue(int vertex)
{
    if(Qfront == NULL)
    {
        Qfront = malloc(sizeof(Node));
        Qfront->v = vertex;
        Qfront->next = NULL;
        Qrear = Qfront;
    }
    else
    {
        Nodeptr newNode = malloc(sizeof(Node));
        newNode->v = vertex;
        newNode->next = NULL;
        Qrear->next = newNode;
        Qrear = newNode;
    }
}

int deque()
{
    if(Qfront == NULL)
    {
        printf("Q is empty , returning -1\n");
        return -1;
    }
    else
    {
        int v = Qfront->v;
        Nodeptr temp= Qfront;
        if(Qfront == Qrear)
        {
            Qfront = Qfront->next;
            Qrear = NULL;
        }
        else
            Qfront = Qfront->next;

        free(temp);
        return v;
    }
}

int isConnected(char **graph,int noOfVertices)
{
    int i;

    //let random source vertex be vertex 0;
    BFS(graph,0,noOfVertices);

    for(i = 0;i < noOfVertices;++i)
        if(visited[i] == 'N')
         return 0;//0 implies false;

    return 1;//1 implies true;
}

void BFS(char **graph,int v,int noOfVertices)
{        
    int i,vertex;
    visited[v] = 'Y';
    enqueue(v);    
    while((vertex = deque()) != -1)
    {            
        for(i = 0;i < noOfVertices;++i)
            if(graph[vertex][i] == 1 && visited[i] == 'N')
            {
                enqueue(i);
                visited[i] = 'Y';
            }
    }
}

对于查找无向图的所有 Connected 组件，我们只需要向 BFS 函数添加 2 行代码。我们的想法是调用 BFS 函数，直到访问所有顶点。

要添加的行是：

printf("\nConnected component %d\n",++count);    
//count is a global variable initialized to 0
//add this as first line to BFS function    

和

printf("%d ",vertex+1);
add this as first line of while loop in BFS

我们定义以下函数：

void listConnectedComponents(char **graph,int noOfVertices)
{
    int i;
    for(i = 0;i < noOfVertices;++i)
    {
        if(visited[i] == 'N')
            BFS(graph,i,noOfVertices);

    }
}