基於 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);

    }
}