Algoritmalar
Algoritmaları şeklen gösteren bir link
burada2.
Depth First Search5. 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.
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 GraphTek 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 GraphDüğü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ğipublic 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;
}
