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("____________________________________________________");
}
}