之所以把判断图连通的算法以及求图中割点的算法放在一起写,是因为这两者之间有一定的关系。注意:只有连通图中才可能有割点,不连通的图是没有割点的。总的来说,这两类算法都离不开并查集结构和BFS先深搜索,具体如下:

1.判断图连通的算法
第一种方法基于BFS,首先利用邻接表(链表形式或者数组形式都可以)存储图的信息,然后取标号值最小的顶点u作为根节点进行先深搜索,最终搜索到的节点将形成一棵树,判断图是否连通,只要判断是否所有节点都在树上即可。
代码如下:
//graph[][]存储图信息,num[]存储每个顶点的邻接点数目
memset(flag, 0sizeof(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]);
        }

    }

}

然而这种算法存在弊端,就是需要存储所有的边信息,当边信息足够多时,存储数组graph[][]、num[]和flag[]的开销是很大的。第二种基于并查集的方法则解决了这个弊端,关于并查集的内容具体可见:http://www.cppblog.com/amazon/archive/2009/08/15/93457.html。对所有的边信息进行并查集处理后,如果该图是连通图,那么所有节点的根节点指针都指向同一个点。
代码如下:
= 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,按照标号值大小依次将图中的顶点隐去,对剩下的所有节点进行先深搜索,根据搜索子树的数目即可知道隐去的节点是否割点(数目为1,非割点;数目为2以上,割点),并可根据子树的数目知道删除该割点后连通子图的数目。
代码如下:
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, 
0sizeof(flag));
    flag[x] 
= true;
    
for(i = 1; i <= nodeNum; i++)
    
{
        
if(flag[i] == false)
        
{
            subnetNum
++;
            DFS(i);
        }

    }

}