Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2015-2016‎ > ‎

16. alkalom

Nemes Tihamér verseny 2. forduló

OKTV 2. forduló

  1. Épület
  2. Ádám-Éva (OKTV)
  3. Háromszög
  4. Építkezés
  5. Ütemezés

Egy kicsit előreugrottunk az egyik feladat kapcsán, és megnéztük a szélességi bejárást Java-ban.

Graf.java

import java.util.LinkedList;
class Graf {
    public int V;
    public int E;
    public LinkedList<Integer>[] next;
    
    public Graf(int myV, int myE) {
            V = myV;
            E = myE;
            next = new LinkedList[V+1];
            for(int i = 1; i <= V; i++) {
                next[i] = new LinkedList<Integer>();
            }
    }
    
    public void addEdge(int u, int v) {
        next[u].addLast(v);
        next[v].addLast(u);
    }
    
    public void print() {
        for(int  i = 1; i <= V; i++) {
            System.out.print(i+" : ");
            for(int j : next[i]) {
                System.out.print(j+ " ");
            }
            System.out.println();
        }
    }
}

SzelessegiBejaras.java

import java.util.Scanner;
import java.util.LinkedList;

class SzelessegiBejaras {
    
    public static void bejar(Graf G, int start, int[] d) {
        boolean[] volt = new boolean[d.length];
        volt[start] = true;
        d[start] = 0;
        LinkedList<Integer> Sor = new LinkedList<Integer>();
        Sor.addLast(start);
        while(Sor.size() > 0) {
            int u = Sor.removeFirst();
            for(int v : G.next[u]) {
                if(!volt[v]) {
                    volt[v] = true;
                    d[v] = d[u]+1;
                    Sor.addLast(v);
                }
            }
        }   
    }
        
    public static void main(String args[]) {
        Scanner be = new Scanner(System.in);
        int V, E;
        V = be.nextInt();
        E = be.nextInt();
        Graf G = new Graf(V,E);
        for(int i = 0; i < E; i++) {
            int x,y;
            x = be.nextInt();
            y = be.nextInt();
            G.addEdge(x,y);
        }
        
        //G.print();
        
        int[] d = new int[G.V+1]; 
        bejar(G, 1, d);
        for(int i = 1; i <= G.V; i++) System.out.println("d(1,"+i+")="+d[i]);   
    }
}