close

C++'da Grafik Arama (Graph Search) Algoritması- Açıklama, Örnek ve Kod

Grafik Arama algoritması, grafik işleme ve bilgi alma alanında temel bir tekniktir. Bu algoritma, belirli kurallara veya arama algoritmalarına dayalı olarak bir grafikteki yolları veya bileşenleri bulmamızı sağlar.

Nasıl çalışır

  1. Grafikteki belirli bir tepe noktasından(düğüm) başlayın.
  2. Derinlik Öncelikli Arama(DFS) veya Önce Genişlik Arama(BFS) gibi belirli kurallara göre arama işlemini gerçekleştirin.
  3. Bulunacak hedefi veya nesneleri aramak için grafiğin köşelerini ve kenarlarını dolaşın.
  4. Yolu veya arama sonuçlarını kaydedin.

Örnek

Aşağıdaki grafiği göz önünde bulundurun:

A -- B -- C -- E  
|      |  
D --------

Derinlik Öncelikli Arama(DFS) algoritmasını kullanarak bu grafikte A köşesinden E köşesine giden bir yol bulmak istiyoruz.

  1. A köşesinden başlayın.
  2. B köşesine gidin.
  3. C köşesine devam edin.
  4. C'de komşu yok, köşe B'ye geri dönün.
  5. D köşesine gidin.
  6. A köşesine devam edin(D, A'ya bağlı olduğundan).
  7. B köşesine gidin.
  8. C köşesine git.
  9. E köşesine git.

A'dan E'ye giden yol A -> B -> C -> E'dir.

C++'da Örnek Kod 

#include <iostream>  
#include <vector>  
#include <stack>  
#include <unordered_map>  
  
class Graph {  
public:  
    void addEdge(char from, char to);  
    std::vector<char> depthFirstSearch(char start, char end);  
  
private:  
    std::unordered_map<char, std::vector<char>> adjList;  
};  
  
void Graph::addEdge(char from, char to) {  
    adjList[from].push_back(to);  
    adjList[to].push_back(from);  
}  
  
std::vector<char> Graph::depthFirstSearch(char start, char end) {  
    std::vector<char> path;  
    std::unordered_map<char, char> parent;  
    std::stack<char> stack;  
  
    stack.push(start);  
    parent[start] = '\0';  
  
    while(!stack.empty()) {  
        char current = stack.top();  
        stack.pop();  
  
        if(current == end) {  
            // Build the path from end to start using the parent map  
            char node = end;  
            while(node != '\0') {  
                path.insert(path.begin(), node);  
                node = parent[node];  
            }  
            break;  
        }  
  
        for(char neighbor: adjList[current]) {  
            if(parent.find(neighbor) == parent.end()) {  
                parent[neighbor] = current;  
                stack.push(neighbor);  
            }  
        }  
    }  
  
    return path;  
}  
  
int main() {  
    Graph graph;  
    graph.addEdge('A', 'B');  
    graph.addEdge('A', 'D');  
    graph.addEdge('B', 'C');  
    graph.addEdge('C', 'E');  
    graph.addEdge('D', 'B');  
  
    char start = 'A';  
    char end = 'E';  
  
    std::vector<char> path = graph.depthFirstSearch(start, end);  
  
    std::cout << "Path from " << start << " to " << end << ": ";  
    for(char node: path) {  
        std::cout << node << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

Bu örnekte, grafikte A köşesinden E köşesine bir yol bulmak için DFS algoritmasını kullanıyoruz. Sonuç, A'dan E'ye giden yolu oluşturan bir dizi köşe olacaktır.