Tugas Pertemuan 7 - Aplikasi Dessert Clicker

 Apa itu graf? Graf merupakan struktur matematik yang merepresentasikan relasi antar entitas di dunia nyata. Sebagai contoh, graf pada Gambar 12.1 merepresentasikan jalan dan jaraknya di antara kota-kota di Sumatera Utara (hanya ilustrasi saja, tidak sesuai dengan peta sebenarnya).

Graf memuat sehimpunan verteks (atau simpul atau titik) dan sehimpunan tepi yang menghubungkan antar verteks. Untuk lebih memudahkan, suatu graf didefinisikan sebagai G = (V, E), dimana V merepresentasikan sehimpunan verteks dan E merepresentasikan sehimpunan tepi. Sebagai contoh, V dan E untuk graf pada Gambar 12.1 adalah sebagai berikut:

V = {"Balige", "Parapat", "Raya",

"Tebing", "Siantar", "Perdagangan", "Sipirok", "Tanjung",

"Binjai", "Medan", "Asahan", "Kisaran"};

E = {{"Balige", "Parapat"},{"Balige", "Tebing"},

{"Balige", "Siantar"}, {"Parapat", "Siantar"},

...};

Suatu graf bisa terarah atau tak-terarah. Di dalam suatu graf terarah, setiap tepi memiliki arah, yang mengindikasikan bahwa Anda bergerak dari satu verteks ke verteks lain melalui tepi. Anda bisa memodelkan relasi orangtua/anak menggunakan suatu graf terarah, dimana tepi dari verteks A ke B mengindikasikan bahwa A adalah orangtua dari B.

Gambar 12.2a menampilkan suatu graf terarah. Di dalam suatu graf tak-terarah, Anda dapat bergerak dalam dua arah antar verteks. Graf pada Gambar 12.1 merupakan graf tak-terarah.

Berikut Implementasi Graph:

	/**
	* Write a description of class graph here.
	*
	* @author Afira Rolobessy
	* @version 15 june 2021
	*/
	class Graph
	{
	private final int numNodes;
	private final boolean direct;
	private final boolean weight;
	private final float[][] matrix;
	private final boolean[][] isMatrix;
	Graph(int num, boolean direct, boolean weight)
	{
	this.direct = direct;
	this.weight = weight;
	this.numNodes = num;
	matrix = new float[num][num];
	isMatrix = new boolean[num][num];
	}
	public void addEdge(int start, int end)
	{
	int addValue = 1;
	if (weight)
	addValue = 0;
	matrix[start][end] = addValue;
	isMatrix[start][end] = true;
	if (!direct)
	{
	matrix[end][start] = addValue;
	isMatrix[end][start] = true;
	}
	}
	public void addEdge(int start, int end, float the_weight)
	{
	float addValue = the_weight;
	if (!weight)
	addValue = 1;
	matrix[start][end] = addValue;
	isMatrix[start][end] = true;
	if (!direct)
	{
	matrix[end][start] = addValue;
	isMatrix[end][start] = true;
	}
	}
	public void printMatrix()
	{
	for (int i = 0; i < numNodes; i++)
	{
	for (int j = 0; j < numNodes; j++)
	{
	// We only want to print the values of those positions that have been marked as set
	if (isMatrix[i][j])
	System.out.format("%8s", matrix[i][j]);
	else
	System.out.format("%8s", "/ ");
	}
	System.out.println();
	}
	}
	public void printEdges()
	{
	for (int i = 0; i < numNodes; i++)
	{
	System.out.print("Node " + i + " is connected to: ");
	for (int j = 0; j < numNodes; j++)
	{
	if (isMatrix[i][j])
	System.out.print(j + " ");
	}
	System.out.println();
	}
	}
	public boolean hasEdge(int start, int end)
	{
	return isMatrix[start][end];
	}
	}
	class Main
	{
	public static void main(String[] args)
	{
	// Graph(numOfNodes, directed, weighted)
	Graph graph = new Graph(6, false, true);
	graph.addEdge(0, 1, 19);
	graph.addEdge(0, 2, 10);
	graph.addEdge(0, 3, 7);
	graph.addEdge(0, 4, 2);
	graph.addEdge(0, 5, 11);
	graph.addEdge(1, 2, 3);
	graph.addEdge(1, 3);// The default weight is 0 if weighted == true
	graph.addEdge(1, 4);
	graph.addEdge(2, 3);
	graph.addEdge(3, 4);
	graph.addEdge(4, 5);
	graph.printMatrix();
	System.out.println();
	System.out.println();
	graph.printEdges();
	System.out.println();
	System.out.println("Does an edge from 1 to 5 exist?");
	if (graph.hasEdge(0,1))
	System.out.println("Yes");
	else
	System.out.println("No");
	}
	}

view raw graph hosted with ❤ by GitHub

Berikut Output: