基于DFS求无向连通图的环
对于每一个连通分量，如果无环则只能是树，即：边数＝结点数－1
只要有一个满足 边数 > 结点数－1 原图就有环，环的个数为：边的个数-顶点个数+1；
public Map<Integer,List<Integer>> getRings(){
//用来记录结点访问状态的数组，0----还未访问；1-----正在进行访问 2------------已访问完
visit=new int[nVerts];
//记录当前结点已经访问过的结点，并记录了父子结点关系
parent=new int[nVerts];
//用来存储图中的环
Map<Integer,List<Integer>> ringsMap=new HashMap<>();
//int source=sources.iterator().next();
int source=1;
visit[source]=1;
stackX.push(source);
int count=0;
int u=source;//记录上一个访问顶点
//标记逆向边的访问
while (!stackX.isEmpty()){
//int v=getNextUnvisitedVertex1(stackX.peek());
int v=-1;
u=stackX.peek();
Link current=adjTable.hashArray[u].first;
while (current!=null){
if (visit[current.getId()]==0){
//树边
v=current.getId();
break;
}
//u->v逆向边，且满足以下情况：
//1，u和v不是父子关系
//2，u->v首次访问,如果不是首次访问，则ringsMAp中已经包含这两个顶点
boolean marked=false;
for(List ringSet:ringsMap.values()){
if (ringSet.contains(adjTable.hashArray[u].find(current.getId()).pipeID)){
marked=true;
break;
}
}
if (visit[current.getId()]==1&&parent[u]!=current.getId()
&&parent[current.getId()]!=u&&marked==false){
//回边
//判断该回边是否已经访问u-》v
// System.out.println("存在环");
//通过parent去反向查找
List ring=new ArrayList<>();
ring.add(current.pipeID);//1
int p=u;
int last=u;
while (p!=current.getId()){
// ring.add(p);
last=p;
p=parent[p];
ring.add(adjTable.hashArray[last].find(p).pipeID);
}
//如果已经有了，就不再输出
ringsMap.put(count++,ring);
current=current.next;
}
else {
current=current.next;
}
}
if (v==-1){
visit[stackX.pop()]=2;
}
else {
visit[v]=1;
parent[v]=u;
// System.out.println(v);
stackX.push(v);
}
}
//reset
for (int i=0;i
visit[i]=0;
}
return ringsMap;
}
