(Graph Search) C++ ਵਿੱਚ ਗ੍ਰਾਫ ਖੋਜ ਐਲਗੋਰਿਦਮ- ਵਿਆਖਿਆ, ਉਦਾਹਰਨ ਅਤੇ ਕੋਡ

ਗ੍ਰਾਫ ਖੋਜ ਐਲਗੋਰਿਦਮ ਗ੍ਰਾਫ ਪ੍ਰੋਸੈਸਿੰਗ ਅਤੇ ਜਾਣਕਾਰੀ ਪ੍ਰਾਪਤੀ ਦੇ ਖੇਤਰ ਵਿੱਚ ਇੱਕ ਬੁਨਿਆਦੀ ਤਕਨੀਕ ਹੈ। ਇਹ ਐਲਗੋਰਿਦਮ ਸਾਨੂੰ ਖਾਸ ਨਿਯਮਾਂ ਜਾਂ ਖੋਜ ਐਲਗੋਰਿਦਮ ਦੇ ਆਧਾਰ 'ਤੇ ਗ੍ਰਾਫ ਵਿੱਚ ਮਾਰਗ ਜਾਂ ਭਾਗ ਲੱਭਣ ਦੇ ਯੋਗ ਬਣਾਉਂਦਾ ਹੈ।

ਕਿਦਾ ਚਲਦਾ

1. ਗ੍ਰਾਫ ਵਿੱਚ ਇੱਕ ਖਾਸ ਸਿਰਲੇਖ(ਨੋਡ) ਤੋਂ ਸ਼ੁਰੂ ਕਰੋ।
2. ਖਾਸ ਨਿਯਮਾਂ ਦੇ ਆਧਾਰ 'ਤੇ ਖੋਜ ਪ੍ਰਕਿਰਿਆ ਕਰੋ, ਜਿਵੇਂ ਕਿ ਡੂੰਘਾਈ-ਪਹਿਲੀ ਖੋਜ(DFS) ਜਾਂ ਚੌੜਾਈ-ਪਹਿਲੀ ਖੋਜ(BFS)।
3. ਟੀਚੇ ਜਾਂ ਵਸਤੂਆਂ ਦੀ ਖੋਜ ਕਰਨ ਲਈ ਗ੍ਰਾਫ ਦੇ ਸਿਰਿਆਂ ਅਤੇ ਕਿਨਾਰਿਆਂ ਨੂੰ ਪਾਰ ਕਰੋ।
4. ਮਾਰਗ ਜਾਂ ਖੋਜ ਨਤੀਜਿਆਂ ਨੂੰ ਰਿਕਾਰਡ ਕਰੋ।

ਉਦਾਹਰਨ

ਹੇਠਾਂ ਦਿੱਤੇ ਗ੍ਰਾਫ 'ਤੇ ਗੌਰ ਕਰੋ:

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

ਅਸੀਂ ਡੂੰਘਾਈ-ਪਹਿਲੀ ਖੋਜ(DFS) ਐਲਗੋਰਿਦਮ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋਏ ਇਸ ਗ੍ਰਾਫ ਵਿੱਚ ਵਰਟੇਕਸ A ਤੋਂ ਵਰਟੇਕਸ E ਤੱਕ ਇੱਕ ਮਾਰਗ ਲੱਭਣਾ ਚਾਹੁੰਦੇ ਹਾਂ।

1. ਸਿਖਰ A ਤੋਂ ਸ਼ੁਰੂ ਕਰੋ।
2. ਸਿਰਲੇਖ B 'ਤੇ ਜਾਓ।
3. ਸਿਰਲੇਖ C 'ਤੇ ਜਾਰੀ ਰੱਖੋ।
4. C ਵਿੱਚ ਕੋਈ ਵੀ ਗੁਆਂਢੀ ਨਹੀਂ ਹਨ, ਬੈਕਟ੍ਰੈਕ ਟੂ ਵਰਟੇਕਸ B।
5. ਸਿਰਲੇਖ D 'ਤੇ ਜਾਓ।
6. ਵਰਟੇਕਸ A 'ਤੇ ਜਾਰੀ ਰੱਖੋ(ਜਿਵੇਂ ਕਿ D A ਨਾਲ ਜੁੜਿਆ ਹੋਇਆ ਹੈ)।
7. ਸਿਰਲੇਖ B 'ਤੇ ਜਾਓ।
8. ਸਿਰਲੇਖ C 'ਤੇ ਜਾਓ।
9. ਵਰਟੇਕਸ E 'ਤੇ ਜਾਓ।

A ਤੋਂ E ਤੱਕ ਦਾ ਮਾਰਗ A -> B -> C -> E ਹੈ।

C++ ਵਿੱਚ ਉਦਾਹਰਨ ਕੋਡ

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

ਇਸ ਉਦਾਹਰਨ ਵਿੱਚ, ਅਸੀਂ ਗ੍ਰਾਫ ਵਿੱਚ ਵਰਟੇਕਸ A ਤੋਂ ਵਰਟੇਕਸ E ਤੱਕ ਦਾ ਮਾਰਗ ਲੱਭਣ ਲਈ DFS ਐਲਗੋਰਿਦਮ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਾਂ। ਨਤੀਜਾ A ਤੋਂ E ਤੱਕ ਮਾਰਗ ਬਣਾਉਣ ਵਾਲੇ ਸਿਰਿਆਂ ਦਾ ਇੱਕ ਕ੍ਰਮ ਹੋਵੇਗਾ।