Problem in classifying graph edges

Asked

Viewed 50 times

1

I’m making an algorithm to classify the Edges of a graph, between Type T, B ,C and F. It’s giving me a wrong output, it finishes vertex 3 at the same time it starts 4, so it doesn’t end up classifying the Edge that has 4 to 3.

Main java.

package Grafos;

public class Main {

    public static void main(String[] args) {
        Grafo novo = new Grafo(8);
        novo.Adiciona_aresta(0,7);
        novo.Adiciona_aresta(1,0);
        novo.Adiciona_aresta(1,6);
        novo.Adiciona_aresta(7,1);
        novo.Adiciona_aresta(6,7);
        novo.Adiciona_aresta(2,1);
        novo.Adiciona_aresta(2,6);
        novo.Adiciona_aresta(5,6);
        novo.Adiciona_aresta(5,2);
        novo.Adiciona_aresta(3,5);
        novo.Adiciona_aresta(3,4);
        novo.Adiciona_aresta(4,5);
        novo.Adiciona_aresta(4,3);
        //novo.DFS_ini(0);
        //novo.Pilha_DFS(0);
        novo.Classificar_Arestas(2);
    }

}

Java graph.

package Grafos;
import java.io.*;
import java.net.SocketTimeoutException;
import java.util.*;
public class Grafo {
    LinkedList<Integer> Arestas [];
    private int n;


    public Grafo(int n){
        this.n = n;
        Arestas = new LinkedList[n];
        for (int i=0; i<n; ++i)
            Arestas[i] = new LinkedList();
    }
    public void Adiciona_aresta(int origem, int destino){
        Arestas[origem].add(destino);

    }

    public int DFS(int S, boolean visited[], int contador){
        visited[S] = true;
        int m;
        ListIterator<Integer> v = Arestas[S].listIterator();
        while(v.hasNext()) {
            m = v.next();
            System.out.println(S + ">>" + m);
            if(!visited[m]){
                contador = DFS(m,visited,contador+1);
            }
        }
        return contador+1;

    }

    public void DFS_ini(int S){
        boolean Visitados[] = new boolean [n];
        int contador = 1;
        int b = DFS(S,Visitados,contador);
        System.out.println(b);
        System.out.println("____________________________________________________");
    }

    public int Verificar_Arestas(int S, boolean visited[], int contador, int d[], int f[]){ //classificar arestas
        visited[S] = true;
        d[S] = contador;
        int m;
        ListIterator<Integer> v = Arestas[S].listIterator();
        while(v.hasNext()){
            m = v.next();
            if(!visited[m]){
                System.out.println(S + " >> " + m);
                System.out.println("Tipo T");
                contador = Verificar_Arestas(m,visited,contador+1,d,f);

            }else{
                System.out.println(S + " >> " + m);
                if((d[S] > d[m] && f[m] == 0)||(d[S] > d[m] && d[S] < f[m])){

                    System.out.println("Tipo B");
                }
                else if(d[S] > f[m]){
                    System.out.println("Tipo C");
                }else if(d[S] < d[m]) {
                    System.out.println("Tipo F");
                }
            }
            f[S] = contador + 1;
        }
        return contador+1;

    }

    public void Classificar_Arestas(int S){ // método que inicia
        int f [] = new int [n];
        int d [] = new int [n];
        boolean visited[] = new boolean [n];
        int contador = 1;

        int b = Verificar_Arestas(S,visited,contador,d,f);
        for(int i = 0; i < n; i++) { //for para verificar caso tenha outra parte do grafo
            if(!visited[i]){
                b = b + Verificar_Arestas(i,visited,b+1,d,f);
            }
        }

    }
    public void Pilha_DFS(int s) {
        boolean[] visitados = new boolean[10];
        visitados[s] = true;
        Pilha<Integer> pilha = new PilhaArrayList<>();
        pilha.push(s);
        while (!pilha.isEmpty()) {
            int topo = pilha.pop();
            for (int linha : Arestas[topo]){
                System.out.println(topo + ">>" + linha);
                    if (visitados[linha]) continue;
                    visitados[linha] = true;
                    pilha.push(linha);
            }
        }
        System.out.println("____________________________________________________");
    }

}
No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.