{"id":4253,"date":"2026-10-27T11:18:46","date_gmt":"2026-10-27T04:18:46","guid":{"rendered":"https:\/\/focusnic.com\/blog\/?p=4253"},"modified":"2026-10-27T11:18:48","modified_gmt":"2026-10-27T04:18:48","slug":"graph-pada-struktur-data","status":"publish","type":"post","link":"https:\/\/focusnic.com\/blog\/graph-pada-struktur-data\/","title":{"rendered":"Graph pada Struktur Data"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Dalam dunia pemrograman dan ilmu komputer, <strong>graph<\/strong> menjadi salah satu struktur data yang sangat krusial. Berbeda dengan array atau linked list yang bersifat linier, graph mampu merepresentasikan hubungan kompleks antar entitas. Struktur ini sering digunakan untuk memodelkan jaringan sosial, rute transportasi, dependensi dalam kompiler, hingga rekomendasi produk. Dengan memahami konsep dan implementasi graph, Anda dapat menyelesaikan permasalahan yang melibatkan relasi banyak-ke-banyak secara efisien.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Graph memanfaatkan <strong>vertex<\/strong> (simpul) dan <strong>edge<\/strong> (tepi) untuk menggambarkan objek dan hubungan antar objek. Keunggulan graph terletak pada fleksibilitasnya dalam mengelola struktur data non-linier dan kemampuannya dalam memodelkan skenario dunia nyata dengan kompleksitas tinggi. Oleh karena itu, pemahaman mendalam tentang graph menjadi fondasi penting dalam pengembangan algoritma canggih dan aplikasi skala besar.<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_89 counter-hierarchy ez-toc-counter ez-toc-light-blue ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Table of Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/focusnic.com\/blog\/graph-pada-struktur-data\/#Definisi_dan_Representasi_Graph_untuk_Pemula\" >Definisi dan Representasi Graph untuk Pemula<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/focusnic.com\/blog\/graph-pada-struktur-data\/#Terminologi_Penting_dalam_Graph\" >Terminologi Penting dalam Graph<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/focusnic.com\/blog\/graph-pada-struktur-data\/#Representasi_Graph_Adjacency_Matrix_dan_List\" >Representasi Graph: Adjacency Matrix dan List<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/focusnic.com\/blog\/graph-pada-struktur-data\/#Algoritma_dan_Operasi_Utama_dalam_Graph\" >Algoritma dan Operasi Utama dalam Graph<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/focusnic.com\/blog\/graph-pada-struktur-data\/#Traversal_Graph_BFS_dan_DFS\" >Traversal Graph: BFS dan DFS<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/focusnic.com\/blog\/graph-pada-struktur-data\/#Pencarian_Jalur_Terpendek_Dijkstra_dan_A\" >Pencarian Jalur Terpendek: Dijkstra dan A*<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/focusnic.com\/blog\/graph-pada-struktur-data\/#Algoritma_Flow_dan_Matching\" >Algoritma Flow dan Matching<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/focusnic.com\/blog\/graph-pada-struktur-data\/#Implementasi_dan_Aplikasi_Graph_di_Dunia_Nyata\" >Implementasi dan Aplikasi Graph di Dunia Nyata<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/focusnic.com\/blog\/graph-pada-struktur-data\/#Contoh_Implementasi_Adjacency_List_di_Java\" >Contoh Implementasi Adjacency List di Java<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/focusnic.com\/blog\/graph-pada-struktur-data\/#Contoh_Implementasi_Adjacency_Matrix_di_Python\" >Contoh Implementasi Adjacency Matrix di Python<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/focusnic.com\/blog\/graph-pada-struktur-data\/#Kesimpulan\" >Kesimpulan<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Definisi_dan_Representasi_Graph_untuk_Pemula\"><\/span>Definisi dan Representasi Graph untuk Pemula<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Secara sederhana, <strong>graph<\/strong> adalah kumpulan objek yang disebut <strong>vertex<\/strong> (simpul atau node) dan hubungan antar objek tersebut yang disebut <strong>edge<\/strong> (tepi atau busur). Graph dapat bersifat terarah (directed) maupun tidak terarah (undirected). Jika graph terarah, edge memiliki arah dari satu vertex ke vertex lain; jika tidak terarah, hubungan bersifat dua arah.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Terminologi_Penting_dalam_Graph\"><\/span>Terminologi Penting dalam Graph<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Vertex (Node)<\/strong>: Titik yang mewakili entitas dalam graph.<\/li>\n\n\n\n<li><strong>Edge (Tepi)<\/strong>: Garis atau busur yang menghubungkan dua vertex.<\/li>\n\n\n\n<li><strong>Weighted Graph<\/strong>: Graph dimana setiap edge memiliki bobot yang merepresentasikan biaya atau jarak.<\/li>\n\n\n\n<li><strong>Degree<\/strong>: Jumlah edge yang terhubung pada suatu vertex (in-degree dan out-degree untuk graph terarah).<\/li>\n\n\n\n<li><strong>Path<\/strong>: Urutan vertex yang terhubung oleh edge.<\/li>\n\n\n\n<li><strong>Cycle<\/strong>: Path yang dimulai dan berakhir pada vertex yang sama.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Representasi_Graph_Adjacency_Matrix_dan_List\"><\/span>Representasi Graph: Adjacency Matrix dan List<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Ada dua cara populer untuk merepresentasikan graph dalam memori:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Adjacency Matrix<\/strong>: Matriks dua dimensi berukuran N\u00d7N, dimana N adalah jumlah vertex. Nilai pada cell [i][j] menunjukkan ada atau tidaknya edge antara vertex i dan j, atau nilai bobotnya. Kelebihan: akses cepat O(1). Kekurangan: memakan banyak memori untuk graph jarang.<\/li>\n\n\n\n<li><strong>Adjacency List<\/strong>: Daftar untuk setiap vertex yang berisi daftar tetangga terhubung. Lebih efisien untuk graph jarang dengan kompleksitas memori O(V+E). Traversal lebih hemat dibanding matrix ketika E jauh lebih kecil dari V\u00b2.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Algoritma_dan_Operasi_Utama_dalam_Graph\"><\/span>Algoritma dan Operasi Utama dalam Graph<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Traversal_Graph_BFS_dan_DFS\"><\/span>Traversal Graph: BFS dan DFS<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Breadth-First Search (BFS)<\/strong> menjelajahi graph secara melebar, mengunjungi semua vertex pada satu tingkat sebelum melanjutkan ke tingkat berikutnya. Implementasi BFS biasanya menggunakan <strong>queue<\/strong>, dimulai dari sumber (source), menandai vertex yang sudah dikunjungi, lalu menambahkan tetangga ke antrian. BFS sangat berguna untuk mencari jalur terpendek pada graph tanpa bobot, deteksi komponen terhubung, dan analisis level. Kompleksitas waktu mencapai O(V+E) dan kompleksitas ruang O(V), sehingga cocok untuk graph besar dengan struktur sparsity.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Depth-First Search (DFS)<\/strong> menjelajahi graph secara mendalam, mengikuti satu jalur hingga tidak ada lintasan baru sebelum melakukan backtracking. DFS dapat diimplementasikan menggunakan <strong>stack<\/strong> atau rekursi dan mampu mendeteksi siklus, melakukan topological sort, serta menemukan strongly connected components (SCC). Kompleksitas waktu DFS juga O(V+E), namun penggunaan rekursi berpotensi menyebabkan stack overflow pada graph yang sangat dalam.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Pencarian_Jalur_Terpendek_Dijkstra_dan_A\"><\/span>Pencarian Jalur Terpendek: Dijkstra dan A*<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Dijkstra<\/strong> adalah algoritma terkenal untuk mencari jalur terpendek pada graph berbobot non-negatif. Algoritma ini memanfaatkan struktur data <strong>priority queue<\/strong> (heap) untuk memilih vertex dengan jarak terpendek sementara. Setiap iterasi, jarak ke tetangga diperbarui jika ditemukan jalur lebih pendek. Kompleksitas waktu standar adalah O(E + V log V), cocok untuk jaringan jalan raya atau graf transportasi.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>A*<\/strong> memperluas konsep Dijkstra dengan menambahkan fungsi heuristik yang memperkirakan jarak tersisa ke tujuan, sehingga fokus pencarian berada pada jalur yang paling menjanjikan. A* banyak digunakan pada pencarian rute peta, game AI, dan robotika. Keakuratan dan performa A* sangat bergantung pada pemilihan heuristik, yang harus admissible untuk memastikan jalur optimal.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Algoritma_Flow_dan_Matching\"><\/span>Algoritma Flow dan Matching<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Beberapa algoritma lanjutan penting untuk pemecahan masalah network flow dan matching:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Ford-Fulkerson<\/strong>: Metode dasar untuk menghitung maksimum flow dengan iterasi pencarian augmenting path. Sering dioptimasi menggunakan Edmonds-Karp dengan BFS sehingga kompleksitas menjadi O(V E^2).<\/li>\n\n\n\n<li><strong>Edmonds-Karp<\/strong>: Optimisasi Ford-Fulkerson yang menggunakan BFS untuk menemukan jalur peningkatan, memberikan batas tepi O(V E^2).<\/li>\n\n\n\n<li><strong>Dinic<\/strong>: Algoritma maksimum flow dengan level graph dan blocking flow untuk mempercepat perhitungan hingga O(E sqrt(V)).<\/li>\n\n\n\n<li><strong>Hopcroft\u2013Karp<\/strong>: Spesifik untuk matching bipartit, kompleksitas O(sqrt(V) E), dipakai dalam penjadwalan dan permasalahan alokasi.<\/li>\n\n\n\n<li><strong>Kruskal<\/strong> dan <strong>Prim<\/strong>: Algoritma untuk minimum spanning tree, berguna dalam perancangan jaringan dan clustering.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Implementasi_dan_Aplikasi_Graph_di_Dunia_Nyata\"><\/span>Implementasi dan Aplikasi Graph di Dunia Nyata<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Contoh_Implementasi_Adjacency_List_di_Java\"><\/span>Contoh Implementasi Adjacency List di Java<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Berikut ilustrasi singkat implementasi <strong>adjacency list<\/strong> pada Java:<\/p>\n\n\n\n<div class=\"wp-block-urvanov-syntax-highlighter-code-block\"><pre class=\"lang:java decode:true \" >class Graph {\n    private int V;\n    private List&gt; adj;\n\n    public Graph(int V) {\n        this.V = V;\n        adj = new ArrayList&lt;&gt;();\n        for (int i = 0; i &lt; V; i++) adj.add(new ArrayList&lt;&gt;());\n    }\n\n    public void addEdge(int src, int dest) {\n        adj.get(src).add(dest);\n        adj.get(dest).add(src); \/\/ untuk undirected graph\n    }\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Contoh_Implementasi_Adjacency_Matrix_di_Python\"><\/span>Contoh Implementasi Adjacency Matrix di Python<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Contoh implementasi <strong>adjacency matrix<\/strong> dengan Python:<\/p>\n\n\n\n<div class=\"wp-block-urvanov-syntax-highlighter-code-block\"><pre class=\"lang:python decode:true \" >class Graph:\n    def __init__(self, vertices):\n        self.V = vertices\n        self.adj_matrix = [[0] * vertices for _ in range(vertices)]\n\n    def add_edge(self, u, v, weight=1):\n        self.adj_matrix[u][v] = weight\n        self.adj_matrix[v][u] = weight  # graph tak berarah<\/pre><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Kesimpulan\"><\/span>Kesimpulan<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Penerapan graph di dunia nyata sangat luas dan terus berkembang. Di bidang jejaring sosial, graph memodelkan hubungan pertemanan, interaksi, dan deteksi komunitas menggunakan algoritma clustering. Dalam <strong>sistem rekomendasi<\/strong>, graph knowledge base menghubungkan item dan preferensi pengguna untuk meningkatkan relevansi rekomendasi. Sementara pada <strong>SEO<\/strong> dan web crawling, graph halaman web (web graph) memetakan hyperlink antar halaman dan menentukan peringkat dengan algoritma PageRank. Memvalidasi struktur situs melalui graph membantu mengenali broken link, circular redirect, dan optimasi internal linking.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Integrasi graph database seperti Neo4j atau Amazon Neptune juga semakin populer untuk skenario real-time query relasional yang kompleks. Struktur graph memaksimalkan performa query untuk relasi multi-hop dan memudahkan visualisasi data sebagai jaringan yang intuitif.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Dengan memahami <strong>graph<\/strong> dan algoritmanya, Anda dapat mengoptimalkan penyelesaian masalah struktural, meningkatkan performa aplikasi, serta merancang solusi yang skalabel. Pelajari setiap algoritma dan pola representasi dengan cermat untuk menguasai struktur data non-linier ini.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Dalam dunia pemrograman dan ilmu komputer, graph menjadi salah satu struktur data yang sangat krusial. Berbeda dengan array atau linked list yang bersifat linier, graph mampu merepresentasikan hubungan kompleks antar entitas. Struktur ini sering digunakan untuk memodelkan jaringan sosial, rute transportasi, dependensi dalam kompiler, hingga rekomendasi produk. Dengan memahami konsep dan implementasi graph, Anda dapat [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":4320,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[114],"class_list":["post-4253","post","type-post","status-publish","format-standard","has-post-thumbnail","category-informasi","tag-programming"],"_links":{"self":[{"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/posts\/4253","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/comments?post=4253"}],"version-history":[{"count":3,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/posts\/4253\/revisions"}],"predecessor-version":[{"id":4323,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/posts\/4253\/revisions\/4323"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/media\/4320"}],"wp:attachment":[{"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/media?parent=4253"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/categories?post=4253"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/tags?post=4253"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}