27 Kasım 2023 Pazartesi

Graph Algoritmaları

Algoritmalar
Algoritmaları şeklen gösteren bir link burada
1. Breadth First Search. LeetCode Breadth First Search yazısına bakabilirsiniz
2. Depth First Search
5. Strongly Connected
7. Graph Coloring
8. Maximum Flow
9. Matching
11. B+ Tree
Tam olarak Graph Veri Yapısı sayılmasa da not almak istedim. Temel kural şöyle.
Root hariç her düğümde 3 pointer ve en az 1 leaf node olmalı.
Graph Nerede Kullanılır
1. Optimization Problems
Açıklaması şöyle.
Algorithms like Dijkstra's enable your navigation system / GPS to decide which roads you should drive on to reach a destination.

The Hungarian Algorithm can assign each Uber car to people looking for a ride (an assignment problem)

Chess, Checkers, Go and Tic-Tac-Toe are formulated as a game tree (a degenerate graph) and can be "solved" using brute-force depth or breadth first search, or using heuristics with minimax or A*

Flow networks and algorithms like maximum flow can be used in modelling utilities networks (water, gas, electricity), roads, flight scheduling, supply chains.
2. Specialized types of graphs
Açıklaması şöyle.
Bayesian networks were used by NASA to select an operating system for the space shuttle

Neural networks are used in language translation, image synthesis (such as fake face generation), color recovery of black-and-white images, speech synthesis
Graph İçin Temel Bilgiler
1. Düğüm
Vertex veya node olarak adlandırılır.

2. Directed Graph
Tek yönlüdür. Şöyledir.
A —> B —> <— C 
     |
     v
     E <— F —> D —> G

X -> <- Y

node : neighbors
  A  :  [B]
  B  :  [C, E]
  C  :  [B]
  D  :  [G]
  E  :  []
  F  :  [E, D]
  G  :  []
  X  :  [Y]
  Y  :  [X]

3. Undirected Graph
Düğümler arasında yön bilgisi yoktur. Çizgiler için genellikle bir ağırlık verilir.
A--5--B
|   /
2  3
| /
 C
4. Graph İçin Kullanılan Temel Veri Yapıları
Sparse olan graph'lar için adjacency list - komşuluk listesi - kullanılır. Dolu olan graph'larda ise adjaceny matrix kullanılır. Adjaceny list şuna benzer.
* 1   -> 2   4
* 2   -> 3   1
* 3   -> 2   4
* 4   -> 3   1
Düğümün komşularını saklamak için vector, list, hashmap gibi herhangi bir veri yapısı kullanılabilir. Basit bir Java örneği
public class SimpleAdjacencyList {
    private Map<Integer, List<Vertex>> adjacencyList = new HashMap<>();
}
Yukarıdaki kodda Map Value değeri için şöyle bir sınıf tanımlamak daha iyi olabilir.
public class DirectedGraphNode {
    String val;
    List<DirectedGraphNode> neighbors;
}

Hiç yorum yok:

Yorum Gönder