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

3. Dijkstra's Shortest Path

4. Cycle Detection

5. Strongly Connected

6. Topological Sorting

7. Graph Coloring

8. Maximum Flow

9. Matching

10. Minimum Spanning Tree

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;
}