1. Graph Veri Yapıları Nedir?
Bilgisayar dünyasında bulunan ve gerçek hayatta çeşitli sebeplerle karşılaşılan yapıları temsil amacıyla kullanılan şekillerdir.
- Grafta bulunan varlıklar düğümler ile ifade edilmekte, bu varlıklar arasındaki ilişkiler ise graftaki bağlantılar ile ifade edilmektedir.
- Bağlantılara sayısal ağırlıklar ve yönler atanabilir. (directed or undirected)
- En kısa path için Dijkstra Algoritması kullanılır.
2.Graph Veri Yapısı Türleri
2.1. Undirected & Directed Graphs
Kenarlar arasındaki bağlantının nereden başlayıp nerede sonlandığını belirten yön bilgisi işimize yarayacaksa yönlü graph tercih edilir.
2.2. Weighted & Unweighted Graphs
Ağırlıklı graphlara kullanım örneği olarak ,şehirler arasındaki uzaklık veya routerler arası bant genişliği verilebilir.
3. Graph Veri Yapıları Nerede Kullanılır?
Kullanıcıların beğenisine dayalı sistemi oluşturmak için kullanılır. Bu özelliğiyle öneri motorlarını modellerken ve sosyal ağlardaki bağlantılarda kullanılmaktadır. Örneğin Youtube size bir video önerdiğinde, arka planda graphları kullanmaktadır.
Adjacency Matrices & Adjacency List
Kodlama kısmına geçmeden önce bahsetmek isteğim son konuya geçelim. Adjacency matrix NxN boolean matristir. Düğümler arasındaki ilişki bu matris kullanılarak temsil edilir.
Adjacency list ise graph’ı temsil etmenin en yaygın yoludur. Bir anahtar-değer çifti veri yapısını saklamak için bir hash tablosu kullanabiliriz. Adjacency list hafızada yer kaplama açısından daha optimaldir.
Hash tablosunu oluşturursak;
Şimdi farklı bir graph’ta işlemlerimizi yapalım
Undirected ve ağırlıkları olan bir graph. Ağırlıklarını şimdilik kullanmayacağız. Önce graph’ı tanımlayalım:
graph= {
'A':["D","C"],
'B':["C","F"],
'C':["A","B","D","E"],
'D':["A","C","G"],
'E':["C","F"],
'F':["B","E","G"],
'G':["D","F"]
}Bir düğümden diğerine tüm olası yolları oluşturalım:
# function to generate all possible paths
def find_all_paths(graph, start, end, path =[]):
path = path + [start]
if start == end:
return [path]
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
# Driver function call to print all
# generated paths
print(find_all_paths(graph, "F", "C"))Output:
[['F', 'B', 'C'], ['F', 'E', 'C'], ['F', 'G', 'D', 'A', 'C'], ['F', 'G', 'D', 'C']]En kısa yolu bulma:(Atılacak adım sayısı dikkate alınarak)
# function to find the shortest path
def find_shortest_path(graph, start, end, path =[]):
path = path + [start]
if start == end:
return path
shortest = None
for node in graph[start]:
if node not in path:
newpath = find_shortest_path(graph, node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortestprint(find_shortest_path(graph, 'F', 'C'))
Output:
['F', 'B', 'C']
