algorytm.org

Implementacja w Java

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Generowanie grafu z cyklem Eulera - Implementacja w Java
Ocena użytkownikóww: *****  / 5
SłabyŚwietny
Nadesłany przez Tomasz Lubiński, 31 lipca 2005 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

Euler.java:
import java.util.Random;

//Tomasz Lubiński (c)2007
//www.algorytm.org
//Generowanie gafu z cyklem Eulera

public class Euler {
	
	public static short[][] genGraphWithEuler(int n, int b) {
		short result[][] = new short[n][n];
		Random rand = new Random();
		
		//clear graph
		for (int i=0; i<n; i++)
			for (int j=0; j<n; j++)
				result[i][j] = 0;
		
		//generate graph with given n and b
		for (int i=1; i<n; i++)
			 for (int j=0; j<i; j++)
			  if (rand.nextInt(100)<b) {
				  result[i][j] = 1;
				  result[j][i] = 1;
			  }
		
		//modify to have EULER
		for (int i=0; i<n-1; i++) {
		    //calculate degree
		    int deg = 0;
		    for (int j=0; j<n; j++)
		        if (result[i][j]>0) 
		            deg++;
		    //check if degree is even
		    if (deg%2 != 0) {
		       int x = rand.nextInt(n-i-1)+i+1;
		       if (result[i][x]>0) {
		    	   result[i][x] = 0;
		    	   result[x][i] = 0;
		       } else {
		    	   result[i][x] = 1;
		    	   result[x][i] = 1;
		       }
		    }
		}
		
		return result;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n;
		int b;
		short graph[][];
		
		System.out.println("Podaj liczbe wierzcholkow grafu");
		n = Console.readInt("");
		
		System.out.println("Podaj stopień nasycenia grafu (w %)");
		b = Console.readInt("");
		
		graph = genGraphWithEuler(n, b);
		
		for (int i=0; i<n; i++){
			System.out.println();
			for (int j=0; j<n; j++) {
				System.out.print(graph[i][j] + " ");
			}
		}
		System.out.println();
	}

}
Dodaj komentarz