Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class grafo {
- public static void main(String[] args) {
- Scanner s = new Scanner(System.in);
- int v = 13;
- int matriz [][] = new int[v][v];
- matriz[0][1] = 1;
- matriz[0][2] = 1;
- matriz[0][5] = 1;
- matriz[0][6] = 1;
- matriz[1][0] = 1;
- matriz[2][0] = 1;
- matriz[3][5] = 1;
- matriz[3][4] = 1;
- matriz[4][3] = 1;
- matriz[4][5] = 1;
- matriz[4][6] = 1;
- matriz[5][0] = 1;
- matriz[5][3] = 1;
- matriz[5][4] = 1;
- matriz[6][0] = 1;
- matriz[6][4] = 1;
- matriz[7][8] = 1;
- matriz[8][7] = 1;
- matriz[9][10] = 1;
- matriz[9][11] = 1;
- matriz[9][12] = 1;
- matriz[10][9] = 1;
- matriz[11][9] = 1;
- matriz[11][12] = 1;
- matriz[12][9] = 1;
- matriz[12][11] = 1;
- buscaProfundidade(matriz, v);
- }
- public static void buscaProfundidade(int [][]grafo, int v){
- boolean resposta = false;
- boolean [] marcado = new boolean[v];
- for(int j = 0; j < v; j++){
- if(!marcado[j]){
- resposta = dfs(grafo, j, marcado);
- }
- }
- if(resposta == true){
- System.out.println("não é acíclico");
- }else{
- System.out.println("Aciclico");
- }
- }
- public static boolean dfs(int [][] grafo, int v, boolean[] marcado){
- marcado[v] = true;
- boolean ciclo = false;
- for(int i = 0; i < grafo[0].length; i++){
- if(grafo[v][i]==1){
- if(marcado[v] && marcado[i]){
- ciclo = true;
- }
- if(!marcado[i]){
- dfs(grafo, i, marcado);
- }
- }
- }
- return ciclo;
- }
- //não é acíclico
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement