图论

基于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;

}