無方向図の判環

(1)まず無方向図の判断アルゴリズムを紹介し,これは比較的簡単である.
無方向図にループ(ループ)が存在するか否かを判断するアルゴリズム記述
ループが存在する場合は、必ずサブマップが存在し、ループです.ループ内のすべての頂点の度>=2.
アルゴリズム:
ステップ1:すべての度<=1の頂点と関連するエッジを削除し、これらのエッジに関連する他の頂点の度を1つ減らします.
ステップ2:度数が1になった頂点をキューに並べ、そのキューから頂点を取り出して手順1を繰り返します.
最後に削除されていない頂点がある場合は、ループが存在します.そうでない場合は、ループはありません.
アルゴリズム解析:
m個のエッジがあるため、n個の頂点があります.m>=nの場合,グラフィック知識に基づいてループの存在を直接判断できる.
(証明:ループがなければ、この図は必然的にk本の木k>=1である.木の性質によって、辺の数m=n-k.k>=1であるため、mm 
(2)dfsでループを判定する.
dfsで判断するときは判断が必要です
例えば4−5の場合,4から5にアクセスし,5からその周辺ノードにアクセスを開始する場合,4ノードは再アクセスする必要はない.

int dfs(int u,int p)//u         ，p          。
{
	if(vis[u])//        ，    。           
     {
     	return 1;
     }
	vis[u]=1;
	int m=V[u].size();
	for(int i=0;i<m;i++)
	{
		int v=V[u][i];
		if(v!=p)//               ，   。
	    dfs(v,u);
	}
	return 0;
}