PAPER STRUKTUR DATA DAN ALGORITMA

GRAPH ALGORITHM

OLEH : AHMAD HUSEN ARISSA APRILIA N DHANI FATIMA R INDAH PUSPITASARI MIRANDA NUR QOLBI A PATRICIA VENI SANZA YUNITA PRIMASARI

M0511002 M0511010 M0511018 M0511026 M0511034 M0511043 M0511051

JURUSAN INFORMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA 2012

PENDAHULUAN Latar Belakang Graph merupakan struktur data yang paling umum. Jika struktur linear memungkinkan pendefinisian keterhubungan sikuensial antara entitas data, struktur data tree memungkinkan pendefinisian keterhubungan hirarkis, maka struktur graph memungkinkan pendefinisian keterhubungan tak terbatas antara entitas data. Banyak entitas-entitas data dalam masalah-masalah nyata secara alamiah memiliki keterhubungan langsung (adjacency) secara tak terbatas demikian. Contoh: informasi topologi dan jarak antar kota-kota di pulau Jawa. Dalam masalah ini kota x bisa berhubungan langsung dengan hanya satu atau lima kota lainnya. Untuk memeriksa keterhubungan dan jarak tidak langsung antara dua kota dapat diperoleh berdasarkan data keterhubungan-keterhubungan langsung dari kota-kota lainnya yang memperantarainya. Representasi data dengan struktur data linear ataupun hirarkis pada masalah ini masih bisa digunakan namun akan membutuhkan pencarian-pencarian yang kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straightforward) dilakukan pada strukturnya sendiri. Tujuan Mengenal dan mengetahui seluk beluk graf algoritma Mengetahui masalah-masalah yang ada pada graf algoritma Menunjukkan beberapa masalah kehidupan nyata, yang dapat dikonversi menjadi grafik. Membuat algoritma untuk memecahkan beberapa masalah grafik umum. Menunjukkan bagaimana memilih pilihan yang tepat dari struktur data secara yang drastis dapat mengurangi waktu berjalan algoritma ini. Melihat teknik penting, yang dikenal sebagai depth-first, dan menunjukkan bagaimana hal itu dapat digunakan untuk memecahkan masalah yang tampaknya trivial beberapa waktu linier. METODOLOGI 1. Menerjemahkan Data Structures And Algorithm Analysis by Mark Allen Weis ke bahasa Indonesia 2. Mempelajari buku Data Structures And Algorithm Analysis by Mark Allen Weiss 3. Merangkum dari buku Data Structures And Algorithm Analysis by Mark Allen Weis

HASIL DAN PEMBAHASAN 9.1 Definition Teori graf adalah cabang kajian yang mempelajari sifat-sifat graf. Secara informal, suatu graf adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan busur). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan gelang (loop). Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan pada facebook bisa direpresentasikan dengan graf, yakni simpul-simpulnya adalah para pengguna facebook dan ada sisi antar pengguna jika dan hanya jika mereka berteman. Perkembangan algoritma untuk menangani graf akan berdampak besar bagi ilmu komputer. Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap sisi. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat sisinya berarah, yang secara teknis disebut graf berarah atau digraf (directed graph). Digraf dengan sisi berbobot disebut jaringan. Jaringan banyak digunakan pada cabang praktis teori graf yaitu analisis jaringan. Perlu dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah). 9.1.1. Representation of Graph Salah satu cara yang mudah untuk merepresentasikan graph adalah menggunakan sebuah array 2 dua dimensi yang dikenal dengan Adjacency Matrix. Adjacency Matrix merupakan representasi matriks n x n yang menyatakan hubungan antar simpul dalam suatu graf. Kolom dan baris dari matriks ini merepresentasikan simpul-simpul, dan nilai entri dalam matriks ini menyatakan hubungan antar simpul, apakah terdapat sisi yang menghubungkan kedua simpul tersebut. Pada sebuah matriks nxn, entri non-diagonal aij merepresentasikan sisi dari simpul i dan simpul j. Sedangkan entri diagonal aii menyatakan sisi kalang(loop) pada simpul i.Gambar 4: Graf tak berarah berlabel

Gambar 5: Adjacency matrix Gambar 5 merupakan adjacency matrix yang berkorelasi dengan graf tak berarah pada gambar 4. Kolom dan baris pada matriks merupakan simpul- simpul berlabel 1-6. Kelebihan dari adjacency matrix ini adalah elemen matriksnya dapat diakses langsung melalui indeks, dengan begitu hubungan ketetanggan antara kedua simpul dapat ditentukan dengan langsung. Sedangkan kekurangan pada representasi ini adalah bila graf memiliki jumlah sisi atau busur yang relative sedikit, karena matriksnya bersifat jarang yaitu hanya mengandung elemen bukan nol yang sedikit. Kasus seperti ini merugikan, karena kebutuhan ruang memori untuk matriks menjadi boros dan tidak efisien karena komputer menyimpan elemen 0 yang tidak perlu. Jika graph tidak rapat dengan kata lain jika graph renggang, solusi yang lebih baik adalah menggunakan representasi Adjacency list. adjacency list merupakan bentuk representasi dari seluruh sisi atau busur dalam suatu graf sebagai suatu senarai. Simpul-simpul yang dihubungkan sisi atau busur tersebut dinyatakan sebagai simpul yang saling terkait. Dalam implementasinya, hash table digunakan untuk menghubungkan sebuah simpul dengan senarai berisi simpul-simpul yang saling terkait tersebut.

Gambar 3 : Undirected Cyclic Graph Graf pada gambar 3 dapat dideskripsikan sebagai senarai {a,b},{a,c},{b,c}. Dan representasi adjacency list dapat digambarkan melalui tabel di bawah ini.

Tabel 1. Representasi Adjacency List Vertex Adjacency a Adjacent to b Adjacent to c Adjacent to

Array of Adjacent b,c a,c a,b

Salah satu kekurangan dari teknik representasi ini adalah tidak adanya tempat untuk menyimpan nilai yang melekat pada sisi. Contoh nilai ini antara lain berupa jarak simpul, atau beban simpul. 9.2 Topological Sort Topological sort adalah suatu urutan simpul dengan graf acyclic terarah. Dengan kata lain jika ada jalandari vI ke vj, maka vj muncul setelah vi saat pengurutan.

Gambar diatas merupakan contoh graf acyclic yang merepresentasikan struktur prasyarat rangkaian. Pengurutan topological dari rangkaian ini adalah setiap urutan rangkaian tidak boleh melanggar syarat prasyarat. Sudah jelas bahwa dalam pengurutan topologi tidak mungkin jika grafik memiliki siklus, karena pada dua simpul v dan w pada siklus, v mendahului w, dan w mendahului v. selain itu, pengurutan tidak harus unik, hanya pengurutan yang sah yang dilakukan.

Pada graf diatas, v1, v2, v5, v4, v3, v7, v6 dan v1, v2, v5, v4, v7, v3, v6 adalah pengurutan topological. Algoritma yang sederhana untuk menemukan pengurutan topological adalah pertama, menemukan simpul tanpa ujung. Nantinya simpul ini dapat dicetak dn dihapus bersama dengan tepinya dari graf tersebut. Strategi yang sama dapat diterapkan oleh seluruh grafik. Untuk merumuskannya, kita definisikan indegree dari simpul v sebagai nilai dari sisi(u,v). kita hitung indegree dari seluruh simpul pada graf. Dengan asmusi bahwa indegree dari setiap simpul disimpan dan ditafsirkan oleh sebuah adjacency list.

Method findNewVertexOfIndegreeZero meninjau array untuk mencari simpul dengan indegree 0 yang belum diberi nomor topological. Method inin mengembalikan nilai null bila simpul yang dicari tidak ada. Hal ini menunjukkan bahwa graf tersebut memiliki siklus.

Karena findNewVertexOfIndegreeZero adalah peninjauan sekuensial secara sederhana dari array simpul, maka setiap proses membutuhkan waktu O (| V |). Karena ada | V | seperti panggilan, waktu berjalan dari algoritma ini adalah O (| V | 2). Dengan lebih berhati-hati memperhatikan struktur data, tidak mustahil untuk melakukan yang lebih baik. Penyebab waktu berjalan yang buruk adalah peninjauan secara sekuensial melalui array simpul. Jika grafik jarang, kita akan mengharapkan bahwa hanya sedikit simpul yang indegrees-nya diperbarui setiap iterasi. Namun, dalam pencarian simpul dari indegree 0, kita berpotensi melihat semua simpul, meskipun hanya sedikit yang berubah. Kita dapat menghapus ketidak-efisiensi-an ini dengan menjaga semua (unassigned) simpul dari indegree 0 dalam kotak khusus. Method findNewVertexOfIndegreeZero kemudian kembali (dan menghapus) setiap titik dalam kotak. Ketika pengurangan indegrees dari simpul yang berdekatan, kita periksa setiap titik dan tempatkan dalam kotak jika indegree nya 0. Untuk mengimplementasikan kotak, kita dapat menggunakan salah satu stack atau queue, kita akan menggunakan antrian. Pertama, indegree dihitung untuk setiap simpul. Kemudian semua simpul dari indegree 0 ditempatkan pada antrian yang awalnya kosong. Selama antrian tidak kosong, simpul v akan dihapus, dan semua simpul yang berdekatan dengan v indegreenya diturunkan. Sebuah simpul disimpan di antrian segera setelah indegree nya 0. Urutan topological selanjutnya adalah urutan simpul dequeue. Tabel dibawah menunjukkan status setelah setiap tahap.

Implementasi pseudocode dari algoritma ini ditunjukkan pada Gambar 9.7. Kita anggap setiap simpul memiliki bidang bernama topNum, dimana penomorannya secara topological. Waktu untuk mengeksekusi algoritma ini adalah O (| E | + | V |) jika menggunakan adjacency list meskipun ada nested loop. Sudah jelas bahwa tubuh loop dieksekusi paling banyak satu kali per tepi. Operasi antrian dilakukan paling banyak satu kali per titik, dan langkah-langkah inisialisasi lainnya, termasuk perhitungan indegrees, juga membutuhkan waktu sebanding dengan ukuran graf. 9.3 Shortest-Path Algorithm Pada bagian ini kita akan mengkaji berbagai masalah shortest-path. Inputnya adalah grafik berbobot: yang terkait dengan setiap tepi (vi, vj) adalah nilai ci,j untuk melintasi tepi. Nilai yang dibutuhkan untuk perjalanan v1v2. . . vN adalah

. Hal ini disebut sebagai panjang jalan berbobot. Panjang jalan tak berbobot adalah jumlah tepi pada jalur, yaitu N - 1. Single-source Shortest-Path Problem Diberikan sebagai input graf berbobot G = (V, E), dan sebuah simpul yang dibedakan, s, menemukan jalur terpendek berbobot dari s ke setiap simpul lainnya di G.

Sebagai contoh, dalam grafik pada Gambar 9,8, jalan terpendek berbobot dari v1 ke v6 memiliki nilai 6 dan jalurnya dari v1 ke v4 ke v7 ke v6. Jalan terpendek terpendek tak berbobot antara simpul ini adalah 2.

Grafik di Gambar 9.9 menunjukkan masalah yang dapat menyebabkan tepi bernilai negatif. Jalan dari v5 ke v4 memiliki nilai 1, tapi jalan yang lebih pendek bisa dihasilkan dengan mengikuti loop v5, v4, v2, v5, v4, yang memiliki nilai -5. Jalan ini bukan terpendek, karena kita melakukan loop panjang seenaknya. Dengan demikian, jalur terpendek antara dua titik tidak terdefinisi. Demikian pula, jalur terpendek dari v1 ke v6 tidak terdefinisi, karena kita bisa masuk ke dalam lingkaran yang sama. Loop ini dikenal sebagai siklus nilai negatif. Nilai negatif tepi bukan merupakan hal yang buruk, sebagai siklus, tapi dapat membuat masalah lebih rumit. Untuk kenyamanan, siklus nilai negative ditiadakan, jalur terpendek dari s ke s adalah nol.

Pengujian algoritma untuk memecahkan empat versi dari masalah ini adalah pertama, kita pertimbangkan masalah jalan terpendek tak berbobot dan menunjukkan bagaimana mengatasinya dalam O (| E | + | V |). Selanjutnya, kita tunjukkan cara untuk memecahkan masalah jalan terpendek berbobot jika kita menganggap bahwa tidak ada tepi negatif. Waktu berjalan untuk algoritma ini adalah O (| E | log | V |) ketika diimplementasikan dengan struktur data yang wajar. Jika grafik memiliki tepi negatif, ada solusi yang sederhana, namun sayangnya memiliki waktu yang buruk terikat O (| E | | V |). sehingga, kita harus memecahkan berbobot masalah untuk khusus kasus grafik asiklik dalam waktu linier. 9.3.1. Unweighted Shortest Paths

Gambar 9.10 menunjukkan grafik tak berbobot, G. Menggunakan beberapa simpul, s, yang merupakan parameter input, kita akan mencari jalur terpendek dari s ke semua simpul lainnya. Kita hanya tertarik pada jumlah tepi yang terdapat pada jalan, sehingga tidak ada beban pada tepi. Hal ini jelas merupakan kasus khusus dari masalah jalan terpendek berbobot, karena kita bisa menetapkan semua sisi berat adalah 1. Misalkan kita memilih untuk menuju v3. Dapat dikatakan bahwa jalan terpendek dari s ke v3 adalah jalan dari panjang 0. Seprti pada Gambar 9.11.

Sekarang kita dapat mulai mencari semua simpul yang jaraknya 1 dari s. Simpul ini yang bisa ditemukan dengan melihat simpul yang berdekatan dengan s. Jika kita melakukan ini, kita melihat bahwa v1 dan v6 adalah satu sisi dari s. Hal ini ditunjukkan pada Gambar 9.12.

Sekarang kita dapat menemukan simpul yang terpendek jalur dari s = 2, dengan mencari semua berdekatan dengan v1 dan v6 (simpul pada jarak 1), yang jalur terpendeknya belum diketahui. Pencarian ini memberitahu kita bahwa jalur terpendek ke v2 dan v4 adalah 2. Gambar 9.13 menunjukkan kemajuan yang telah dibuat sejauh ini.

Akhirnya kita dapat menemukan, dengan memeriksa simpul berdekatan dengan v2 dan v4 baru-baru ini dievaluasi, yaitu v5 dan v7 yang memiliki jalur terpendek dari tiga sisi. Semua simpul kini telah dihitung, dan Gambar 9.14 menunjukkan hasil akhir dari algoritma.

Strategi untuk mencari grafik ini dikenal sebagai breadth-first search. Mengingat kita harus menerjemahkan strategi inivkode. Gambar 9.15 menunjukkan awal konfigurasi meja bahwa algoritma kita akan menggunakan untuk melacak kemajuannya.

Algoritma dasarnya digambarkan pada Gambar 9.16. Algoritma pada Gambar 9.16 meniru diagram dengan pendeklarasian sebagai simpul yang diketahui pada jarak d = 0, maka d = 1, maka d = 2, dan seterusnya, dan mengatur semua simpul yang berdekatan w yang nilainya masih dw = ke dw = d + 1.

Waktu berjalan dari algoritma ini adalah O (| V | 2), karena terdapat doubly nested loops. Sebuah ketidak-efisiensi-an yang jelas adalah bahwa loop terluar terus berjalan sampai NUM_VERTICES - 1, bahkan jika semua simpul sudah diketahui sebelumnya. Meskipun pengujian tambahan dapat dibuat untuk menghindari hal ini, tidak akan mempengaruhi running time terburuk, seperti dapat dilihat dengan generalisasi apa yang terjadi ketika input adalah grafik pada Gambar 9.17 dengan start vertex v9.

Kita dapat menghapus ketidak-efisiensian ini dengan cara yang sama dengan topologi. Pada setiap titik waktu, hanya ada dua jenis simpul yang tidak diketahui yang memiliki dv . Beberapa dv = currDist dan sisanya memiliki dv = currDist + 1. Namun hal ini sangat mebuang-buang waktu karena harus mencari di seluruh tabel untuk menemukan simpul yang sebenarnya.

Solusi yang sangat sederhana namun abstrak adalah dengan menjaga dua kotak. Kotak #1 memiliki simpul tidak diketahui dengan currDist = dv, dan kotak #2 memiliki dv = currDist + 1. Untuk menguji penemuan simpul v yang tepat, v dapat diganti dengan mencari setiap titik di dalam kotak #1. Setelah memperbarui w (ada di paling dalam jika blok), kita dapat menambahkan w untuk kotak #2. Setelah loop terluar berakhir, kotak #1 kosong, dan kotak #2 dapat ditransfer ke kotak #1 untuk tahap berikutnya. Algoritmanya ditunjukkan pada Gambar 9.18 dan Gambar 9.19 menunjukkan bagaimana nilai-nilai pada grafik berubah selama proses. Dengan analisis yang sama dengan jenis topologi, dapat dilihat bahwa running time nya adalah O (| E | + | V |), selama daftar adjacency digunakan.

9.3.2. Dijkstras Algorithm Jika grafik diberi bobot, masalah (ternyata) menjadi lebih sulit, tetapi kita masih dapat menggunakan cara dari kasus tak berbobot. Metode umum untuk memecahkan masalah single-source shortest-path dikenal sebagai Algoritma Dijkstra. Algoritma Greedy umumnya memecahkan masalah secara bertahap dengan mengerjakan yang terlihat terbaik pada setiap tahap. Misalnya, untuk membuat perubahan dalam mata uang AS, yang paling menghitung orang keluar kuartal pertama, kemudian dime, sen, dan uang. Algoritma rakus memberikan perubahan menggunakan jumlah minimum koin. Masalah utama dengan algoritma greedy adalah bahwa mereka tidak selalu bekerja. Penambahan sepotong 12-sen dapat merubah algoritma koin untuk mengembalikan 15 sen, karena jawaban yang diberikan (sebuah 12-sen dan tiga sen) tidak optimal (satu dime dan satu nikel). Grafik pada Gambar 9.20 adalah contoh kita. Gambar 9.21 merupakan konfigurasi awal, dengan asumsi bahwa node awal, s, adalah v1.Simpul pertama yang

dipilih adalah v1, dengan panjang jalan 0. Simpul inidiketahui. Sehingga sekarang v1 diketahui, beberapa entri perlu disesuaikan. Simpul yang berdekatan dengan v1 adalah v2 dan v4. Kedua simpul mendapatkan masukan mereka disesuaikan, sebagai ditunjukkan pada Gambar 9.22.

Kemudian v4 dipilih dan diketahui. Simpul v3, v5, v6, v7 dan berdekatan, dan ternyata semua memerlukan penyesuaian, seperti yang ditunjukkan pada Gambar 9.23.

Selanjutnya, v2 dipilih. v4 berdekatan tapi sudah diketahui, sehingga tidak ada pekerjaan dilakukan disini. v5 berdekatan tapi tidak disesuaikan, karena nilai yang melalui v2 adalah 2 + 10 = 12 dan jalur dengan panjang 3 sudah diketahui. Gambar 9.24 menunjukkan tabel setelah ini adalah simpul dipilih.

Simpul berikutnya yang dipilih adalah v5 dengan biaya 3. v7 adalah satusatunya titik yang berdekatan, tetapi tidak disesuaikan, karena 3 + 6> 5. Kemudian v3 dipilih, dan jarak untuk v6 disesuaikan ke bawah sampai 3 + 5 = 8. Tabel yang dihasilkan digambarkan pada Gambar 9.25.

v7 Berikutnya dipilih; v6 diperbarui menjadi 5 + 1 = 6. Tabel yang dihasilkan adalah Gambar 9.26. Akhirnya, v6 dipilih. Tabel terakhir ditunjukkan pada Gambar 9.27. Gambar 9.28 secara grafis menunjukkan bagaimana tepi ditandai dikenal dan titik diperbarui dalam algoritma Dijkstra.

Sekarang kita berikan pseudocode untuk mengimplementasikan algoritma Dijkstra. Setiap Vertex disimpan di berbagai field data yang digunakan dalam algoritma. Hal ini ditunjukkan pada Gambar 9.29.

Jalan itu dapat dicetak menggunakan routine rekursif pada Gambar 9.30. Routine rekursif mencetak jalan sepanjang jalan sampai ke titik sebelum v di jalan dan kemudian mencetak v. Hal ini bekerja secara sederhana. Gambar 9.31 menunjukkan algoritma utama, yang hanya loop untuk mengisi tabel dengan menggunakan aturan greedy selection.

Waktu berjalan tergantung pada bagaimana simpul dimanipulasi, yang belum dipertimbangkan. Jika kita menggunakan algoritma nyata dari pemindaian berurutan simpul untuk menemukan dv minimum, setiap tahap akan memerlukan waktu O (|V|) untuk menemukan nilai minimum, dengan demikianwaktu selama O (|V|2) akan dihabiskan untuk menemukan nilai minimum selama satu algoritma. Waktu untuk memperbarui dw adalah konstan per pembaruan, dan paling banyak adalah satu pembaruan per tepi untuk total O (|E|). Dengan demikian, waktu berjalan total adalah O(|E|+|V|2) = O(|V|2). Jika grafik padat, dengan | E | = (|V|2), algoritma ini tidak hanya sederhana tetapi juga optimal, karena berjalan dalam waktu linier dalam jumlah tepi. Jika grafiknya jarang, dengan |E| = (|V|), algoritma ini terlalu lambat. Dalam hal ini, jarak perlu disimpan dalam antrian prioritas. Sebenarnya ada dua cara untuk melakukan ini; keduanya sama.

9.3.3. Graph with Negative Edge Cost Jika grafik memiliki nilai tepi negatif, maka algoritma Dijkstra tidak akan bekerja. Masalahnya adalah sekali u simpul dinyatakan diketahui, ada kemungkinan dari beberapa simpul lainnya, simpul v yang tidak diketahui memiliki jalan kembali ke u yang sangat negatif. Dalam kasus seperti itu, mengambil jalan dari s ke v kembali ke u lebih baik daripada pergi dari s ke u tanpa menggunakan v. Sebuah solusi yang menarik adalah menambahkan konstan untuk setiap biaya tepi, sehingga menghilangkan tepi negatif, menghitung jalur terpendek pada grafik baru, dan kemudian menggunakan hasilnya kepada yang asli. Implementasi naif dari strategi ini tidak bekerja karena jalan dengan banyak tepi menjadi lebih berat daripada jalan dengan beberapa tepi. Kombinasi algoritma berbobot dan tak berbobot akan memecahkan masalah, tetapi pada nilai peningkatan yang drastis saat waktu berjalan. Kita mulai dengan menempatkan s pada antrian. Kemudian, pada setiap tahap, kita dequeue simpul v. Kita akan menemukan semua simpul w yang berdekatan dengan v sehingga dw > dv + cv,w. Kita perbarui dw dan pw, dan tempatkan w di antrian jika belum ada. Sedikit dapat diatur untuk setiap simpul untuk menunjukkan kehadiran dalam antrian. Antrian diulangi terus menerus hingga kosong. Gambar 9.32(hampir) mengimplementasikan algoritma ini.

Meskipun algoritma bekerja jika tidak ada nilai siklus negatif, maka tidak lagi benar bahwa kode di dalam loop dijalankan sekali per tepi. Setiap simpul dapat didequeue paling tidak |V| kali, sehingga waktu berjalannya adalah O(|E| |V|) jika adjacency list digunakan. Hal ini cukup meningkat dari algoritma Dijkstra, sehingga sangat menguntungkan dalam prakteknya, nilai tepi adalah nonnegatif. Jika nilai siklus negative yang hadir, maka algoritma seperti yang tertulis akan berulang tanpa batas. Dengan menghentikan algoritma ini setelah setiap simpul memiliki dequeued |V| + 1 kali, kita dapat menjamin penghentian. 9.3.4. Acyclic Graphs Jika grafik diketahui asiklik, kita dapat meningkatkan algoritma Dijkstra dengan mengubah urutan simpul dinyatakan diketahui, atau diketahui sebagai aturan pemilihan simpul. Aturan baru adalah dengan memilih simpul untuk topologi. Algoritma ini dapat diselesaikan dalam satu proses, karena pilihan dan pembaruan dapat berlangsung sebagai jenis topologi sedang dilakukan. Aturan seleksi bekerja karena ketika simpul v dipilih, jarak, d v, tidak bisalagi diturunkan, karena dengan aturan pengurutan topologi, ini tidak memiliki ujung masukan yang berasal dari node diketahui. Sebuah grafik asiklik bisa meniru beberapa masalah skiing (kita akan pergi dari titik a ke b tetapi hanya dapat turun bukit), jadi jelas tidak ada siklus. Aplikasi lain yang mungkin bisa ditiru adalah reaksi kimia (nonreversible). Suatu penggunaan yang lebih penting dari grafik asiklik adalah critical path analysis (analisa jalur kritis). Grafik di Gambar 9.33 akan menjadi contoh kita. Setiap node merupakan suatu aktivitas yang harus dilakukan, bersama dengan waktu yang dibutuhkan untuk menyelesaikan aktivitas. Grafik ini dikenal sebagai sebuah grafik aktivitas-node. Tepi mewakili hubungan yang diutamakan: tepi (v, w) berarti bahwa aktivitas v harus diselesaikan sebelum kegiatan w mungkin dimulai. Tentu saja, ini berarti bahwa grafik harus asiklik. Kita asumsikan bahwa setiap kegiatan yang tidak tergantung (baik secara langsung atau tidak langsung) satu sama lain dapat dilakukan secara paralel oleh server yang berbeda.

Untuk melakukan perhitungan ini, kita mengubah grafik aktivitas-node ke event-node graph. Setiap event sesuai dengan selesainya suatu aktivitas dan semua aktivitas yang tergantung. Event dicapai dari simpul v dalam grafik event-node mungkin tidak dapat dimulai sampai event v selesai. Grafik ini dapat dibangun secara otomatis atau dengan tangan. Tepi tiruan dan simpul mungkin perlu dimasukkan dalam kasus di mana suatu kegiatan tergantung pada yang lainnya. Hal ini diperlukan untuk menghindari dependensi palsu (atau salah kurangnya dependensi). Grafik event-node yang sesuai dengan grafik pada Gambar 9.33 ditunjukkan oleh Gambar 9.34.

Untuk menemukan waktu penyelesaian awal proyek, kita hanya perlu menemukan panjang jalan terpanjang dari event pertama ke event terakhir. Untuk grafik biasanya, masalah jalan-terpanjang umumnya tidak masuk akal, dikarenakan kemungkinan nilai siklus positif. Ini adalah setara dengan masalah nilai siklus negative pada jalan terpendek. Jika siklus positif yang hadir, kita bisa meminta jalan terpanjang sederhana, tetapi tidak ada solusi yang memuaskan dikenal untuk masalah ini. Karena graf event-node adalah asiklik, kita tidak perlu khawatir tentang siklus. Dalam hal ini, adaptasi mudah dilakukan oleh algoritma-jalan terpendek untuk menghitung awal penyelesaian waktu untuk semua node dalam grafik. Jika ECi adalah waktu penyelesaian paling awal untuk node i, maka aturan yang berlaku adalah:

Gambar 9.35 menunjukkan waktu penyelesaian paling awal untuk setiap peristiwa dari contoh grafik event-node. Kita juga dapat menghitung waktu terakhir, LCi, bahwa setiap peristiwa dapat menyelesaikan tanpa mempengaruhi waktu akhir penyelesaian. Rumus untuk melakukan hal ini adalah

Nilai-nilai ini dapat dihitung dalam waktu linier dengan mempertahankan, untuk setiap simpul, sebuah daftar dari simpul yang berdekatan dan terdahulu. Waktu selesai terbaru yang ditunjukkan pada Gambar 9.36.

Waktu slack untuk setiap tepi dalam grafik event-node merupakan jumlah waktu yang penyelesaian aktivitasnya dapat ditunda tanpa menunda penyelesaian keseluruhan. Sangat mudah untuk melihat bahwa Gambar 9.37 menunjukkan kendur (sebagai entri ketiga) untuk setiap kegiatan dalam grafik event-node. Untuk setiap node, nomor teratas adalah waktu penyelesaian paling awal dan masuknya bawah adalah terbaru penyelesaian waktu.

Beberapa aktivitas memiliki slack nol. Ini adalah aktivitas kritis, yang harus diselesaikan sesuai dengan jadwal. Setidaknya ada satu jalur yang seluruhnya terdiri dari tepi zero-slack, jalan semacam itu disebut jalur kritis.

9.3.5. All-Pairs Shortest Path Kadang-kadang penting untuk menemukan jalan terpendek antara semua pasang simpul dalam grafik. Meskipun kita bisa menjalankan single-source algorithm yang tepat |V| kali, kita mungkin mengharapkan solusi yang agak lebih cepat, terutama pada grafik padat, jika kita menghitung semua informasi sekaligus. Dalam Bab 10, kita akan melihat algoritma O (|V|3) untuk memecahkan masalah ini untuk grafik berbobot. Meskipun, untuk grafik padat, hal ini sama dengan menjalankan secara sederhana algoritma Dijkstra (antrian tidak diprioritaskan) |V| kali, loop terjadi begitu ketat yang dispesialkan untuk semua-pasangan algoritma yang mungkin akan lebih cepat dalam praktek. Pada grafik jarang, tentu saja, itu lebih cepat untuk menjalankan |V| algoritma Dijkstra yang dikodekan dengan antrian prioritas. 9.3.6. Shortest-Path Example Pada bagian ini kita menulis beberapa rutinitas Java untuk menghitung tangga kata. Dalam tangga kata setiap kata dibentuk dengan mengubah satu karakter dalam kata sebelumnya tangga tersebut. Sebagai contoh, kita dapat mengkonversi zero sampai five dengan urutan satu karakter substitusi sebagai berikut: zero hero here hire fire five. Ini adalah masalah terpendek tak berbobot di mana setiap kata adalah simpul, dan dua simpul memiliki tepi (dua arah) antara mereka jika mereka dapat dikonversi ke satu sama lain dengan substitusi satu karakter. Pada Bagian 4.8, kita menjelaskan dan menulis routine Java yang akan menciptakan sebuah himpunan dengan kunci kata-kata, dan nilai-nilainya adalah daftar yang berisi kata-kata yang dapat mengakibatkan dari transformasi satu karakter. Dengan demikian, himpunan ini merupakan grafik, dalam format adjacency list, dan kita hanya perlu menulis satu routine untuk menjalankan single-source unweighted algoritma terpendek dan rountine kedua untuk output urutan kata-kata, setelah single-source unweighted algoritma terpendek selesai. Kedua rutinitas ini ditunjukkan pada Gambar 9.38.

9.4 Network Flow Problem Misal diberikan grafik G = (V, E) dengan kapasitas tepi cv, w. Kapasitas ini bisa mewakili jumlah air yang mengalir melalui pipa atau jumlah lalu lintas yang dapat

mengalir di jalan di antara dua persimpangan. Kita memiliki dua simpul: s, yang kita sebut sumber, dan t, yang merupakan muara. Melalui tepi apapun, (v, w),di unit cv, w aliran bisa terlewati. Pada setiap titik v, yang bukan s atau t, aliran masuk harus sama dengan total aliran keluar. Masalah arus maksimum adalah menentukan jumlah maksimum aliran yang dapat lewat dari s ke t. Sebagai contoh, untuk grafik pada Gambar 9.39 aliran maksimum kiri adalah 5, seperti ditunjukkan oleh grafik di kanan. Meskipun contoh grafik ini adalah asiklik, ini bukan ketentuan; algoritma akan bekerja bahkan jika grafik memiliki siklus.

Sebagaimana disyaratkan oleh pernyataan masalah, tidak ada tepi yang membawa aliran lebih dari kapasitasnya. Vertex memiliki tiga unit aliran masuk, yang didistribusikan untuk c dan d. Vertex d mengambil tiga unit aliran dari a dan b dan menggabungkan keduanya, mengirimkan hasilnya ke t. Sebuah simpul dapat menggabungkan dan mendistribusikan aliran dengan cara apapun yang ia suka, selama kapasitas tepi tidak dilanggar dan selama konservasi aliran tetap terjaga (apa yang masuk harus keluar). Melihat grafik, kita melihat bahwa s memiliki tepi kapasitas 4 dan 2 meninggalkannya, dan t memiliki tepi kapasitas 3 dan 3 memasukinya. Jadi mungkin aliran maksimum bisa menjadi 6 bukan 5. Namun, Gambar 9.40 menunjukkan bagaimana kita dapat membuktikan bahwa aliran maksimum adalah 5. Kita potong grafik menjadi dua bagian, satu bagian berisi s dan beberapa simpul lainnya; bagian lain berisi t. Karena aliran harus menyeberang melalui potongan, total kapasitas semua sisi (u, v) dimana u di partisi s dan v adalah di partisi t adalah ikatan pada aliran maksimum. Ujung-ujungnya (a, c) dan (d, t), dengan total kapasitas 5, jadi aliran maksimum tidak dapat melebihi 5. Setiap grafik memiliki sejumlah besar potongan; cut dengan total kapasitas minimal menyediakan ikatan pada aliran maksimum, dan ternyata, kapasitas pemotongan minimum persis sama dengan arus maksimum.

9.4.1. A Simple Maximum-Flow Algorithm Upaya pertama untuk memecahkan masalah dilakukan secara bertahap. Kita mulai dengan grafik kita, G, dan membangun Gf grafik aliran. Gf menceritakan aliran yang telah dicapai pada setiap tahap dalam algoritma. Awalnya semua sisi di Gf memiliki tidak memiliki arus, dan kita berharap bahwa ketika algoritma berakhir, Gf berisi aliran.Kita maksimal juga membangun sebuah grafik, Gy, yang disebut sisa grafik. Gy mengatakan, untuk setiap sisi, berapa banyak aliran yang lebih dapat ditambahkan. Kita bisa menghitung ini dengan mengurangi aliran arus dari kapasitas untuk setiap sisinya. Kelebihan Gy dikenal sebagai sisa tepi. Pada setiap tahap, kita menemukan jalan di Gy dari s ke t. Jalan ini dikenal sebagai penambah jalan. Tepi minimum di jalan ini adalah jumlah arus yang dapat ditambahkan untuk setiap tepi di jalan. Kami melakukan ini dengan menyesuaikan Gf dan Gy recomputing. Ketika kita tidak menemukan jalan dari s ke t di Gy, proses diakhiri. Algoritma ini tidak dideterminasi, kita bebas untuk memilih jalur dari s ke t; jelas beberapa pilihan lebih baik daripada yang lain, dan kita akan mengatasi masalah ini nanti. Kita akan menjalankan algoritma ini pada contoh. Grafik di bawah ini adalah G, Gf, Gy, masing-masing. Perlu diketahui bahwa ada sedikit cacat dalam algoritma ini. Awal konfigurasi pada Gambar 9.41.

Ada banyak jalan dari s ke t pada grafik sisa. Misalkan kita pilih s, b, d, t. Lalu kita bisa mengirim dua unit mengalir melalui tepi setiap di jalan ini. Kita akan mengadopsi konvensi bahwa sekali kita telah mengisi (penuh), tepi tersebut akan dihapus dari sisa grafik. Kemudian kita dapatkan Gambar 9.42.

Berikutnya, kita mungkin memilih jalur s, a, c, t, yang juga memungkinkan dua unit aliran. Hal ini ditunjukkan grafik pada Gambar 9.43.

Satu-satunya jalan kiri untuk memilih adalah s, a, d, t, yang memungkinkan satu unit aliran. Ditunjukkan pada Gambar 9.44.

Algoritma ini berakhir pada titik ini, karena t tidak bisa diakses dari s. Yang dihasilkan aliran dari 5 terjadi menjadi maksimal. Untuk melihat apa masalahnya, misalkan dengan grafik awal kita memilih jalan s, a, d, t. Jalur ini memungkinkan tiga

unit aliran dan dengan demikian tampaknya menjadi pilihan yang baik. Hasil pilihan ini, bagaimanapun, hanya meninggalkan satu jalur dari s ke t pada grafik sisa, yang memungkinkan satu unit lebih banyak aliran, dan dengan demikian, algoritma kita mengalami kegagalan menemukan solusi optimal. Ini adalah contoh dari algoritma rakus yang tidak bekerja. Gambar 9.45 menunjukkan mengapa algoritma gagal.

Untuk membuat algoritma ini bekerja, kita perlu membuat algoritma mengubah pikirannya. Untuk melakukan ini, untuk setiap sisi (v, w) dengan aliran fv,w pada grafik aliran, kita akan menambahkan sebuah sisi dalam grafik sisa (w, v) dari kapasitas fv,w. Akibatnya, kita membiarkan algoritma untuk membatalkan nya keputusan dengan mengirimkan arus kembali ke arah berlawanan. Hal ini paling baik dilihat dengan contoh. Mulai dari grafik asli kita dan memilih jalan menambah s, a, d, t, kita memperoleh grafik dalam Gambar 9,46.

Perhatikan bahwa dalam grafik sisa, ada tepi di kedua arah antara a dan d. Entah satu unit aliran lagi dapat didorong dari a ke d, atau sampai dengan tiga unit dapat didorong kembali kita dapat membatalkan aliran. Sekarang algoritma

menemukan cara untuk menambah jalan s, b, d, a, c, t, dari aliran 2. Dengan mendorong dua unit mengalir dari d ke a, algoritma mengambil dua unit aliran jauh dari tepi (a, d) dan pada dasarnya mengubah pikirannya. Gambar 9.47 menunjukkan grafik baru.

Tidak ada jalur menambah dalam grafik ini, sehingga algoritma berakhir. Perhatikan bahwa hasil yang sama akan terjadi jika pada Gambar 9.46, jalan menambah s, a, c, t dipilih yang memungkinkan satu unit aliran, karena dengan begitu jalan menambah berikutnya dapat ditemukan. Sangat mudah untuk melihat bahwa jika algoritma berakhir, maka harus berakhir dengan aliran maksimal. Pemutusan menyiratkan bahwa tidak ada jalan dari s ke t pada grafik sisa. Jadi memotong sisa grafik, menempatkan simpul dicapai dari s di satu sisi, dan tidak bisa dicapai (termasuk t) di sisi lain. Gambar 9.48 menunjukkan pemotongan. Jelas setiap tepi dalam graf G asli yang melintasi pemotongan harus penuh, jika tidak, akan ada sisa aliran yang tersisa di salah satu tepi, yang kemudian akan berarti keunggulan yang melintasi pemotongan (di arah yang salah) di Gy. Tapi itu berarti bahwa aliran dalam G persis sama dengan kapasitas pemotongan G, maka kita memiliki aliran maksimum.

Jika biaya tepi dalam grafik adalah bilangan bulat, maka algoritma harus berhenti, masing-masing augmentasi menambahkan unit aliran, jadi kita akhirnya mencapai aliran maksimum, meskipun tidak ada jaminan bahwa ini akan menjadi efisien. Secara khusus, jika kapasitas semua bilangan bulat dan aliran maksimum adalah f, maka, karena masing-masing jalan menambah meningkatkan nilai aliran dengan di 1 setidaknya, f tahap cukup, dan waktu berjalan total adalah O (f | E |), karena jalan yang dapat menambah ditemukan dalam O (| E |) waktu dengan algoritma terpendek-jalan unweighted. Contoh klasik dari mengapa ini adalah waktu yang berjalan buruk ini ditunjukkan oleh grafik pada Gambar 9.49.

Aliran maksimum dilihat dengan inspeksi menjadi 2.000.000 dengan mengirimkan 1.000.000 bawah setiap sisi. Augmentations acak terus bisa menambah sepanjang jalur yang mencakup tepi terhubung dengan a dan b. Jika ini terjadi berulang kali, 2.000.000 augmentations akan diperlukan, ketika kita bisa bertahan dengan hanya 2. Sebuah metode sederhana untuk mengatasi masalah ini selalu memilih menambah jalan yang memungkinkan peningkatan terbesar dalam aliran. Menemukan jalan semacam itu mirip dengan memecahkan masalah-jalan terpendek tertimbang dan modifikasi single-line untuk algoritma Dijkstra akan melakukan trik. Jika capmax adalah kapasitas maksimum tepi, maka salah satu dapat menunjukkan yang O (| E | Log capmax) augmentations akan cukup untuk menemukan aliran maksimum. Dalam hal ini, sejak O (| E | log | V |) waktu digunakan untuk setiap perhitungan jalur menambah, total terikat O (| E | 2 log | V | Log capmax) diperoleh. Jika kapasitas semua bilangan bulat kecil, ini mengurangi ke O (| E | 2 log | V |).

SIMPULAN Teori graf adalah cabang kajian yang mempelajari sifat-sifat graf. Secara informal, suatu graf adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan busur). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan gelang (loop). Untuk merepresentasikan graf ada 2 cara yaitu dengan menggunakan Adjacency matrix atau Adjacency list. Pengurutan pada algoritma graf dapat menggunakan cara topological sort. Topological sort adalah suatu urutan simpul dengan graf acyclic terarah. Dalam Algoritma graf terdapat permasalahan megenai Algoritma jalan terpendek yang inputnya adalah grafik berbobot dan tak berbobot. Untuk memecahkan masalah tersebut terdapat solusi yaitu menggunakan Algoritma Dijkstra. Namun ALgoritma Dijkstra idak akan bekerja jika memiliki nilai tepi negative, sehingga harus dihilangkan. Untuk meningkatkan Algoritma Djikstra, kita dapat mengubah urutan simpul sehingga berbentuk asiklik. Untuk pemecahan masalah pencarian jalan terpendek untuk simpul yang berpasangan, kita bisa saja menggunakan single-source algorithm. Namun kita bisa menggunakan solusi yang lebih cepat yaitu menggunakan loop. Selain itu, kita juga memiliki masalah jaringan arus pada graf yang dapat diselesaikan menggunakan algoritma sederhana untuk mencari aliran maksimal.