深度优先生成树
对于无向图，处理边(v, w)时，若w未被访问过则将v->w作为树的一条边，否则将v->w画成虚线表示后向边，这条边并不是树的一部分
深度优先生成树.PNG
双连通性
一个连通的无向图中任一顶点删除后，剩下的图仍连通（例如邮件系统，公交运输系统）
若图非双连通，将删除后图不再连通的顶点叫做割点
深度优先搜索找割点（连通图）
从图的任一顶点开始，执行深度优先搜索并在顶点被访问是给它们编号，称为前序编号Num(v)
对于深度优先搜索生成树上的每个顶点，计算可回到的编号最低的顶点Low(v)（利用零条或多条边可能还有一条后向边）
Num-Low.PNG
可通过一次后序遍历算出Low
Low(v)=Min{Num(v)（不选取边）；
所有后向边(v, w)中最低的Num(w)（选取一条后向边）；
所有边(v, w)中最低的Low(w)（选取一些边加一条后向边）}
根是割点当且仅当它有多个儿子
任何其它顶点v是割点，当且仅当它有某个儿子w，Low(w)>=Num(v)
因为此条件意味着要从w到达v上的任何一点必须要经过v
void DFSArticul(ALGraph G, int v0)
{
min=visited[v0]=count++; //count是DFS访问顺序
for(p=G.vertices[v0].first;p;p=p->nextarc)
{
w=p->adjves;
if(visited[w]==0)
{//w是未访问过的
DFSArticul(G, w);
if(low[w]<min) min=low[w];
if(low[w]>=visited[v0])
//v0是割点
}else //w已被访问过则是回边上的点
if(visited[w]<min) min=visited[w];
}
low[v0]=min
}
count=1; visited[0]=1;
p=G.vertices[0].firstarc;
v=p->adjvex;
DFSArticul(G, v); //从根的邻接点v开始DFS
if(count<G.vexnum){
//生成树的根至少有两个子树，根是割点
while(p->nextarc){
p=p->nextarc; v=p->adjvex;
if(!visited[v]) DFSArticul(G, v);
}
