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

1.判斷圖連通的算法
第一種方法基于BFS，首先利用鄰接表（鏈表形式或者數(shù)組形式都可以）存儲圖的信息，然后取標號值最小的頂點u作為根節(jié)點進行先深搜索，最終搜索到的節(jié)點將形成一棵樹，判斷圖是否連通，只要判斷是否所有節(jié)點都在樹上即可。
代碼如下：
//graph[][]存儲圖信息，num[]存儲每個頂點的鄰接點數(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]);
        }
    }
}

然而這種算法存在弊端，就是需要存儲所有的邊信息，當邊信息足夠多時，存儲數(shù)組graph[][]、num[]和flag[]的開銷是很大的。第二種基于并查集的方法則解決了這個弊端，關(guān)于并查集的內(nèi)容具體可見：http://m.shnenglu.com/amazon/archive/2009/08/15/93457.html。對所有的邊信息進行并查集處理后，如果該圖是連通圖，那么所有節(jié)點的根節(jié)點指針都指向同一個點。
代碼如下：
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.求割點的算法
首先必須保證，所求的圖是連通圖，不連通的圖沒有割點。
該算法依然基于BFS，按照標號值大小依次將圖中的頂點隱去，對剩下的所有節(jié)點進行先深搜索，根據(jù)搜索子樹的數(shù)目即可知道隱去的節(jié)點是否割點（數(shù)目為1，非割點；數(shù)目為2以上，割點），并可根據(jù)子樹的數(shù)目知道刪除該割點后連通子圖的數(shù)目。
代碼如下：
jump = false;
for(i = 1; i <= nodeNum; i++)
{
    subnetNum = 0;
    HowMuch(i, subnetNum);

    if(subnetNum != 1)
    {
        printf("%d是割點，刪除后有%d個連通子圖\n", i, subnetNum);
        jump = true;
    }
}
if(jump == 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]);
        }
    }
}

//判斷是否割點
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);
        }
    }
}