Короткая версия алгоритмов DFS / BFS - PullRequest
Новая
       30

Короткая версия алгоритмов DFS / BFS

0 голосов
/ 14 января 2020

Постоянно сталкиваясь с проблемами олимпиад на графах, я всегда писал довольно длинный код для реализации DFS, и для его отладки требовалось много времени. Я написал такие конструкции: 


class Graph { 
    int V;   
    list<int> *adj;    
public: 
    Graph(int V);  
    void addEdge(int v, int w);  
    void DFS(int s, int f);   

}; 

Graph::Graph(int V) { 
    this->V = V; 
    adj = new list<int>[V]; 
} 

void Graph::addEdge(int v, int w) { 
    adj[v].push_back(w);  
    adj[w].push_back(v);
}

void Graph::DFS(int s,int f) { 
    vector<bool> visited(V, false); 
    stack<int> stack; 
    stack.push(s); 

    while (!stack.empty()) {  
        s = stack.top(); 
        stack.pop(); 

        if (!visited[s]) {
            cout << s << " "; 
            visited[s] = true; 
        } 

        for (list<int>::iterator i = adj[s].begin(); i != adj[s].end(); ++i) 
            if (!visited[*i]) 
                stack.push(*i); 
    }
}

Это было долго и неудобно, особенно при смене языка на другой. Это особенно сложно при написании с нуля. Мне нужен оптимальный подход для реализации DFS / BFS как можно более кратко и элегантно, желательно в форме аккуратного метода, который принимает входные значения в форме (начало, конец).

1 Ответ

0 голосов
/ 14 января 2020 
void addEl(int a, int b,  vector<int> g[]) {
    g[a].push_back(b);
    g[b].push_back(a);
}

void DFS(int s, int f, int n,  vector<int> g[]) {
    vector<bool> vis(n,false);
    stack<int> stk;

    stk.push(s);

    while(!stk.empty()) {
        s = stk.top();
        stk.pop();
        if(!vis[s]) {
            cout << s << endl;
            vis[s] = true;
            if(s==f) return;
        }
        for(int i=0;i<g[s].size();i++) {
            if(!vis[g[s][i]]) stk.push(g[s][i]);
        }
    }
}

Вероятно, это то, что я хотел (но без OOP)

...