SciPy graflari

Graflar bilan ishlash

Graflar muhim ma’lumotlar tuzilmasi hisoblanadi.

SciPy bunday ma’lumotlar tuzilmalari bilan ishlash uchun scipy.sparse.csgraph modulini taqdim etadi.

Qo‘shnilik matritsasi (adjacency matrix)

Qo‘shnilik matritsasi — nxn o‘lchamli matritsa bo‘lib, bu yerda n grafdagi elementlar soni.

Uning qiymatlari esa elementlar orasidagi bog‘lanishni ifodalaydi.

Misol:

A, B va C elementlaridan iborat bunday graf uchun bog‘lanishlar quyidagicha:

A va B 1 vazn bilan bog‘langan.

A va C 2 vazn bilan bog‘langan.

C va B bog‘lanmagan.

Qo‘shnilik matritsasi quyidagicha ko‘rinadi:

      A B C
   A:[0 1 2]  
   B:[1 0 0]
   C:[2 0 0]

Quyida qo‘shnilik matritsalari bilan ishlash uchun eng ko‘p qo‘llaniladigan metodlardan ba’zilari keltirilgan.

Bog‘langan komponentlar

connected_components() metodi yordamida barcha bog‘langan komponentlarni toping.

Misol

import numpy as np from scipy.sparse.csgraph import connected_components from scipy.sparse import csr_matrix arr = np.array([ [0, 1, 2], [1, 0, 0], [2, 0, 0] ]) newarr = csr_matrix(arr) print(connected_components(newarr))

O‘zingiz sinab ko‘ring »

Dijkstra

Grafda bir elementdan boshqasiga eng qisqa yo‘lni topish uchun dijkstra metodidan foydalaning.

U quyidagi argumentlarni qabul qiladi:

return_predecessors: boolean (aylanib chiqishning butun yo‘lini qaytarish uchun True, aks holda False).
indices: faqat shu elementdan boshlanadigan barcha yo‘llarni qaytarish uchun element indeksi.
limit: yo‘lning maksimal vazni.

Misol

1-elementdan 2-elementgacha bo‘lgan eng qisqa yo‘lni toping:

import numpy as np from scipy.sparse.csgraph import dijkstra from scipy.sparse import csr_matrix arr = np.array([ [0, 1, 2], [1, 0, 0], [2, 0, 0] ]) newarr = csr_matrix(arr) print(dijkstra(newarr, return_predecessors=True, indices=0))

O‘zingiz sinab ko‘ring »

Floyd Warshall

Barcha element juftliklari orasidagi eng qisqa yo‘lni topish uchun floyd_warshall() metodidan foydalaning.

Misol

Barcha element juftliklari orasidagi eng qisqa yo‘lni toping:

import numpy as np from scipy.sparse.csgraph import floyd_warshall from scipy.sparse import csr_matrix arr = np.array([ [0, 1, 2], [1, 0, 0], [2, 0, 0] ]) newarr = csr_matrix(arr) print(floyd_warshall(newarr, return_predecessors=True))

O‘zingiz sinab ko‘ring »

Bellman Ford

bellman_ford() metodi ham barcha element juftliklari orasidagi eng qisqa yo‘lni topa oladi, biroq bu metod manfiy vaznlar bilan ham ishlay oladi.

Misol

Manfiy vaznga ega berilgan grafda 1-elementdan 2-elementgacha bo‘lgan eng qisqa yo‘lni toping:

import numpy as np from scipy.sparse.csgraph import bellman_ford from scipy.sparse import csr_matrix arr = np.array([ [0, -1, 2], [1, 0, 0], [2, 0, 0] ]) newarr = csr_matrix(arr) print(bellman_ford(newarr, return_predecessors=True, indices=0))

O‘zingiz sinab ko‘ring »

Chuqurlik bo‘yicha aylanib chiqish (Depth First Order)

depth_first_order() metodi grafni berilgan tugundan boshlab chuqurlik bo‘yicha aylanib chiqish (depth first traversal) natijasini qaytaradi.

Bu funksiya quyidagi argumentlarni qabul qiladi:

graf.
grafni aylanib chiqish boshlanadigan element.

Misol

Berilgan qo‘shnilik matritsasi uchun grafni chuqurlik bo‘yicha aylanib chiqing:

import numpy as np from scipy.sparse.csgraph import depth_first_order from scipy.sparse import csr_matrix arr = np.array([ [0, 1, 0, 1], [1, 1, 1, 1], [2, 1, 1, 0], [0, 1, 0, 1] ]) newarr = csr_matrix(arr) print(depth_first_order(newarr, 1))

O‘zingiz sinab ko‘ring »

Kenglik bo‘yicha aylanib chiqish (Breadth First Order)

breadth_first_order() metodi grafni berilgan tugundan boshlab kenglik bo‘yicha aylanib chiqish (breadth first traversal) natijasini qaytaradi.

Bu funksiya quyidagi argumentlarni qabul qiladi:

graf.
grafni aylanib chiqish boshlanadigan element.

Misol

Berilgan qo‘shnilik matritsasi uchun grafni kenglik bo‘yicha aylanib chiqing:

import numpy as np from scipy.sparse.csgraph import breadth_first_order from scipy.sparse import csr_matrix arr = np.array([ [0, 1, 0, 1], [1, 1, 1, 1], [2, 1, 1, 0], [0, 1, 0, 1] ]) newarr = csr_matrix(arr) print(breadth_first_order(newarr, 1))

O‘zingiz sinab ko‘ring »

W3Schools Pathfinder

Yutuqlaringizni kuzating – bu bepul!

Ro'yxatdan o'tish Kirish