Kamis-18 Mei-2017
Moh.Sabhan
Struktur Data
Nim : 160411100078

Python Graph

1954/5000

PuncakSebuah simpul adalah bagian paling dasar dari sebuah grafik dan juga disebut simpul.Sepanjang kita akan menyebutnya catatan. Sebuah simpul juga memiliki informasi tambahan dan kami menyebutnya sebagai payload.TepiTepi adalah bagian dasar grafik lainnya, dan menghubungkan dua simpul / tepi mungkin satu arah atau dua arah. Jika tepi dalam grafik sama-sama satu arah, grafik adalah graf berarah, atau digraf. Gambar yang ditunjukkan di atas bukanlah sebuah digraph.BeratTepi dapat diberi bobot untuk menunjukkan bahwa ada biaya untuk berpindah dari satu titik ke titik lainnya. Misalnya pada grafik jalan yang menghubungkan satu kota ke kota lain, bobot di tepian mungkin mewakili jarak antara kedua kota atau status lalu lintas.GrafikGrafik dapat diwakili oleh $ G $ di mana $ G = (V, E) $. $ V $ adalah kumpulan simpul dan $ E $ adalah seperangkat tepi. Setiap tepi adalah tupel $ (v, w) $ di mana $ w, v \ in V $. Kita bisa menambahkan komponen ketiga ke tupel tepi untuk mewakili sebuah bobot. Sebuah subgraf $ s $ adalah seperangkat tepi $ e $ dan simpul $ v $ sedemikian rupa sehingga $ e \ in E $ dan $ v \ in V $.Gambar di atas menunjukkan grafik berbobot sederhana dan kita dapat mewakili grafik ini sebagai himpunan dari enam simpul$$ V = \ {a, b, c, d, e, f \} $$Dan himpunan sembilan tepinya:(A, b, 7), (a, c, 9), (b, d, 15), (b, c, 10), (c, d) , 11), (c, f, 2), (d, e, 6), (e, f, 9) \} $$JalanJalur dalam grafik adalah urutan simpul yang dihubungkan oleh tepi. Kami biasanya menentukan jalur sebagai $ w_1, w_2, ..., w_n $ sehingga $ (w_i, w_ {i + 1}) \ in E $ untuk semua $ 1 \ le i \ le n-1 $. Panjang jalur yang tidak tertimbang adalah jumlah tepi di jalur $ (n-1) $. Panjang jalur tertimbang adalah jumlah bobot semua tepi di jalan.Misalnya pada gambar di atas, jalur dari $ a $ to $ e $ adalah urutan simpul $ (a, c, d, e) $. Tepinya adalah $ \ {(a, c, 9), (c, d, 11), (d, e, 6) \} $.SiklusSiklus dalam grafik terarah adalah jalur yang dimulai dan berakhir pada titik yang sama. Grafik tanpa siklus disebut grafik asiklik. Grafik terarah tanpa siklus disebut grafik asiklik terarah atau DAG.

Kode

Dalam kode tersebut, kita membuat dua kelas: Grafik, yang menyimpan daftar induk simpul, dan Vertex, yang mewakili setiap simpul dalam grafik

Sarankan edit