算法实验（二）寻找无向图的衔接点

「爱情、让人受尽委屈。」 2022-02-05 07:45 191阅读 0赞

图G的衔接点是指图G中的一个节点，删除该节点将导致图不连通。

分为两部分：

**1.如果是根节点，则判断其是否有两个子节点（DFS树中，不是原始的图中）及以上，如果是则为衔接点。**

**2.不是根节点，如果词典有一个子节点s，且没有任何从节点s或任何s的后代节点指向v的真祖先的后向边**

判断第二点我们根据一个low值来判断。

v.low=min(v.d,w.d)//(u,w)是节点v的某个后代节点u（自己也可以）的一条后向边

代码如下：

void linkedDgraph1::DFS_Articulution(vector<int> &articulution)
    {
    	time = 0;
    	for (int i = 0; i < verticeNumber; i++)
    	{
    		int temp = point[i];
    		if (color[temp] == WHITE)
    		{
    			//if (outDegree(temp) > 1)
    	
    			DFS_Articulution_visit(temp,articulution);
    			if (DFS_subVerticeNumber(temp) > 1)//如果子节点的数目大于1，则是衔接点
    				articulution.push_back(temp);
    			if (DFS_subVerticeNumber(temp) <2)
    			{
    				vector<int>::iterator it = articulution.begin();//如果子节点的数目小于2，则删除在前面的加入的根节点
    				while (it!= articulution.end())
    				{
    					if (*it == temp)
    					{
    						articulution.erase(it);
    						break;
    					}
    					it++;
    				}
    			}
    		}
    
    	}
    }
    
    void linkedDgraph1::DFS_Articulution_visit(int u, vector<int> &articulution)
    {
    	time += 1;
    	dTime[u] = time;
    	color[u] = GRAY;
    	low[u] = time;
    	graphNode<int> *p = Adj[u].first();
    	while (p != NULL)
    	{
    		int v = p->element;
    		if (precursor[u] != v)//去除掉这种特殊的“后向边”，即a,b之间的边，但是插入的时后不仅插入了（a,b)还插入了(b,a)但这是无向图，只能算一条。
    		{
    			if (color[v] == WHITE)//如果点是白色的
    			{
    				precursor[v] = u;
    				DFS_Articulution_visit(v,articulution);
    				//G1.insertEdge(u, v, 1);
    				//cout << u << "-->" << v << endl;
    				if (low[v] < low[u])//存在子节点被更新过
    				    low[u] = low[v];
    			}
    			if (color[v] == GRAY)//如果是后向边
    				if (dTime[v] < low[u])//计算新的low，判断v的dTime来更新low
    					low[u] = dTime[v];
    			if (low[v] >= dTime[u])//v是u的子节点
    			{
    				bool exist = false;
    				for (int i = 0; i < articulution.size(); i++)
    				{
    					if (articulution[i] == u)
    					{
    						exist = true;
    						break;
    					}
    					
    				}
    				if(!exist)
    				 articulution.push_back(u);
    			}
            }
    		p = p->next;
    	}
    	
    	color[u] = BLACK;
    	time += 1;
    	fTime[u] = time;
    }

求子节点数目（DFS树中）的函数：

int linkedDgraph1::DFS_subVerticeNumber(int n)
    {
    	int count = 0;
    	for (int i = 0; i < verticeNumber; i++)
    	{
    		if (precursor[i] == n)
    			count++;
    	}
    	return count;
    }

注意：整个代码采用邻接链表实现，无向图插入边的时候是插入（a,b)和（b,a）要小心这里存在的无效的后向边