Graph_Java/Bipartido.java at main · mlziade/Graph_Java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package java.grafo;

import java.util.ArrayList;
import java.util.List;

public class Bipartido extends Grafo{

    private static int AZUL = 0;
    private static int VERDE = 0;

    private int[] azul;
    private int qtdAzul;
    private int[] verde;
    private int qtdVerde;

    public Bipartido(Grafo g){
        Lista aux = g.prim;
        int totalNos = 0;
        while(aux != null){
            totalNos += 1;
            aux = aux.prox_no;
        }

        this.azul = new int[totalNos];
        this.qtdAzul = 0;
        this.verde = new int[totalNos];
        this.qtdVerde = 0;
    }

    void addNaCor(int no, int cor){
        if(cor == AZUL){
            azul[qtdAzul] = no;
            qtdAzul += 1;
        }
        if(cor == VERDE){
            verde[qtdVerde] = no;
            qtdVerde += 1;
        }
    }

    boolean pertenceCor(int no, int cor) {
        if (cor == AZUL) {
            for (int i = 0; i < qtdAzul; i++) {
                if (this.azul[i] == no) return true;
            }
        }
        if (cor == VERDE) {
            for (int i = 0; i < qtdVerde; i++) {
                if (this.verde[i] == no) return true;
            }
        }
        return false;
    }

    public boolean analisaBipartido(Grafo g){
        if((g.prim == null) || (g.prim.prox_no == null)) return false;
        List<Integer> cjtoU = new ArrayList<>();
        List<Integer> cjtoV = new ArrayList<>();
        Lista p = g.prim;

        while(p != null){
            Vizinho viz = p.prox_viz;
            while(viz != null){
                int i;
                for(i = 0; i < cjtoV.size(); i++){
                    int elem = cjtoV.get(i).intValue();
                    if(elem == viz.no_viz) break;
                }
                if(i < cjtoV.size()) break;
                viz = viz.prox;
            }
            if(viz == null) cjtoV.add(p.no);
            else{
                viz = p.prox_viz;
                while(viz != null){
                    int i;
                    for(i = 0; i < cjtoU.size(); i++){
                        int elem = cjtoU.get(i).intValue();
                        if(elem == viz.no_viz) break;
                    }
                    if(i < cjtoU.size()) break;
                    viz = viz.prox;
                }
                if(viz != null) return false;
                cjtoU.add(p.no);
            }
            p = p.prox_no;
        }
        return true;
    }

}