Graph

 





Grafik adalah struktur data yang menyimpan data yang terhubung. Dengan kata lain, graf G (atau g) didefinisikan sebagai himpunan simpul (V) dan sisi (E) yang menghubungkan simpul. Contoh grafik adalah jaringan media sosial, jaringan komputer, Google Maps, dll.


Setiap graph terdiri dari edge dan vertex (disebut juga node). Setiap simpul dan tepi memiliki relasi. Dimana vertex mewakili data dan edge mewakili hubungan di antara mereka. Vertex dilambangkan dengan lingkaran dengan label di atasnya. Tepi dilambangkan dengan garis yang menghubungkan node (simpul).


DATA HOSTED WITH ♥ BY PASTEBIN.COM - DOWNLOAD RAW - SEE ORIGINAL
  1. public class Graph {
  2.  
  3.      private int numOfNodes;
  4.      private boolean directed;
  5.      private boolean weighted;
  6.      private float[][] matrix;
  7.  
  8.      /*
  9.      This will allow us to safely add weighted graphs in our class since
  10.      we will be able to check whether an edge exists without relying
  11.      on specific special values (like 0)
  12.      */
  13.      private boolean[][] isSetMatrix;
  14.  
  15.      public Graph(int numOfNodes, boolean directed, boolean weighted) {
  16.  
  17.      this.directed = directed;
  18.      this.weighted = weighted;
  19.      this.numOfNodes = numOfNodes;
  20.  
  21.      // Simply initializes our adjacency matrix to the appropriate size
  22.      matrix = new float[numOfNodes][numOfNodes];
  23.      isSetMatrix = new boolean[numOfNodes][numOfNodes];
  24.      }
  25.  
  26.      public void addEdge(int source, int destination) {
  27.      int valueToAdd = 1;
  28.  
  29.      if (weighted) {
  30.        valueToAdd = 0;
  31.        }
  32.  
  33.      matrix[source][destination] = valueToAdd;
  34.      isSetMatrix[source][destination] = true;
  35.  
  36.      if (!directed) {
  37.        matrix[destination][source] = valueToAdd;
  38.        isSetMatrix[destination][source] = true;
  39.     }
  40. }
  41.  
  42.      public void addEdge(int source, int destination, float weight) {
  43.  
  44.      float valueToAdd = weight;
  45.  
  46.      if (!weighted) {
  47.      valueToAdd = 1;
  48.      }
  49.  
  50.      matrix[source][destination] = valueToAdd;
  51.      isSetMatrix[source][destination] = true;
  52.  
  53.      if (!directed) {
  54.        matrix[destination][source] = valueToAdd;
  55.        isSetMatrix[destination][source] = true;
  56.      }
  57. }
  58.  
  59.      public void printMatrix() {
  60.      for (int i = 0; i < numOfNodes; i++) {
  61.        for (int j = 0; j < numOfNodes; j++) {
  62.          // We only want to print the values of those positions that have been marked as set
  63.          if (isSetMatrix[i][j])
  64.            System.out.format("%8s", String.valueOf(matrix[i][j]));
  65.          else System.out.format("%8s", "/ ");
  66.        }
  67.      System.out.println();
  68.     }
  69. }
  70.  
  71.      public void printEdges() {
  72.      for (int i = 0; i < numOfNodes; i++) {
  73.        System.out.print("Node " + i + " is connected to: ");
  74.        for (int j = 0; j < numOfNodes; j++) {
  75.          if (isSetMatrix[i][j]) {
  76.            System.out.print(j + " ");
  77.          }
  78.       }
  79.      System.out.println();
  80.     }
  81. }
  82.  
  83.      public boolean hasEdge(int source, int destination) {
  84.        return isSetMatrix[source][destination];
  85.   }
  86.  
  87.      public Float getEdgeValue(int source, int destination) {
  88.        if (!weighted || !isSetMatrix[source][destination])
  89.          return null;
  90.        return matrix[source][destination];
  91.      }
  92. }
DATA HOSTED WITH ♥ BY PASTEBIN.COM - DOWNLOAD RAW - SEE ORIGINAL
  1. public class GraphShow {
  2.      public static void main(String[] args) {
  3.  
  4.      // Graph(numOfNodes, directed, weighted)
  5.      Graph graph = new Graph(5, false, true);
  6.  
  7.      graph.addEdge(0, 2, 19);
  8.      graph.addEdge(0, 3, -2);
  9.      graph.addEdge(1, 2, 3);
  10.      graph.addEdge(1, 3); // The default weight is 0 if weighted == true
  11.      graph.addEdge(1, 4);
  12.      graph.addEdge(2, 3);
  13.      graph.addEdge(3, 4);
  14.  
  15.      graph.printMatrix();
  16.  
  17.      System.out.println();
  18.      System.out.println();
  19.  
  20.      graph.printEdges();
  21.  
  22.      System.out.println();
  23.      System.out.println("Does an edge from 1 to 0 exist?");
  24.      if (graph.hasEdge(0,1)) {
  25.        System.out.println("Yes");
  26.     }
  27.      else System.out.println("No");
  28.    }
  29. }



DATA HOSTED WITH ♥ BY PASTEBIN.COM - DOWNLOAD RAW - SEE ORIGINAL
  1. public class Node{
  2.      int n;
  3.      String name;
  4.  
  5.      Node(int n, String name){
  6.        this.n = n;
  7.        this.name = name;
  8.     }
  9. }
DATA HOSTED WITH ♥ BY PASTEBIN.COM - DOWNLOAD RAW - SEE ORIGINAL
  1. import java.util.LinkedList;
  2. import java.util.HashMap;
  3.  
  4. public class Graph {
  5.  
  6. // Each node maps to a list of all his neighbors
  7. private HashMap<Node, LinkedList<Node>> adjacencyMap;
  8. private boolean directed;
  9.  
  10. public Graph(boolean directed) {
  11.      this.directed = directed;
  12.      adjacencyMap = new HashMap<>();
  13. }
  14.  
  15. public void addEdgeHelper(Node a, Node b) {
  16.      LinkedList<Node> tmp = adjacencyMap.get(a);
  17.  
  18.      if (tmp != null) {
  19.        tmp.remove(b);
  20.      }
  21.      else tmp = new LinkedList<>();
  22.      tmp.add(b);
  23.      adjacencyMap.put(a,tmp);
  24. }
  25.  
  26. public void addEdge(Node source, Node destination) {
  27.  
  28.      // We make sure that every used node shows up in our .keySet()
  29.      if (!adjacencyMap.keySet().contains(source))
  30.         adjacencyMap.put(source, null);
  31.  
  32.      if (!adjacencyMap.keySet().contains(destination))
  33.        adjacencyMap.put(destination, null);
  34.  
  35.      addEdgeHelper(source, destination);
  36.  
  37.      // If a graph is undirected, we want to add an edge from destination to source as well
  38.      if (!directed) {
  39.        addEdgeHelper(destination, source);
  40.     }
  41. }
  42.  
  43.  
  44. public void printEdges() {
  45.      for (Node node : adjacencyMap.keySet()) {
  46.        System.out.print("The " + node.name + " has an edge towards: ");
  47.        if (adjacencyMap.get(node) != null) {
  48.          for (Node neighbor : adjacencyMap.get(node)) {
  49.           System.out.print(neighbor.name + " ");
  50.          }
  51.          System.out.println();
  52.        }
  53.        else {
  54.          System.out.println("none");
  55.        }
  56.     }
  57. }
  58.  
  59. public boolean hasEdge(Node source, Node destination) {
  60.      return adjacencyMap.containsKey(source) && adjacencyMap.get(source) != null &&  adjacencyMap.get(source).contains(destination);
  61.    }
  62. }
DATA HOSTED WITH ♥ BY PASTEBIN.COM - DOWNLOAD RAW - SEE ORIGINAL
  1. public class GraphShow{

  3.      public static void main(String[] args) {
  4.        System.out.println("==+==+== Adjacency Lists Implementation ==+==+==\\n");
  5.        Graph graph = new Graph(true);
  6.        Node a = new Node(0, "A");
  7.        Node b = new Node(1, "B");
  8.        Node c = new Node(2, "C");
  9.        Node d = new Node(3, "D");
  10.        Node e = new Node(4, "E");
  11.  
  12.        graph.addEdge(a,b);
  13.        graph.addEdge(b,c);
  14.        graph.addEdge(b,d);
  15.        graph.addEdge(c,e);
  16.        graph.addEdge(b,a);
  17.  
  18.        graph.printEdges();
  19.  
  20.        System.out.println(graph.hasEdge(a,b));
  21.        System.out.println(graph.hasEdge(d,a));
  22.     }
  23. }




Komentar

Posting Komentar

Postingan populer dari blog ini

KUIS Akhir EPL

Kuis Akhir EPL  Nama : Sidrotul Munawaroh Nrp : 5025201047 1. Berikut alasan mengapa perangkat lunak harus mengalami proses evolusi: - Perubahan Kebutuhan Pengguna: kebutuhan dan ekspektasi pengguna terus berubah seiringnya waktu, maka dari itu perangkat lunak perlu berkembang untuk memenuhi tuntutan baru dan meningkatkan fungsionalitas - Perbaikan dan Pemeliharaan: Proses evolusi mencakup perbaikan bug, peningkatan performa, dan pemeliharaan perangkat lunak - Teknologi Baru: Kemajuan dalam teknologi memungkinkan pengembang perangkat lunak untuk memanfaatkan alat dan metode baru yang dapat meningkatkan kualitas dan efisiensi perangkat lunak. - Perubahan Lingkungan Operasional: Perubahan dalam lingkungan operasional, seperti perubahan sistem operasi, infrastruktur hardware, atau integrasi dengan platform lain, dapat memerlukan adaptasi dan evolusi perangkat lunak agar tetap kompatibel dan berjalan dengan baik. - Peningkatan Keamanan: Ancaman keamanan terus berkembang, dan perangkat ...
Baca selengkapnya

Tower of Hanoi - Java

Gambar
            Tower of Hanoi   adalah sebuah permainan matematis atau teka-teki. Permainan ini terdiri dari tiga tiang dan sejumlah cakram dengan ukuran berbeda-beda yang bisa dimasukkan ke tiang mana saja. Permainan dimulai dengan cakram-cakram yang tertumpuk rapi berurutan berdasarkan ukurannya dalam salah satu tiang, cakram terkecil diletakkan teratas, sehingga membentuk kerucut. Tujuan dari teka-teki ini adalah untuk memindahkan seluruh tumpukan ke tiang yang lain, mengikuti aturan berikut: Hanya satu cakram yang boleh dipindahkan dalam satu waktu. Setiap perpindahan berupa pengambilan cakram teratas dari satu tiang dan memasukkannya ke tiang lain, di atas cakram lain yang mungkin sudah ada di tiang tersebut. Tidak boleh meletakkan cakram di atas cakram lain yang lebih kecil. DATA HOSTED WITH ♥ BY  PASTEBIN.COM  -  DOWNLOAD RAW  -  SEE ORIGINAL import java.util.Scanner;   public class App {      stati...
Baca selengkapnya

Binary Search Tree

Gambar
       Binary tree adalah struktur data non linier bentuk khusus dari pohon umum (general tree) yang diilhami dari pohon yang kita lihat sehari-hari. Namun, karena ini merupakan pohon imajiner maka bentuknya bisa dibolak-balik sesuai yang kita inginkan.      Pohon umum di gambar 1 memiliki 7 simpul (7 nodes), yaitu A, B, C, D, E, F, dan G. Setiap simpul bisa memiliki hubungan dengan 0, 1, 2, 3, atau berapapun simpul lain. Yang dikatakan hubungan adalah garis yang menghubungkan simpul tersebut dengan simpul-simpul di bawahnya. Karena ketidakpastian banyaknya simpul yang dapat berhubungan dengan simpul lain, maka akan menimbulkan kesulitan jika akan dilakukan komputerisasinya. Kalau masing-masing dipatok (default) dengan penyediaan sebanyak 5 hubungan dari masing-masing simpul, maka, jika akhirnya hanya digunakan 1 sampai 3 saja, berakibat terjadinya pemborosan penggunaan memori. Sebaliknya, jika hanya disediakan 3 hubungan dari setiap simpul tetapi pada...
Baca selengkapnya