精华内容
下载资源
问答
  • 关节点(Articulation Poinst)是,在原本连通图,在删除关节点及依附边之后,图将被分割成至少两个连通分量(原本整连通图变得不连通)。 另外,没有一个关节点的连通图称为双连通图(Biconnect Graph) 二、求解...

    一、定义:

    关节点(Articulation Poinst)是指,在原本连通的图,在删除关节点及依附的边之后,图将被分割成至少两个连通分量(原本整连通的图变得不连通)。
    另外,没有一个关节点的连通图称为双连通图(Biconnect Graph)

    二、求解关节点算法:

    首先,将无向连通图从某个顶点开始进行DFS遍历,遍历会得到一个DFS树(深度优先生成树)
    相信读者已经通过其他地方知道了下面的判断顶点u是否是关节点的原则:

    1、如果u是整颗DFS树的根,如果u至少有两个子女,那么u必然是关节点。

    2、DFS树中叶节点不是关节点

    3、非根顶点u(不整颗DFS树的根)不是关节点的充要条件是:它的任一子孙都可以沿某条路径绕过顶点u达到u的任一祖先w (w!=u),u不属于该路径(这条路径包括回边)
    ps:(回边是原本图中有的,在DFS数里没有的)

    针对判定原则里的1我们再定义一个变量children用于记录当前顶点的子女数,如果当前顶点是根结点(整棵树的根),再定一个数组parent,parent[u]表示u的双亲是谁。

    针对判定原则里的2,3我们再定义:
    1、depth[u]为顶点uDFS树中的深度
    2、low[u]为顶点u的所有子孙(包括u)能够到达的邻居中的最低(小)深度。

    显然,在DFS树中如果顶点w是顶点u的祖先,那么必有depth[w] < depth[u]
    因此,在DFS的时候,先让depth[u]等于low[u]等于当前节点的深度,然后再看节点u的子孙里有没有那个子孙v有到u的某个祖先w的回边,有的话更新那个子孙v以及其那个子孙v所有祖先的low[]的值为depth[w](直到那个祖先w)
    然后就可以判断了,假设uv的双亲,如果low[u]>=depth[u]那么u的子孙都没一条边(回边)可以绕过u到达u的祖先,所以u是个关节点

    维基百科上有个动画:(这个动画有点小问题,右边:D2回溯到D1那就可以判断D1为关节点了,还有D4回溯到D2那里没画,当然这是小问题;左边:D3回溯到D2哪里标绿线才对,标错了)
    在这里插入图片描述
    想要它慢点,暂停?用windows media player打开就好

    看下维基上的伪代码:

    GetArticulationPoints(i, d)
        visited[i] = true
        depth[i] = d
        low[i] = d
        childCount = 0
        isArticulation = false
        for each ni in adj[i]
            if not visited[ni]
                parent[ni] = i
                GetArticulationPoints(ni, d + 1)
                childCount = childCount + 1
                if low[ni] >= depth[i]
                    isArticulation = true
                low[i] = Min(low[i], low[ni])
            else if ni != parent[i]
                low[i] = Min(low[i], depth[ni])
        if (parent[i] != null and isArticulation) or (parent[i] == null and childCount > 1)
            Output i as articulation point
    

    C++代码:

    #include<iostream>
    #include<list> 
    #include<algorithm>  //for min
    #define NIL -1
    
    using namespace std;
    class Graph
    {
    	int n;		//图中节点个数
    	list<int>* adj;   //邻接表
    	void APUtil(int v,bool visited[],int depth[],int low[],
    			int parent[],int curDepth,bool AP[]); 
    public:
    	Graph(int _n);
    	void addEdge(int v,int w);
    	void AP();			//求出连通图中的关节点 
    };
    
    Graph::Graph(int _n)
    {
    	n = _n;
    	adj = new list<int>[_n];
    }
    
    void Graph::addEdge(int v,int w)
    {
    	adj[v].push_back(w);
    	adj[w].push_back(v);
    }
    
    void Graph::APUtil(int u,bool visited[],int depth[],int low[],
    			int parent[],int curDepth,bool AP[]) 
    {
    	visited[u] = true;				//已访问 
    	int children = 0;				//孩子数 
    	
    	// 初始化u的深度和能到达的深度最小的祖先 
    	depth[u] = low[u] = curDepth;	
    	
    	list<int>::iterator it;
    	for( it = adj[u].begin(); it != adj[u].end(); it++)
    	{
    		int v = *it;
    		
    		if( !visited[v])		//v没被访问过
    		{
    			parent[v] = u;		//设置v的双亲 
    			children++;			//u的子女+1
    			APUtil(v, visited, depth, low, parent, curDepth + 1, AP); 
    			
    			//访问完v后回溯到这里,检查下u的子孙里有没有那个能
    			//有绕过u能到达的深度最小的祖先,有的话u从子孙那边 
    			//到那个祖先 ,更新low[u] 
    			low[u] = min(low[u], low[v]); 
    			
    			//判断:
    			//1、如果u是根结点(整颗生成树的根,其双亲为-1,即NIL) 
    			//如果children >  1,则u是关节点
    			if( parent[u] == NIL && children > 1)
    			{
    				AP[u] = true; 
    			} 
    			
    			//2、不是根结点,但是有子女v无法绕过它u到它u的祖先w
    			//u是关节点,此时low[v] >= depth[u] 
    			if( parent[u] != NIL && low[v] >= depth[u]) 
    			{
    				AP[u] = true;
    			}
    		}
    		else if( v != parent[u])			 
    		{//v访问过了,说明v是当前节点u的祖先,v找到了一条边(回边到v的祖先),
    		//这里排除下v是u的双亲(因为v是u的双亲的话处理的就不是回边了,这条边在DFS树)
    			low[u] = min(low[u], depth[v]);			//更新low[u]; 
    		} 
    	} 
    }
    
    void Graph::AP()
    {
    	bool *visited = new bool[n];
    	int *parent = new int[n];
    	int *low = new int[n];
    	int *depth = new int[n];
    	bool *AP = new bool[n];
    	
    	for(int i = 0; i < n; i++)
    	{
    		AP[i] = false;
    		parent[i] = NIL;
    		visited[i] = false;
    	} 
    	for(int i = 0; i < n; i++)
    	{
    		if(!visited[i])
    		{
    			APUtil(i,visited,depth,low,parent,0,AP);
    		}
    	}
    	
    	for(int i = 0; i < n; i++)
    	{
    		if(AP[i] == true)
    		{
    			cout<<i<<"  ";
    		}
    	}
    	cout<<endl;
    } 
    

    以动画里图为例测试:

    int main()
    {
    	cout<<"输入图的关节点有:"<<endl;
    	Graph g1(15);
    	g1.addEdge(0,1);
    	g1.addEdge(1,2);
    	g1.addEdge(1,6);
    	g1.addEdge(2,3);
    	g1.addEdge(2,4);
    	g1.addEdge(3,4);
    	g1.addEdge(4,5);
    	g1.addEdge(5,6);
    	g1.addEdge(6,7);
    	g1.addEdge(1,8);
    	g1.addEdge(0,9);
    	g1.addEdge(9,10);
    	g1.addEdge(10,11);
    	g1.addEdge(10,13);
    	g1.addEdge(11,12);
    	g1.addEdge(12,13);
    	g1.AP();
    	return 0; 
    }
    

    结果在这里插入图片描述

    还有一种写法:
    不用深度depth[],用disc[u]最早发现的时间的来记录当前顶点uDFS树在被发现的次序,而low[u]来表示顶点u到达的disc值最小的祖先(不是双亲)。

    void Graph::APUtil(int u,bool visited[],int disc[],int low[],
    			int parent[],int &time,bool AP[]) 
    {
    	visited[u] = true;				//已访问 
    	int children = 0;				//孩子数 
    	
    	// 初始化u的深度和能到达的深度最小的祖先 
    	disc[u] = low[u] = ++time;	
    	
    	list<int>::iterator it;
    	for( it = adj[u].begin(); it != adj[u].end(); it++)
    	{
    		int v = *it;
    		
    		if( !visited[v])		//v没被访问过
    		{
    			parent[v] = u;		//设置v的双亲 
    			children++;			//u的子女+1
    			APUtil(v, visited, disc, low, parent, time, AP); 
    			
    			//访问完v后回溯到这里,检查下u的子孙里有没有那个能
    			//有绕过u能到达的深度最小的祖先,有的话u从子孙那边 
    			//到那个祖先 ,更新low[u] 
    			low[u] = min(low[u], low[v]); 
    			
    			//判断:
    			//1、如果u是根结点(整颗生成树的根,其双亲为-1,即NIL) 
    			//如果children >  1,则u是关节点
    			if( parent[u] == NIL && children > 1)
    			{
    				AP[u] = true; 
    			} 
    			
    			//2、不是根结点,但是有子女v无法绕过它u到它u的祖先w
    			//u是关节点,此时low[v] >= disc[u] 
    			if( parent[u] != NIL && low[v] >= disc[u]) 
    			{
    				AP[u] = true;
    			}
    		}
    		else if( v != parent[u])			 
    		{//v访问过了,说明v是当前节点u的祖先,v找到了一条边(回边到v的祖先),
    		//这里排除下v是u的双亲(因为v是u的双亲的话处理的就不是回边了,这条边在DFS树)
    			low[u] = min(low[u], disc[v]);			//更新low[u]; 
    		} 
    	} 
    }
    void Graph::AP()
    {
    	bool *visited = new bool[n];
    	int *parent = new int[n];
    	int *low = new int[n];
    	int *disc = new int[n];
    	bool *AP = new bool[n];
    	
    	for(int i = 0; i < n; i++)
    	{
    		AP[i] = false;
    		parent[i] = NIL;
    		visited[i] = false;
    	} 
    	
    	int time = 0;
    	for(int i = 0; i < n; i++)
    	{
    		if(!visited[i])
    		{
    			APUtil(i,visited,disc,low,parent,time,AP);
    		}
    	}
    	
    	for(int i = 0; i < n; i++)
    	{
    		if(AP[i] == true)
    		{
    			cout<<i<<"  ";
    		}
    	}
    	cout<<endl;
    }
    

    三、判断是否是双连通图(Biconnect)

    用上面的求关节点算法,求完有关节点必然不是双连通图,但是如果单纯地只想判断下是不是双连通图,只要找第一个关节点就知道,如果没有,还得看是不是连通图。

    bool Graph::isBCUtil(int u,bool visited[],int depth[],int low[],
    			int parent[],int curDepth) 
    {
    	visited[u] = true;				//已访问 
    	int children = 0;				//孩子数 
    	
    	// 初始化u的深度和能到达的深度最小的祖先 
    	depth[u] = low[u] = curDepth;	
    	
    	list<int>::iterator it;
    	for( it = adj[u].begin(); it != adj[u].end(); it++)
    	{
    		int v = *it;
    		
    		if( !visited[v])		//v没被访问过
    		{
    			parent[v] = u;		//设置v的双亲 
    			children++;			//u的子女+1
    		
    			if( isBCUtil(v, visited, depth, low, parent, curDepth + 1) == true) 
    			{
    				return true;
    			}
    			//访问完v后回溯到这里,检查下u的子孙里有没有那个能
    			//有绕过u能到达的深度最小的祖先,有的话u从子孙那边 
    			//到那个祖先 ,更新low[u] 
    			low[u] = min(low[u], low[v]); 
    			
    			//判断:
    			//1、如果u是根结点(整颗生成树的根,其双亲为-1,即NIL) 
    			//如果children >  1,则u是关节点
    			if( parent[u] == NIL && children > 1)
    			{
    				return true;
    			} 
    			
    			//2、不是根结点,但是有子女v无法绕过它u到它u的祖先w
    			//u是关节点,此时low[v] >= depth[u] 
    			if( parent[u] != NIL && low[v] >= depth[u]) 
    			{
    				return true;
    			}
    		}
    		else if( v != parent[u])			 
    		{//v访问过了,说明v是当前节点u的祖先,v找到了一条边(回边到v的祖先),
    		//这里排除下v是u的双亲(因为v是u的双亲的话处理的就不是回边了,这条边在DFS树)
    			low[u] = min(low[u], depth[v]);			//更新low[u]; 
    		} 
    	} 
    	return false;
    }
    
    bool Graph::isBC()
    {
    	bool *visited = new bool[n];
    	int *parent = new int[n];
    	int *low = new int[n];
    	int *depth = new int[n];
    	
    	for(int i = 0; i < n; i++)
    	{
    		parent[i] = NIL;
    		visited[i] = false;
    	} 
    	
    	//isBCUtil返回图中有没有关节点 
    	if( isBCUtil(0,visited,depth,low,parent,0) == true)
    	{
    		return false;
    	} 
    	
    	for(int i = 0; i < n; i++ )
    	{
    		if(visited[i] == false)
    		{//DFS后还有节点没被访问过,连通图都不是 
    			return false;
    		}
    	}
    	return true;
    } 
    

    ============================================================================================================================================================================================================================================================================

    全部代码:

    #include<iostream>
    #include<list> 
    #include<algorithm>  //for min
    #define NIL -1
    
    using namespace std;
    class Graph
    {
    	int n;		//图中节点个数
    	list<int>* adj;   //邻接表
    	void APUtil(int v, bool visited[], int depth[], int low[],
    			int parent[], int curDepth, bool AP[]); 
    	bool isBCUtil(int v, bool visited[], int depth[], int low[],
    			int parent[], int curDepth);
    public:
    	Graph(int _n);
    	void addEdge(int v,int w);
    	void AP();			//求出连通图中的关节点 
    	bool isBC(); 
    };
    
    Graph::Graph(int _n)
    {
    	n = _n;
    	adj = new list<int>[_n];
    }
    void Graph::addEdge(int v,int w)
    {
    	adj[v].push_back(w);
    	adj[w].push_back(v);
    }
    void Graph::APUtil(int u,bool visited[],int depth[],int low[],
    			int parent[],int curDepth,bool AP[]) 
    {
    	visited[u] = true;				//已访问 
    	int children = 0;				//孩子数 
    	
    	// 初始化u的深度和能到达的深度最小的祖先 
    	depth[u] = low[u] = curDepth;	
    	
    	list<int>::iterator it;
    	for( it = adj[u].begin(); it != adj[u].end(); it++)
    	{
    		int v = *it;
    		
    		if( !visited[v])		//v没被访问过
    		{
    			parent[v] = u;		//设置v的双亲 
    			children++;			//u的子女+1
    			APUtil(v, visited, depth, low, parent, curDepth + 1, AP); 
    			
    			//访问完v后回溯到这里,检查下u的子孙里有没有那个能
    			//有绕过u能到达的深度最小的祖先,有的话u从子孙那边 
    			//到那个祖先 ,更新low[u] 
    			low[u] = min(low[u], low[v]); 
    			
    			//判断:
    			//1、如果u是根结点(整颗生成树的根,其双亲为-1,即NIL) 
    			//如果children >  1,则u是关节点
    			if( parent[u] == NIL && children > 1)
    			{
    				AP[u] = true; 
    			} 
    			
    			//2、不是根结点,但是有子女v无法绕过它u到它u的祖先w
    			//u是关节点,此时low[v] >= depth[u] 
    			if( parent[u] != NIL && low[v] >= depth[u]) 
    			{
    				AP[u] = true;
    			}
    		}
    		else if( v != parent[u])			 
    		{//v访问过了,说明v是当前节点u的祖先,v找到了一条边(回边到v的祖先),
    		//这里排除下v是u的双亲(因为v是u的双亲的话处理的就不是回边了,这条边在DFS树)
    			low[u] = min(low[u], depth[v]);			//更新low[u]; 
    		} 
    	} 
    }
    void Graph::AP()
    {
    	bool *visited = new bool[n];
    	int *parent = new int[n];
    	int *low = new int[n];
    	int *depth = new int[n];
    	bool *AP = new bool[n];
    	
    	for(int i = 0; i < n; i++)
    	{
    		AP[i] = false;
    		parent[i] = NIL;
    		visited[i] = false;
    	} 
    	for(int i = 0; i < n; i++)
    	{
    		if(!visited[i])
    		{
    			APUtil(i,visited,depth,low,parent,0,AP);
    		}
    	}
    	
    	for(int i = 0; i < n; i++)
    	{
    		if(AP[i] == true)
    		{
    			cout<<i<<"  ";
    		}
    	}
    	cout<<endl;
    } 
    bool Graph::isBCUtil(int u,bool visited[],int depth[],int low[],
    			int parent[],int curDepth) 
    {
    	visited[u] = true;				//已访问 
    	int children = 0;				//孩子数 
    	
    	// 初始化u的深度和能到达的深度最小的祖先 
    	depth[u] = low[u] = curDepth;	
    	
    	list<int>::iterator it;
    	for( it = adj[u].begin(); it != adj[u].end(); it++)
    	{
    		int v = *it;
    		
    		if( !visited[v])		//v没被访问过
    		{
    			parent[v] = u;		//设置v的双亲 
    			children++;			//u的子女+1
    		
    			if( isBCUtil(v, visited, depth, low, parent, curDepth + 1) == true) 
    			{
    				return true;
    			}
    			//访问完v后回溯到这里,检查下u的子孙里有没有那个能
    			//有绕过u能到达的深度最小的祖先,有的话u从子孙那边 
    			//到那个祖先 ,更新low[u] 
    			low[u] = min(low[u], low[v]); 
    			
    			//判断:
    			//1、如果u是根结点(整颗生成树的根,其双亲为-1,即NIL) 
    			//如果children >  1,则u是关节点
    			if( parent[u] == NIL && children > 1)
    			{
    				return true;
    			} 
    			
    			//2、不是根结点,但是有子女v无法绕过它u到它u的祖先w
    			//u是关节点,此时low[v] >= depth[u] 
    			if( parent[u] != NIL && low[v] >= depth[u]) 
    			{
    				return true;
    			}
    		}
    		else if( v != parent[u])			 
    		{//v访问过了,说明v是当前节点u的祖先,v找到了一条边(回边到v的祖先),
    		//这里排除下v是u的双亲(因为v是u的双亲的话处理的就不是回边了,这条边在DFS树)
    			low[u] = min(low[u], depth[v]);			//更新low[u]; 
    		} 
    	} 
    	return false;
    }
    bool Graph::isBC()
    {
    	bool *visited = new bool[n];
    	int *parent = new int[n];
    	int *low = new int[n];
    	int *depth = new int[n];
    	
    	for(int i = 0; i < n; i++)
    	{
    		parent[i] = NIL;
    		visited[i] = false;
    	} 
    	
    	//isBCUtil返回图中有没有关节点 
    	if( isBCUtil(0,visited,depth,low,parent,0) == true)
    	{
    		return false;
    	} 
    	
    	for(int i = 0; i < n; i++ )
    	{
    		if(visited[i] == false)
    		{//DFS后还有节点没被访问过,连通图都不是 
    			return false;
    		}
    	}
    	return true;
    } 
    int main()
    {
    	cout<<"输入图的关节点有:"<<endl;
    	Graph g1(15);
    	g1.addEdge(0,1);
    	g1.addEdge(1,2);
    	g1.addEdge(1,6);
    	g1.addEdge(2,3);
    	g1.addEdge(2,4);
    	g1.addEdge(3,4);
    	g1.addEdge(4,5);
    	g1.addEdge(5,6);
    	g1.addEdge(6,7);
    	g1.addEdge(1,8);
    	g1.addEdge(0,9);
    	g1.addEdge(9,10);
    	g1.addEdge(10,11);
    	g1.addEdge(10,13);
    	g1.addEdge(11,12);
    	g1.addEdge(12,13);
    	g1.AP();
    	cout<<"g1是不是双连通图:"<<endl;
    	cout<<(g1.isBC() ? "是":"不是")<<endl;
    	
    	cout<<"g2是不是双连通图:"<<endl; 
    	Graph g2(2);
    	g2.addEdge(0,1);
    	cout<<(g2.isBC() ? "是":"不是")<<endl; 
    	
    	cout<<"g3是不是双连通图:"<<endl; 
    	Graph g3(4);
    	g3.addEdge(0,1);
    	g3.addEdge(1,2);
    	g3.addEdge(1,3); 
    	cout<<(g3.isBC() ? "是":"不是")<<endl; 
    	
    	cout<<"g4是不是双连通图:"<<endl;
    	Graph g4(5); 
        g4.addEdge(1, 0); 
        g4.addEdge(0, 2); 
        g4.addEdge(2, 1); 
        g4.addEdge(0, 3); 
        g4.addEdge(3, 4); 
        cout<<(g4.isBC() ? "是":"不是")<<endl; 
      
      	cout<<"g5是不是双连通图:"<<endl;
        Graph g5(3); 
        g5.addEdge(0, 1); 
        g5.addEdge(1, 2); 
        g5.addEdge(2, 0); 
        cout<<(g5.isBC() ? "是":"不是")<<endl; 
    	return 0; 
    }
    

    在这里插入图片描述

    展开全文
  • 连通分量,关节点和桥 ==== ...与无向图相关联还有关节点x,是去掉x,图不连通;桥(u,v)是去掉这条边,图不连通。 求解算法要义在于首先要理解: 树边-前向边-后向边-交叉边 "Conside
    图的连通分量,关节点和桥
    ====
    对于有向图,我们称其一个子图是强连通分量,是指任意两点u,v, 都有两条路径u到v和v到u。

    对于连通无向图,我门称其一个子图是双连通分量,是指任意两点u,v,存在一个圈包含u,v。与无向图相关联的还有关节点x,是指去掉x,图不连通;桥(u,v)是指去掉这条边,图不连通。

    求解算法的要义在于首先要理解:
    树边-前向边-后向边-交叉边
    "Consider what happens when a depth-first search is performed on a directed
    graph G. The set of edges which lead to a new vertex when traversed during the
    search form a tree. The other edges fall into three classes. Some are edges running from ancestors to descendants in the tree. These edges may be ignored, because
    they do not affect the strongly connected components of G. Some edges run from
    descendants to ancestors in the tree; these we may call fronds as above. Other edges run from one subtree to another in the tree. These, we call cross-links."[1] 
    每个强连通分量为搜索树中的一棵子树。

    定义:
     o dfn[u]为节点u搜索的次序编号(时间戳).
     o low[u]为 u所在强连通子图对应的搜索子树的根节点的dfn值(u或u的子树能够追溯到的最早的栈中节点的次序号).
     o 为了处理有向图的交叉边,引入comp[u]表示u属于于哪个连通分量.

    对于边(x,y):
    o (dfn[y] < dfn[x]) 表示这条边是后向边或者交叉边。
    o (0 == comp[y])表示还在栈里面,即这条边不可能是交叉边。
    o (low[y] >= dfn[x]) 表明x搜索树子树的根,即无向图的关节点 ([1] LEMMA5)。
    o (low[y] > dfn[x]) 表明这条边是无向图的桥。

    讨论:
    o 对于无向图讨论强连通没有意义,因为它总是强连通的;对于有向图讨论关节点和桥,结果全是乱的。

    o 求得scc之后,把每个scc缩成一个点,加上原图的边,构成一个有向无环图dag。
    我可以边dfs边构造dag:在 comp[y]不为零时记录dag的边, 在输出scc时增加一个顶点,并添上刚才记录的边。与此有关的一个专利[3], 要是Tarjan先生把他的dfs框架专利了,还容得尔曹唧唧歪歪.

    o Q:把一个有向图变成强连通,至少需要加多少条边?
      A: 在dag中统计入度为零的顶点数s1和出度为零的顶点数s2, 结果为max(s1,s2)。
      证明:不妨设s1>s2, 两组顶点编号为I[1..s1], D[1..s2], 可以这样连:D[1] 连I[2], D[2] 连I[3], ..., D[s2] 连I[s2+1],然后
      I[s2+1] 连I[s2+2],I[s2+2]连I[s2+3],..., I[s1]连I[1]构成一个大外环。

    o Q:把一个无向图变成双连通,至少需要加多少条边?
      A:bcc 缩点后形成一棵树,统计树的叶子数目为s,则结果为(s+1)/2。
      证明[4]:最近公共祖先(LCA)最远的两个叶子连一条边,然后再找下一个LCA最远的两个叶子连一条边,..., 这样两两配对。
      为什么要跟LCA扯上关系,因为这样才能两个半圈不会部分重复。

    o 强连通分量的应用:
    Q: POJ2762 对于一个很大的有向图的任意两点,是否可达,要求复杂度为O(N)。
    A: scc + 缩点 + dfs。
    Q: IOPC2006 给定一个有向图G(V,E),问最多能从G图中删去多少条边,且删了边之后图G的连通性不变。换一种描述:给定一个有向图G(V,E),我们可以改造这个图G中的连边得到新图G’,问图G’中至少要含有多少边,才能满足G’的连通性与图G一致。
    A: scc + 缩点后,按逆拓扑顺序,加入u和u出发的边,检查这些新加入的边是否可删除:
    对于<u,v>, 如果存在x,使得u,x有边,且x到v有路径,则<u,v>可删。[2]
     
    /*
    
    history: 
    2014.04.25  StringBuffer out 改成  LinkedList<Integer> out
    2014.04.29  add Tarjan 
    */
    import java.io.*;
    import java.util.*;
    
    public class Graph
    {
    	int n; /*顶点数*/
    	int[][] adjList;
    	int[] edgeCnt, edgeCap;
    	
    	void trimToSize()
    	{
    		int i;
    		for(i = 0; i < n; ++i){
    			adjList[i] = Arrays.copyOf(adjList[i], edgeCnt[i]);
    		}
    
    		edgeCnt = null; edgeCap = null; 
    	}
    	
    	int addEdge(int v, int w)
    	{
    		if(edgeCnt[v] >= edgeCap[v]){
    			int newCap = edgeCap[v] + 10;
    
    			adjList[v] = Arrays.copyOf(adjList[v], newCap);
    			edgeCap[v] = newCap;
    		}
    		adjList[v][edgeCnt[v]++] = w;
    
    		return 0;
    	}
    
    	int[] getNeighbors(int v)
    	{
    		return adjList[v];
    	}
    
    	void dfs(int v, byte[] color, LinkedList<Integer> out)
    	{
    		int i, w = 0;
    		int[] nei = getNeighbors(v);
    		
    		color[v] = 1;
    		for(i = 0; i < nei.length; ++i){
    			w = nei[i];
    			if(0 == color[w])dfs(w, color, out);
    			else if(1 == color[w]){/*a cycle is found.*/}
    		}
    		color[w] = 2;
    		out.addFirst( v);
    		//System.out.printf("v = %d out = %s %n", v, out);
    	}
    
    	void topoSort(byte[] color, LinkedList<Integer> out )
    	{
    		int i;
    		out.clear();
    		Arrays.fill(color, (byte)0);
    		for(i = 0; i < n; ++i){
    			if(0 == color[i])dfs(i, color, out);
    		}
    	}
    
    	void bfs(int v, byte[] color, LinkedList<Integer> out)
    	{
    		int i, w;
    		int[] nei;
    		LinkedList<Integer> qu = new LinkedList<Integer>();
    	
    		out.clear();
    		Arrays.fill(color, (byte)0);
    		
    		qu.push(v);
    		while(!qu.isEmpty()){
    			v = qu.pop();
    			out.addLast(v);
    			color[v] = 1; /*visited*/
    			
    			nei = getNeighbors(v);
    			for(i = 0; i < nei.length; ++i){
    				w = nei[i];
    				if(0 == color[w])qu.push(w);
    			}
    		}
    	}
    	
    	public Graph(int vertexNum, int edgeNum, Scanner in) throws IOException
    	{/*假设输入顶点数,边数,之后是m对边(v,w)*/
    		
    		int i, v, w;
    
    		n = vertexNum;
    		adjList = new int[n][0];
    		edgeCnt = new int[n];
    		edgeCap = new int[n];
    		for(i = 0; i < n; ++i){
    			edgeCnt[i] = 0;
    			edgeCap[i] = 10;
    			adjList[i] = new int[edgeCap[i]];
    		}
    
    		for(i = 0; i < edgeNum; ++i){
    			v = in.nextInt(); // - 1;
    			w = in.nextInt(); // - 1;
    			addEdge(v, w);
    		}
    		trimToSize();
    	}
    
    }
    
    class Tarjan
    {
    	Graph g;
    	int n;
    	
    	int[] dfn; /*每个顶点的dfn值*/
    	int[] low;/*每个顶点的low值*/
    	int[] stk;/*存储分量顶点的栈*/
    	int stp;
    	int	index; /*搜索次序*/
    
    	int[] comp; /*标记每个顶点属于哪个连通分量*/
    	int compTag;
    
    	int[] cut;/*标记每个顶点是否为割点*/
    	int son; /*根节点孩子个数,大于2则根节点为关节点*/ 
    	int beginVertex;
    
    	public Tarjan(Graph gRef)
    	{/*common context init*/
    		g = gRef;
    		n = g.n;
    		dfn = new int[n]; 
    		low = new int[n]; 
    	}
    	
    	public void SCC()
    	{/*求有向图的强连通分量*/
    		int i;
    		Arrays.fill(dfn, 0);
    		Arrays.fill(low, 0);	
    		stk = new int[n]; stp = 0; 
    		comp = new int[n]; compTag = 0;
    		index = 0;
    	
    		
    		i = 0; //2;
    		for(; i < n; ++i){
    			if(0 == dfn[i])strongConnect(i);
    		}
    		stk = null;
    		comp = null;
    	}
    
    	void strongConnect(int x)
    	{
    		int[] adj;
    		int i, y;
    		
    		stk[stp++] = x;	
    		dfn[x] = low[x] = ++index;
    		adj = g.getNeighbors(x);
    		for(i = 0; i < adj.length; ++i){
    			y = adj[i];
    			if(0 == dfn[y]){
    				strongConnect(y);
    				low[x] = Math.min(low[x], low[y]);
    			}else if((dfn[y] < dfn[x]) && (0 == comp[y])){
    				low[x] = Math.min(low[x], dfn[y]);
    			}	
    		}
    
    		if(low[x] == dfn[x]){
    			++compTag;
    			System.out.printf("SCC(%d): ", compTag);
    			do{
    				y = stk[--stp];
    				comp[y] = compTag;
    				System.out.printf("%d:(%d,%d), ", y, dfn[y], low[y]);
    			}while(y != x);
    			System.out.printf("%n");
    		}
    	}
    
    	public void BCC()
    	{/*求无向图的双连通分量,*/
    		int i;
    
    		Arrays.fill(dfn, 0);
    		Arrays.fill(low, 0);
    		stk = new int[4*n]; stp = 0; 
    		cut = new int[n]; 
    		
    		beginVertex = 0; son = 0;
    		index = 0;
    		biConnect(beginVertex, -1);
    		if(son > 1)cut[beginVertex] = 1;
    		
    		System.out.printf("Cut: ");
    		for(i = 0; i < n; ++i)if(cut[i] > 0)System.out.printf("%d, ", i);
    		System.out.printf("%n");
    
    		stk = null;
    		cut = null;
    	}
    
    	void biConnect(int x, int father)
    	{
    		int i, y, x1, y1;
    		int[] nei;
    
    		dfn[x] = low[x] = ++index;
    		nei = g.getNeighbors(x);
    		for(i = 0; i < nei.length; ++i){
    			y = nei[i];
    			if(y == father)continue;
    
    			if(0 == dfn[y]){
    				stk[stp++] = x; stk[stp++] = y;
    				biConnect(y,x);	
    				low[x] = Math.min(low[x], low[y]);
    
    				if(low[y] >= dfn[x]){
    					System.out.printf("BCC(%d,%d): ", x, y);
    					do{
    						y1 = stk[--stp]; x1 = stk[--stp];
    						System.out.printf("<%d:(%d,%d),%d:(%d,%d)>, ", x1, dfn[x1], low[x1], y1, dfn[y1], low[y1]);
    					}while(dfn[x1] >= dfn[y]);
    
    					System.out.printf("%n");
    				}
    
    				if(x == beginVertex)++son;
    				if(x != beginVertex && low[y] >= dfn[x])cut[x] = 1;
    				
    				if(low[y] > dfn[x])System.out.printf("Bridge <%d %d> %n", x, y);
    					
    			}else if(dfn[y] < dfn[x]){
    				stk[stp++] = x; stk[stp++] = y;
    				low[x] = Math.min(low[x], dfn[y]);
    			}	
    		}
    	}
    
    }
    
    class Test
    {
    	public static void main (String[] arg) throws IOException
    	{
    		int n, m;
    		byte[] color; /*for dfs: 0--white, 1--gray, 2--black*/
    		LinkedList<Integer> out = new LinkedList<Integer>();
    
    		Scanner in = new Scanner(System.in);
    		n = in.nextInt();
    		m = in.nextInt();
    		color = new byte[n];
    
    		Graph g = new Graph(n, m,  in);
    		in.close();
    		in = null;
    
    		Arrays.fill(color, (byte)0);
    		g.dfs(0, color, out);
    		System.out.println("dfs: " + out);
    		
    		g.bfs(0, color, out);
    		System.out.println("bfs: " + out);
    
    		g.topoSort(color, out);
    		System.out.println("topoSort: " + out);
    		color = null;
    		out = null;
    
    		Tarjan t = new Tarjan(g);
    		t.SCC();
    		t.BCC();
    
    	}
    }
    

    对于这个图的输出结果:



    ludi@msys ~/java
    $ cat in.txt
    8 14
    0 1
    1 2 1 4 1 5
    2 3 2 6
    3 2 3 7
    4 0 4 5
    5 6
    6 5 6 7
    7 7

    ludi@msys ~/java
    $ javac -encoding UTF-8 Graph.java  && cat in.txt | java Test
    dfs: [0, 1, 4, 2, 6, 5, 3, 7]
    bfs: [0, 1, 5, 6, 7, 4, 2, 3]
    topoSort: [0, 1, 4, 2, 6, 5, 3, 7]
    SCC(1): 7:(5,5),
    SCC(2): 5:(7,6), 6:(6,6),
    SCC(3): 3:(4,3), 2:(3,3),
    SCC(4): 4:(8,1), 1:(2,1), 0:(1,1),
    BCC(3,7): <3:(4,4),7:(5,5)>,
    Bridge <3 7>
    BCC(2,3): <2:(3,3),3:(4,4)>,
    Bridge <2 3>
    BCC(6,5): <6:(6,6),5:(7,7)>,
    Bridge <6 5>
    BCC(2,6): <6:(6,5),7:(5,5)>, <2:(3,3),6:(6,5)>,
    Bridge <2 6>
    BCC(1,2): <1:(2,2),2:(3,3)>,
    Bridge <1 2>
    BCC(0,1): <4:(8,1),5:(7,7)>, <4:(8,1),0:(1,1)>, <1:(2,1),4:(8,1)>, <0:(1,1),1:(2,1)>,
    Cut: 1, 2, 3, 6,


    对这个无向图的输出结果:


    5 10
    0 1 0 4
    1 0 1 2 
    2 1 2 3 2 4 
    3 2 
    4 0 4 2

    $ javac -encoding UTF-8 Graph.java  && cat in.txt | java Test
    dfs: [0, 1, 2, 4, 3]
    bfs: [0, 4, 2, 3, 1, 1]
    topoSort: [0, 1, 2, 4, 3]
    SCC(1): 4:(5,1), 3:(4,3), 2:(3,1), 1:(2,1), 0:(1,1),
    BCC(2,3): <2:(3,3),3:(4,4)>,
    Bridge <2 3>
    BCC(0,1): <4:(5,1),0:(1,1)>, <2:(3,1),4:(5,1)>, <1:(2,1),2:(3,1)>, <0:(1,1),1:(2,1)>,
    Cut: 2,


     
    [1] R. Tarjan Depth-First Search and Linear Graph Algorithms.
    [2] 浅谈强连通分量与拓扑排序的应用 http://3y.uu456.com/bp-01a8sfefsef7ba0d4a733b3e-1.html.
    [3] 标识强连通分量的入口和出口的技术 http://www.google.com/patents/CN102279738A?cl=zh
    [4] 点连通度与边连通度 https://www.byvoid.com/blog/biconnect/
    展开全文
  • Metacarpal=手掌接近手腕的关节 Knuckle=手指根关节 Middle=手指中间关节 Distal=手指最外一个关节 tip=指尖 以下是mrtk中定义的关节位置,自行组合即可 None Wrist=手腕 Palm=手掌 ThumbMetacarpalJoint ...

    Thumb=拇指

    index=食指

    middle=中指

    ring=无名指

    pink=小指

    Metacarpal=手掌接近手腕的关节

    Knuckle=手指根关节

    Middle=手指中间关节

    Distal=手指最外一个关节

    tip=指尖

    以下是mrtk中定义的关节位置,自行组合即可

    None

    Wrist=手腕

    Palm=手掌

    ThumbMetacarpalJoint

    ThumbProximalJoint

    ThumbDistalJoint

    ThumbTip

    IndexMetacarpal

    IndexKnuckle

    IndexMiddleJoint

    IndexDistalJoint

    IndexTip

    MiddleMetacarpal

    MiddleKnuckle

    MiddleMiddleJoint

    MiddleDistalJoint

    MiddleTip

    RingMetacarpal

    RingKnuckle

    RingMiddleJoint

    RingDistalJoint

    RingTip

    PinkyMetacarpal

    PinkyKnuckle

    PinkyMiddleJoint

    PinkyDistalJoint

    PinkyTip
     

     

    展开全文
  • 指关节手势截屏一直是华为手机一大卖点,一般用过指关节手势截屏用户,大多数一上手就离开不了这个功能。通过指关节手势截屏,我们可以自由地控制截图区域,从而达到自己需求目的。目前安卓手机比较常见截屏...

    指关节手势截屏一直是华为手机的一大卖点,一般用过指关节手势截屏的用户,大多数一上手就离开不了这个功能。通过指关节手势截屏,我们可以自由地控制截图区域,从而达到自己的需求目的。

    75d6d5251dc32945d83797572988b372.png

    目前安卓手机比较常见的截屏方式一般有两种情况:一种截屏方式是长按关机键和音量上键,等待1-2秒后提示截屏完成。另外一种截屏方式是打开下拉状态栏,点一下截图按钮 ,就可完成截屏的操作、。部分手机有三指下滑截屏的功能等。

    e948cc65c4b3bf6676cbc23067d0eb08.png

    相对于传统的截屏方式,华为家的指关节手势截屏最大的特点就是可以根据自己的需求来进行灵活化的截屏。比如区域截屏,长截屏等都可以通过华为家的指关节手势截屏来解决。以区域截屏为例,一般手机需要先截全屏,然后再打开图库app找到截图的文件,然后再进行编辑,这些步骤比较麻烦。如果我们用指关节手势截屏的话,,只需要一根指关节,圈出需要截屏的部分内容,然后直接保存就可以了,正好节省了我们打开图库和找截屏文件并进行编辑的时间。

    2bad57b083886b931f9af56edeaabf8f.png

    那么指关节手势截屏具体有哪些操作呢?经过小编这段时间的上手,发现华为的指关节手势截屏具体分为三种:截全屏,长截屏以及区域截屏等。接下来针对这三种截屏方式,容小编给大家一一讲解一下。

    截全屏:华为手机传统的截屏方案上面已经说明了,实际上一些华为低端机并没有指关节手势截屏,但是华为在这些千元机上加了“三指下滑截屏”的操作,虽然也是手势截屏,但是相对于指关节截屏来说,三指下拉截屏实在太鸡肋了。用指关节手势截屏操作截全屏的方法也很简单,只需要一个指关节,在屏幕敲两下,然后截屏就完成了。嗯~是的,你没听错,就是这么简单。

    8ef4b0094359f44c04f0a8c4551152ab.gif

    长截屏:传统手机长截屏的操作方案是先截屏然后再点击长截图就可以实现长截屏操作了。这样的话我们需要进行两个过程,还是比较繁琐的。运用指关节截屏的话我们只需要在屏幕画一个“S”字母,手机就会自动进行长截屏操作了。

    305360215444db0caef801a1317ab594.gif

    区域截屏:区域截屏的传统方法小编在上面已经举例说明了,在这里小编就不多介绍了。关于区域截屏,我们只需要用一根指关节,圈定自己想要的区域内容,然后点击保存就可以了。相对于传统的方式,指关节手势截屏更是简单粗暴。

    f0734d4cbb6d0c7cb9aaf2239f294373.gif

    看到这儿,所以你明白为什么之前被取消指关节截屏的手机用户疯狂要求华为,一定要把指关节截屏加回来的原因了吧。指关节截屏这个功能属实是非常好用的一个功能,但是很多用户不知道这个功能,所以小编特意针对这个功能开了这个贴,希望更多的朋友能看到。

    展开全文
  • ** 机械臂轨迹规划 ...在关节空间中进行轨迹规划是关节变量表示为时间函数,用此矢函数及其一阶二阶导数描述操作臂预期运动。在直角坐标中进行轨迹规划是将手部位姿表示为实践函数,而相应的关节
  • 在常见慢性关节疾病中,类风湿性关节炎无疑是最严重一种,因为类风湿非常顽固,患者患类风湿之后几乎终生离不开药物治疗,一旦治疗不得当很容易造成关节畸形甚至残疾。类风湿最佳治疗时间无疑是在患病初期,这...
  • 初识Box2D关节b2Joint

    千次阅读 2013-06-23 14:04:04
    在让刚体听我-鼠标控制中,我们学会了鼠标拖动Box2D刚体,另外我还提到了关节,那么今天我们就来讨论一下Box2Db2Joint关节类。 在医学上,骨与骨之间连接地方称为关节。在Box2D中,刚体与刚体之间连接...
  • OpenCV基于OpenPose手部关键点检测概述✔️ 手部关键点检测,旨在找出给定图片中手指上的关节点及指尖关节点, 其中手部关键点检测应用场景主要包括:手势识别手语识别与理解手部行为识别✔️ OpencvDNN手部...
  • OpenPose 基于OpenCV DNN 手部关键检测

    万次阅读 热门讨论 2019-05-30 21:38:35
    手部关键点检测,旨在找出给定图片中手指上的关节点及指尖关节点. 其类似于面部关键点检测(Facial Landmark Detection) 和人体关键点检测(Human Body Pose Estimation);不同之处是,整个手部是作为一个目标物体. ...
  • OpenCV基于OpenPose手部关键点检测概述✔️ 手部关键点检测,旨在找出给定图片中手指上的关节点及指尖关节点, 其中手部关键点检测应用场景主要包括:手势识别手语识别与理解手部行为识别✔️ OpencvDNN手部...
  • 手部关键点检测,旨在找出给定图片中手指上的关节点及指尖关节点. 其类似于面部关键点检测(Facial Landmark Detection) 和人体关键点检测(手部关键点检测应用场景包括:[1] - 手势识别[2] - 手语识别与理解[3] - ...
  • 集成华为手部关键识别服务轻松识别手语字母 介绍 华为机器学习(ML Kit)提供手部关键识别服务,可用于手语识别。...这里尝试的是手势当中的美国手语字母表,是基于关节,手指和手腕的位置进行分
  • 【判断题】V 带(三角带)传动传动比随外载荷变化而变化。 (【简答题】如图所示为某型号机械手臂运动轨迹,请根据运动轨迹完善程序,使用工具为 tool1,工件坐标... ( )【判断题】最大工作速度通常机器人单关节速...
  • 手部关键检测是在手指上找到关节以及在给定图像中找到指尖过程。它类似于在脸部(面部关键检测)或身体(人体姿势估计)上找到关键。但是手部检测不同地方在于,我们将整个手部视为一个对象。 美国卡耐基...
  • 对于利用moveit控制真实的机械臂的流程一、首先假设你的底层的硬件控制是完成了的二、保证你...前一个jointstate指的是你自己获取到的机械臂的实时的关节状态,而后一个指的就是我们最终在文章结束后得到的一系列的路
  • 一、工业机构名词解释:1、关节(Joint):即运动副,允许机器人手臂各零件...5、定位精度(Positioning accuracy):机器人末端参考实际到达位置与所需要到达理想位置之间差距。6、重复性(Repeatability
  • pose初体验

    2019-06-05 00:04:00
    所谓pose的识别任务指的是对人体的身体关节点进行识别 其中主要的数据集包括coco数据集以及mpii 数据集 此次我用的是mpii数据集。 mpii数据集 { 0 - r ankle, 1 - r knee, 2 - r hip,3 - l hip,4 - l knee, 5 - ...
  • 连杆间速度传递

    2020-09-19 23:57:51
    注意线速度是相对于一点的的,而角速度是相对于一个物体的,因此,“连杆的速度”指的是连杆坐标系原点的线速度和连杆的角速度。 如上图所示,将机构的每一个连杆看作为一个刚体,可以用线速度矢量和角速度矢量描述...
  • 大家都知道我们华为手机有很多好用功能,但是华为必备录屏方法,你都用过吗?接下来就和小编一起看看吧!1.下拉菜单栏第一个方法非常...2.双指关节轻扣屏幕大家都知道用指关节单击屏幕可以截屏,甚至是画出...
  • 手持华为p30,之前是小米六,用惯了MIUI之后感觉华为用户体验简直就是反人类,其反人类体验如下:1、指关节敲击截屏,我就不说这有多难受了,很多情况下截不到屏,还容易开应用里拓展选项,对比米六截屏...
  • 最小二乘和伪逆矩阵伪逆矩阵在机械臂范围外时候,轨迹混乱最小二乘法在上个情况下,机械臂直target 3.伪逆矩阵两个不共享关节的可以通过不同UI界面调用伪逆矩阵完成轨迹规划4.伪逆矩阵两个不共享关节,但是第...
  • 工厂员工辞职信范文【三篇】 【篇一】 尊敬领导: 您好! 201x年7月8日我来到成为生产一部...可是由于每天长时间在车间工作,可能是因为不适应车间环境,经常感觉手指和腿部关节疼痛,最近更是越来越难以?..
  • 长期卧床患者易得压疮,压疮即压力性损伤,是患者皮肤或皮下组织由于长期受压,发生持续缺血缺氧、营养不良,而至组织溃烂甚至坏死情况。照顾长期卧床患者,只要护理得当,压疮也可以预防。西安市民高大爷...
  • 一切都在于时间(Timing)和空间幅度(Spacing) 第一课 回到1940年 标尺(Chart)和中间画(Inbetween)演变 原画和小原画(Breakdown) 关键张 三种动画方式 测试测试再测试 摄影表(X-sheet) 你是一个热衷K·I·S·S人...
  •  爷爷体弱多病,前年又得了脑血管病,现在虽然生活能够自理,但不能干活,奶奶是多年类风湿,手指和脚趾关节已严重变形,别说干活,就连照顾弟弟都成问题。我们家地又少,地里每年没什么收入,全家经济****就靠...
  • 琵琶按弦学习

    2015-12-18 11:24:15
    按弦是左手最最基本也最最重要的指法。在按弦中,最容易出现按弦不实、不准的现象。 按弦时,左手四指关节应自然弯曲呈孤状,不宜作平直的姿势。...落指的位置即触弦必须准确,正确位置应在紧挨相、品的上方,
  •  爷爷体弱多病,前年又得了脑血管病,现在虽然生活能够自理,但不能干活,奶奶是多年类风湿,手指和脚趾关节已严重变形,别说干活,就连照顾弟弟都成问题。我们家地又少,地里每年没什么收入,全家经济****就靠...
  • 工业机器人特别是垂直多关节机器人(俗称关节机器人或者六关节机器人)控制问题,不能简单等同于一般运动控制(传统通过位置控制、速度控制或者转矩控制简单运动控制系统)问题。 为什么垂直多关节...

空空如也

空空如也

1 2 3 4 5
收藏数 94
精华内容 37
关键字:

关节点指的是