之所以把判斷圖連通的算法以及求圖中割點(diǎn)的算法放在一起寫，是因?yàn)檫@兩者之間有一定的關(guān)系。注意：只有連通圖中才可能有割點(diǎn)，不連通的圖是沒有割點(diǎn)的。總的來(lái)說(shuō)，這兩類算法都離不開并查集結(jié)構(gòu)和BFS先深搜索，具體如下：

1.判斷圖連通的算法
第一種方法基于BFS，首先利用鄰接表（鏈表形式或者數(shù)組形式都可以）存儲(chǔ)圖的信息，然后取標(biāo)號(hào)值最小的頂點(diǎn)u作為根節(jié)點(diǎn)進(jìn)行先深搜索，最終搜索到的節(jié)點(diǎn)將形成一棵樹，判斷圖是否連通，只要判斷是否所有節(jié)點(diǎn)都在樹上即可。
代碼如下：
//graph[][]存儲(chǔ)圖信息，num[]存儲(chǔ)每個(gè)頂點(diǎn)的鄰接點(diǎn)數(shù)目
memset(flag, 0, sizeof(flag));
DFS(1);
for(i = 1; i <= nodeNum; i++)
{
        if(flag[i] == false)
    {
        printf("不連通\n");    
        }
}

//DFS算法
void DFS(int x)
{
    int i;

    flag[x] = true;
    for(i = 0; i < num[x]; i++)
    {
        if(flag[graph[x][i]] == false)
        {
            DFS(graph[x][i]);
        }
    }
}

然而這種算法存在弊端，就是需要存儲(chǔ)所有的邊信息，當(dāng)邊信息足夠多時(shí)，存儲(chǔ)數(shù)組graph[][]、num[]和flag[]的開銷是很大的。第二種基于并查集的方法則解決了這個(gè)弊端，關(guān)于并查集的內(nèi)容具體可見：http://www.shnenglu.com/amazon/archive/2009/08/15/93457.html。對(duì)所有的邊信息進(jìn)行并查集處理后，如果該圖是連通圖，那么所有節(jié)點(diǎn)的根節(jié)點(diǎn)指針都指向同一個(gè)點(diǎn)。
代碼如下：
a = Find(record[0]);
for(j = 1; j < num_record; j++)
{
    if(a != Find(record[j]))
    {
        printf("The door cannot be opened.\n");
        break;
    }
}

2.求割點(diǎn)的算法
首先必須保證，所求的圖是連通圖，不連通的圖沒有割點(diǎn)。
該算法依然基于BFS，按照標(biāo)號(hào)值大小依次將圖中的頂點(diǎn)隱去，對(duì)剩下的所有節(jié)點(diǎn)進(jìn)行先深搜索，根據(jù)搜索子樹的數(shù)目即可知道隱去的節(jié)點(diǎn)是否割點(diǎn)（數(shù)目為1，非割點(diǎn)；數(shù)目為2以上，割點(diǎn)），并可根據(jù)子樹的數(shù)目知道刪除該割點(diǎn)后連通子圖的數(shù)目。
代碼如下：
jump = false;
for(i = 1; i <= nodeNum; i++)
{
    subnetNum = 0;
    HowMuch(i, subnetNum);

    if(subnetNum != 1)
    {
        printf("%d是割點(diǎn)，刪除后有%d個(gè)連通子圖\n", i, subnetNum);
        jump = true;
    }
}
if(jump == false)
{
    printf("不是割點(diǎn)\n");
}

//DFS算法
void DFS(int x)
{
    int i;

    flag[x] = true;
    for(i = 0; i < num[x]; i++)
    {
        if(flag[graph[x][i]] == false)
        {
            DFS(graph[x][i]);
        }
    }
}

//判斷是否割點(diǎn)
void HowMuch(int x, int &subnetNum)
{
    int i;

    memset(flag, 0, sizeof(flag));
    flag[x] = true;
    for(i = 1; i <= nodeNum; i++)
    {
        if(flag[i] == false)
        {
            subnetNum++;
            DFS(i);
        }
    }
}