Не работает ли алгоритм Тарьяна для этого теста? ссылки: GFG и учебник Тушар Роя - PullRequest
Новая
       42

Не работает ли алгоритм Тарьяна для этого теста? ссылки: GFG и учебник Тушар Роя

0 голосов
/ 11 июня 2019

Тестовый пример: Есть 3 вершины 1,2,3 таких

edge: source-destination 

1-2
1-3
2-3

Поскольку dfs переходит от 1 к 2, а затем к 3.Ниже приведены данные об обнаружении и низком времени: 

1 discT:0,lowT:0;

2 discT:1,lowT:1;

3 discT:2,lowT:2;

Поскольку время на диске 2 меньше времени на 3.2 становится точкой артикуляции из-за теоремы, которая НЕ ДОЛЖНА БЫТЬ.

Я делаю что-то не так.Пожалуйста, объясните.Ниже моя функция DFS -> 

public void dfs(){
             ArrayDeque<vertex> st=new ArrayDeque<>();
             st.push(vertexList.get(0));
             int pt=1;
            vertexList.get(0).discTime=0;
            vertexList.get(0).lowTime=0;
            vertexList.get(0).visited=true;
            int numberOfverticesCovered=0;
             while(!st.isEmpty()){
                 vertex v=st.peek();
                 System.out.println("considering "+v.label);
                 vertex p=getAdjacent(v);
                 if(p==null)
                 {
                     System.out.println("left with no unvisited adjacent vertices "+v.label);
                     if(v!=vertexList.get(0)){
                         LinkedList<edge> le=adjList.get(v.label-1);
                         for (edge e : le)
                         {
                                 if(v.discTime<=e.destination.lowTime)
                                 {
                                    artPoints.add(v);
                                     System.out.println("new articulation point found "+v.label+" for edge "+e.source.label+" and "+e.destination.label);
                                     System.out.println("disc time of "+v.label+"  is "+v.discTime+" and low time is "+v.lowTime);
                                     System.out.println("disc time of adj "+e.destination.label+"  is "+e.destination.discTime+" and low time is "+e.destination.lowTime);
                                    break;
                                 }
                                    v.lowTime=Math.min(v.lowTime, e.destination.lowTime);
                                    System.out.println("new low time of "+v.label+"  is "+v.lowTime);
                         }
                     }
                     numberOfverticesCovered+=1;
                     st.pop();
                 }
                 else
                 {
                     v.children+=1;
    //                 System.out.println("adding child "+p.label+" to parent "+v.label);
                     p.discTime=pt;
                     p.lowTime=pt;
                     p.parent=v;
                     st.push(p);
                     pt+=1;
                 }
                 if(st.isEmpty()&& numberOfverticesCovered!=vertexList.size()){
                     for (vertex object : vertexList) {
                         if(!object.visited)
                         {
                             object.discTime=pt;
                             object.lowTime=pt;
                             object.visited=true;
                             st.push(object);
                             break;
                         }
                     }
                 }
             }

             if(vertexList.get(0).children>1 ) //  put in check for back edge for the other children so that they are not connected to each other.
             {             
                 artPoints.add(vertexList.get(0));
                 System.out.println("added root as an articulation point and it has "+vertexList.get(0).children);
             }

         } 

    }
...