Saya tidak memiliki pelatihan dalam teori grafik, jadi terminologi saya buruk. Saya memiliki grafik pohon terarah yang memiliki "node redundant." Saya mendefinisikan "node redundant" karena mereka yang memiliki gelar = 2 dalam grafik pohon saya. Saya ingin menemukan cara yang efisien untuk mengembalikan semua jalur antara semua node non-redundan, lebih disukai menggunakan alat NetworkX (Python). Grafis yang sangat sederhana ini menunjukkan apa yang saya coba capai:

enter image description here

Jadi mengingat grafik ini, saya ingin mengembalikan tiga jalur (p1, p2, dan p3) yang mewakili koneksi antara 1-> 4, 5-> 4, dan 4-> 7.

Saya dapat menulis algoritma untuk melakukan ini "secara manual", dalam arti bahwa saya mulai dari node dengan derajat = 1 dan "berjalan" di sepanjang grafik sampai saya mencapai node non-gelar = 2 lainnya. Namun, saya curiga sudah ada cara formal untuk melakukan analisis semacam ini, tetapi saya tidak bisa mengetahuinya.

Untuk konteks lebih lanjut, grafik saya jauh lebih besar dan lebih rumit karena mereka representasi dari jaringan sungai, sesuatu seperti ini:

enter image description here

Tapi mereka selalu pohon, tidak ada siklus.

0
Jon 29 Mei 2021, 02:16

1 menjawab

Jawaban Terbaik

Tidak, saya khawatir Anda sudah mencapai cara paling efektif untuk melakukan jalur mini Anda. Anda dapat sedikit mempercepat pemrosesan dengan bekerja mundur dari node pertemuan, tetapi hanya itu yang dapat Anda tingkatkan. Melakukan hal itu akan memungkinkan Anda menghapus node perantara sedikit lebih efektif daripada hanya mencari node sumber (yang masih harus Anda lakukan). Namun, algoritma itu tidak sesederhana itu. Untuk saat ini, saya sarankan Anda tetap dengan desain sederhana yang sudah Anda miliki.


  • Masukkan semua node ke dalam set to_visit.
  • sedangkan to_visit tidak kosong:
    • node = to_visit.pop ()
    • Jika node memiliki gelar 1: # Sumber simpul: temukan jalan menuju pertemuan
      • jalur jejak sampai Anda menekan simpul gelar & gt; 2.
      • Hapus semua node perantara dari to_visit.
      • Path Emit.
1
Prune 29 Mei 2021, 00:01