Advertisement
Viniciusfelbs

Untitled

Nov 25th, 2020
674
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.88 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class grafo {
  4.     public static void main(String[] args) {
  5.         Scanner s = new Scanner(System.in);
  6.         int v = 13;
  7.         int matriz [][] = new int[v][v];
  8.         matriz[0][1] = 1;
  9.         matriz[0][2] = 1;
  10.         matriz[0][5] = 1;
  11.         matriz[0][6] = 1;
  12.         matriz[1][0] = 1;
  13.         matriz[2][0] = 1;
  14.         matriz[3][5] = 1;
  15.         matriz[3][4] = 1;
  16.         matriz[4][3] = 1;
  17.         matriz[4][5] = 1;
  18.         matriz[4][6] = 1;
  19.         matriz[5][0] = 1;
  20.         matriz[5][3] = 1;
  21.         matriz[5][4] = 1;
  22.         matriz[6][0] = 1;
  23.         matriz[6][4] = 1;
  24.         matriz[7][8] = 1;
  25.         matriz[8][7] = 1;
  26.         matriz[9][10] = 1;
  27.         matriz[9][11] = 1;
  28.         matriz[9][12] = 1;
  29.         matriz[10][9] = 1;
  30.         matriz[11][9] = 1;
  31.         matriz[11][12] = 1;
  32.         matriz[12][9] = 1;
  33.         matriz[12][11] = 1;
  34.  
  35.         buscaProfundidade(matriz, v);
  36.      
  37.     }
  38.  
  39.     public static void buscaProfundidade(int [][]grafo, int v){
  40.         boolean resposta = false;
  41.         boolean []  marcado = new boolean[v];
  42.         for(int j = 0; j < v; j++){
  43.             if(!marcado[j]){
  44.                 resposta = dfs(grafo, j, marcado);
  45.             }
  46.         }
  47.         if(resposta == true){
  48.             System.out.println("não é acíclico");
  49.         }else{
  50.             System.out.println("Aciclico");
  51.         }
  52.  
  53.     }
  54.     public static boolean dfs(int [][] grafo, int v, boolean[] marcado){
  55.         marcado[v] = true;
  56.         boolean ciclo = false;
  57.         for(int i = 0; i < grafo[0].length; i++){
  58.             if(grafo[v][i]==1){
  59.                 if(marcado[v] && marcado[i]){
  60.                      ciclo = true;
  61.                 }
  62.                 if(!marcado[i]){
  63.                     dfs(grafo, i, marcado);
  64.                 }
  65.             }
  66.         }
  67.         return ciclo;
  68.     }
  69.     //não é acíclico
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement