Informatika gyűjtemény

Egy szinttel feljebb Graph.java

2004050607080910

<<  10. óra - Szélességi és mélységi bejárás  >>

<<  Idegenvezetés  >>

NézetNyomtat

Graph.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.idegenvezetes;

import java.util.ArrayList;
import java.util.Hashtable;

/**
 *
 * @author balint
 */
public class Graph {

    private Hashtable<String, Integer> idByName;
    private Hashtable<Integer, String> nameById;
    private boolean[][] connections;
    private int disconnectedNode = -1;
    private int nodesCount;
    private ArrayList<Integer> tacticalPoints = new ArrayList<Integer>();

    public Graph(String[] nodes, String[] edges) {
        nodesCount = nodes.length;
        idByName = new Hashtable<String, Integer>(nodesCount);
        nameById = new Hashtable<Integer, String>(nodesCount);
        for (int i = 0; i < nodesCount; i++) {
            idByName.put(nodes[i], i);
            nameById.put(i, nodes[i]);
        }
        connections = new boolean[nodesCount][nodesCount];
        for (int i = 0; i < nodesCount; i++) {
            for (int j = 0; j < nodesCount; j++) {
                connections[i][j] = false;
            }
        }
        String[] tmp;
        int a, b;
        for (int i = 0; i < edges.length; i++) {
            tmp = edges[i].split(" ");
            a = idByName.get(tmp[0]);
            b = idByName.get(tmp[1]);
            connect(a, b);
        }

        disconnectOneByOne();
        for( int i : tacticalPoints ) {
            System.out.print( nameById.get(i) + " " );
        }
        System.out.println();
    }

    private void connect(int a, int b) {
        connections[a][b] = true;
        connections[b][a] = true;
    }

    private void disconnectOneByOne() {
        for (int i = 0; i < nodesCount; i++) {
            disconnectedNode = i;
            if (!isConnected()) {
                tacticalPoints.add(i);
            }
        }
    }

    private boolean isConnected() {
        // bejárjuk a gráfot, de figyelünk arra, hogy a disconnectedhez nem megyünk.
        ArrayList<Integer> queue = new ArrayList<Integer>();
        if (disconnectedNode == 0) {
            queue.add(1);
        } else {
            queue.add(0);
        }
        int node;
        boolean[] usedNodes = new boolean[nodesCount];
        for( int i=0; i<nodesCount; i++ ) {
            usedNodes[i] = false;
        }
        while( !queue.isEmpty() ) {
            node = queue.remove(0);
            // betesszük a szomszédjait.
            if( !usedNodes[node] && (disconnectedNode != node) ) {
                // berakjuk a szomszédjait
                for( int i=0; i<nodesCount; i++ ) {
                    if( connections[node][i] ) {
                        queue.add(i);
                    }
                }
            }
            usedNodes[node] = true;
        }
        for( int i=0; i<nodesCount; i++ ) {
            if( !usedNodes[i] ) return false;
        }
        return true;
    }
}
(Vissza)