გრაფი არის წვეროების ნაკრები, რომლებიც დაკავშირებულია კიდეებით. ორი სტანდარტული წარმოდგენა არის მიმდებარე სია (თითოეული წვერო ინახავს მის მეზობლებს) და მიმდებარე მატრიცა (V×V ბულიანი ბადე). არჩევანი დამოკიდებულია გრაფის სიმკვრივეზე.
გრაფი არის წვეროების ნაკრები, რომლებიც დაკავშირებულია კიდეებით. ორი სტანდარტული წარმოდგენა არის მიმდებარე სია (თითოეული წვერო ინახავს მის მეზობლებს) და მიმდებარე მატრიცა (V×V ბულიანი ბადე). არჩევანი დამოკიდებულია გრაფის სიმკვრივეზე.
Graph: 0 - 1
| |
2 - 3
Adjacency list: Adjacency matrix:
0: [1, 2] 0 1 2 3
1: [0, 3] 0 [0 1 1 0]
2: [0, 3] 1 [1 0 0 1]
3: [1, 2] 2 [1 0 0 1]
3 [0 1 1 0]
# Adjacency list (dict of lists) — preferred for sparse graphs
adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
neighbors = adj[1] # O(1) to get a vertex's neighbors
# Adjacency matrix
matrix = [[0]*4 for _ in range(4)]
matrix[0][1] = matrix[1][0] = 1
has_edge = matrix[0][1] == 1 # O(1) edge lookup
| მიმდებარე სია | მიმდებარე მატრიცა | |
|---|---|---|
| სივრცე | O(V + E) | O(V²) |
| კიდე არსებობს? | O(ხარისხი) | O(1) |
| მეზობლების გამეორება | O(ხარისხი) | O(V) |
| საუკეთესო | იშვიათი გრაფები | მკრთალო გრაფები |
მეტი რეალური გრაფი (სოციალური ქსელი, გზების რუკა, დამოკიდებულების გრაფი) იშვიათია, ამიტომ მიმდებარე სიები დიდი მეხსიერებას დაზოგავენ და აჩქარებენ BFS/DFS-ის მსგავს გადაკვეთებს.
ტრეიდ-অఎფ-ის გაცნობამ საშუალებას გაძლევთ აირჩიოთ წარმოდგენა, რომელიც თქვენი გრაფის ალგორითმებს ეფექტურ ინახავს, ვიდრე შემთხვევით O(V²) მეხსიერებას გამოიყენოთ.