Informatika gyűjtemény

Egy szinttel feljebb Graf.java

2004050607080910

<<  8. óra - Floyd-Warshall algoritmus  >>

<<  Szerkezetek  >>

NézetNyomtat

Graf.java (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 2 KB
package hu.krivan.szakkor.szerkezetek;

import java.util.ArrayList;

/**
 *
 * @author Bálint Kriván
 */
public class Graf {

    public int g,  r;
    public int[][] d;

    private static int infinity = 100;

    public Graf(ArrayList<String> edges) {
        String first_ = edges.remove(0);
        String[] first = first_.split(" ");
        g = Integer.valueOf(first[0]);
        r = Integer.valueOf(first[1]);
        d = new int[g][g];
        for (int a = 0; a < g; a++) {
            for (int b = 0; b < g; b++) {
                d[a][b] = infinity;
                if (a == b) {
                    d[a][b] = 0;
                }
            }
        }

        int g1, g2;
        String[] points;
        for (String edge : edges) {
            points = edge.split(" ");
            g1 = Integer.valueOf(points[0]);
            g2 = Integer.valueOf(points[1]);
            // itt jön a luxus :)
            d[g1 - 1][g2 - 1] = 1;
            d[g2 - 1][g1 - 1] = 1;
        }
    }

    /**
     * Kiíratjuk a csúcsmátrixot -- for debugging purposes.
     */
    public void print() {
        for (int a = 0; a < g; a++) {
            for (int b = 0; b < g; b++) {
                System.out.print(d[a][b] + " ");
            }
            System.out.println();
        }
    }

    /**
     * Beállítjuk a d távolság-mátrixot a Floyd-Warshall algoritmus szerint.
     */
    private void calcDistances() {
        for (int k = 0; k < g; k++) {
            for (int i = 0; i < g; i++) {
                for (int j = 0; j < g; j++) {
                    d[i][j] = min( d[i][j], d[i][k] + d[k][j] );
                }
            }
        }
    }

    /**
     * Van-e olyan páratlan kör, ami tartalmazza a g0-át?
     * @param g kérdéses pont, amihez a kört keressük.
     * @return ha van ilyen
     */
    private boolean hasOddCircle( int g0 )
    {
        for( int g1 = 0; g1 < g; g1++ )
        {
            for( int g2 = 0; g2 < g; g2++ )
            {
                if( d[g0][g1] == d[g0][g2] ) {
                    // találtunk két olyan pontot, ami a g0-tól egyenlő távolságra van.
                    // nézzük meg, hogy ők milyen távol vannak egymástól.
                    if( d[g1][g2] == 1 ) {
                        return true; // találtunk egy páratlan kört.
                    }
                }
            }
        }
        return false;
    }

    public int maxHeightIfHung()
    {
        calcDistances();

        int max, min;
        min = Integer.MAX_VALUE;
        for( int g0 = 0; g0 < g; g0++ )
        {
            if( hasOddCircle( g0 ) ) return -1;
            max = 0;
            for( int g1 = 0; g1 < g; g1++ ) {
                if( d[g0][g1] > max ) {
                    max = d[g0][g1];
                }
            }
            if( max < min ) {
                min = max;
                //minAt = g0; // ha kéne.
            }
        }
        return min;
    }

    private int min(int a, int b) {
        if( a < b ) return a; else return b;
    }
}
(Vissza)