Implementasi Graph
Apa itu Graph?
Graph adalah salah satu bentuk struktur data yang memiliki sifat seperti tree, yaitu memiliki sifat non-linear. Mengapa graph disebut struktur data non-linear? Hal ini disebabkan karena bentuk penyimpanan data oleh graph yang setiap datanya bisa memiliki hubungan dengan data lain.
Graph memiliki konsep seperti tree, dimana setiap datanya dihubungkan dengan aturan tertentu, tetapi graph memiliki fungsi yang lebih banyak jika dibandingkan dengan graph. Bahkan graph memiliki fungsi lebih baik dibanding tree, dimana graph dapat menghubungkan hubungan data yang sangat banyak dan kompleks.
Bagian-Bagian Graph
Graph terdiri dari edge dan vertices, dimana graph merupakan penghubung anta vertices, sedangkan vertices merupakan sebutan tiap node yang menyimpan data tertentu pada struktur data graph. Pada graph, edge memiliki 2 sifat, yaitu directed dan undirected. Directed adalah posisi dimana edge dengan arah 0 menuju 4 (0 =>4) tidak sama dengan 4 menuju 0 (4 => 0), sedangkan undirected memiliki sifat sebaliknya. Hal inilah yang membuat graph memiliki 2 sifat, yaitu directed dan udirected graph.
Selain itu, setiap edge juga dapat diberi komponen weight, dimana weight menggambarkan tingkat kesulitan menjalani edge. Hal ini dapat dilihat dalam pemakaian graph di software maps, seperti Google Maps, Waze, dan sebagainya. Misalnya dari tempat 0 menuju tempat 1, jalanannya macet, tetapi tempat 1 menuju tempat 2 jalananya lancar, maka weight pada edge 0 menuju 1, akan lebih besar daripada edge 1 menuju 2.
Implementasi Graph
Untuk pengimplementasian graph pada Java, dapat dilihat source code di bawah ini.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Graph class with main method | |
| * | |
| * @author Anggito Anju | |
| * @version ver 1.0 - 11 June 21 | |
| */ | |
| public class Graph | |
| { | |
| private int vertexMaxAmout; | |
| private int edgeMaxAmount; | |
| private int vertexAmout = 0; | |
| private int edgeAmount = 0; | |
| private Vertex vertices[]; | |
| private Edge edges[]; | |
| // Graph Constructure | |
| public Graph(int vertexMaxAmout, int edgeMaxAmount) { | |
| this.vertexMaxAmout = vertexMaxAmout; | |
| this.edgeMaxAmount = edgeMaxAmount; | |
| this.vertices = new Vertex[vertexMaxAmout+1]; | |
| this.edges = new Edge[edgeMaxAmount+1]; | |
| } | |
| // Check Vertex already existed | |
| public boolean isVertexExisted(Vertex newVertex) { | |
| for(int i = 0; i<vertexAmout; i++) { | |
| if(vertices[i].getData() == newVertex.getData()) { | |
| return true; | |
| } | |
| } | |
| return false; | |
| } | |
| // Check Edges already existed | |
| public boolean isEdgeExisted(Edge newEdge) { | |
| for(int i = 0; i<edgeAmount; i++) { | |
| if(edges[i].getLabel() == newEdge.getLabel()) { | |
| return true; | |
| } | |
| } | |
| return false; | |
| } | |
| // Add new Vertex | |
| public void addVertex(Vertex newVertex) { | |
| if(isVertexExisted(newVertex)) { | |
| System.out.println("Vertex was already existed !"); | |
| return; | |
| } | |
| vertices[vertexAmout] = newVertex; | |
| vertexAmout++; | |
| } | |
| // Add new Edge | |
| public void addEdge(Vertex from, Vertex to, double weight) { | |
| if(!isVertexExisted(from)) { | |
| System.out.println("Vertex from not existed !"); | |
| return; | |
| } | |
| if(!isVertexExisted(to)) { | |
| System.out.println("Vertex to not existed !"); | |
| return; | |
| } | |
| edges[edgeAmount] = new Edge(from, to, from.getData() + " to " + to.getData(), weight); | |
| edgeAmount++; | |
| } | |
| // Check if 2 vertices are connected | |
| public static void isConnected(Graph g, Vertex from, Vertex to) { | |
| int i; | |
| for(i = 0; i<g.edgeAmount; i++) { | |
| if(g.edges[i].getFrom().getData() == from.getData()) { | |
| if(g.edges[i].getTo().getData() == to.getData()) { | |
| break; | |
| } | |
| } | |
| } | |
| if(i != g.edgeAmount) { | |
| System.out.println("Vertex Connected"); | |
| } | |
| else { | |
| System.out.println("Vertex Not Connected"); | |
| } | |
| } | |
| // Main method | |
| public static void main(String[] args) { | |
| // Initializing graph | |
| Graph myGraph = new Graph(5, 13); | |
| // Initializing vertices | |
| Vertex a = new Vertex(1); | |
| Vertex b = new Vertex(2); | |
| Vertex c = new Vertex(3); | |
| Vertex d = new Vertex(4); | |
| Vertex e = new Vertex(5); | |
| // Add vertices | |
| myGraph.addVertex(a); | |
| myGraph.addVertex(b); | |
| myGraph.addVertex(c); | |
| myGraph.addVertex(d); | |
| myGraph.addVertex(e); | |
| // Add Edges | |
| myGraph.addEdge(a, b, 1); | |
| myGraph.addEdge(a, e, 1); | |
| myGraph.addEdge(b, a, 1); | |
| myGraph.addEdge(b, c, 1); | |
| myGraph.addEdge(b, d, 1); | |
| myGraph.addEdge(b, e, 1); | |
| myGraph.addEdge(c, b, 1); | |
| myGraph.addEdge(c, d, 1); | |
| myGraph.addEdge(d, b, 1); | |
| myGraph.addEdge(d, c, 1); | |
| myGraph.addEdge(d, e, 1); | |
| myGraph.addEdge(e, a, 1); | |
| myGraph.addEdge(e, d, 1); | |
| System.out.println("Checking connections between 2 vertices"); | |
| isConnected(myGraph, a, b); | |
| isConnected(myGraph, c, d); | |
| isConnected(myGraph, c, e); | |
| } | |
| } | |
| /** | |
| * Class for each edge | |
| * | |
| * @author Anggito Anju | |
| * @version ver 1.0 - 11 June 21 | |
| */ | |
| public class Edge | |
| { | |
| String label; | |
| private Vertex from, to; | |
| private double weight; | |
| // Object Constructure | |
| public Edge(Vertex from, Vertex to, String label, double weight) { | |
| this.from = from; | |
| this.to = to; | |
| this.label = label; | |
| this.weight = weight; | |
| } | |
| // Get weight | |
| public double getWeight() { | |
| return weight; | |
| } | |
| // Set weight | |
| public void setWeight(double weight) { | |
| this.weight = weight; | |
| } | |
| // Get vertex from | |
| public Vertex getFrom() { | |
| return from; | |
| } | |
| // Set vertex from | |
| public void setFrom(Vertex from) { | |
| this.from = from; | |
| } | |
| // Get vertex to | |
| public Vertex getTo() { | |
| return to; | |
| } | |
| // Set vertex to | |
| public void setTo(Vertex to) { | |
| this.to = to; | |
| } | |
| // Get Label | |
| public String getLabel() { | |
| return label; | |
| } | |
| // Set Label | |
| public void setLabel(String label) { | |
| this.label = label; | |
| } | |
| } | |
| /** | |
| * Class for each Vertex | |
| * | |
| * @author Anggito Anju | |
| * @version ver 1.0 - 11 June 21 | |
| */ | |
| public class Vertex | |
| { | |
| private int data; | |
| private boolean isVisited; | |
| // Object constructure | |
| public Vertex(int data) { | |
| this.data = data; | |
| this.isVisited = false; | |
| } | |
| // Get data | |
| public int getData() { | |
| return data; | |
| } | |
| // Set data | |
| public void setData(int data) { | |
| this.data = data; | |
| } | |
| // Get visited info | |
| public boolean isVisited() { | |
| return isVisited; | |
| } | |
| // Set visited info | |
| public void setIsVisited(boolean isVisited) { | |
| this.isVisited = isVisited; | |
| } | |
| } |
Pada pengimplementasiannya digunakan 3 class, yaitu:
- Vertex, untuk semua komponen dan fungsi pada setiap vertex
- Edge, untuk semua komponen dan fungsi pada setiap edge
- Graph, untuk fungsi utama pada Graph
Dan berikut merupakan hasil output yang didapatkan
Komentar
Posting Komentar