Deep search implementation

Question

Deep search implementation

Hello. I have a problem with elementary depth-first search.I just started learning graphs and can't implement it. Here is the code itself http://pastebin.com/aT0LREhc Thank you very much in advance.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
using namespace std;
vector <vector<int>> g;       // граф
int n;                        // число вершин

vector<bool> used;

void dfs(int v)
{
    used[v] = true;
    cout << v;
    for (vector<int>::iterator i = g[v].begin(); i != g[v].end(); ++i)
        if (!used[*i])
            dfs(*i);
}

int main()
{
    n = 4;
    int i;
    for (i = 1; i <= n; ++i) {
        dfs(i);
    }    
}

0

c++графы

Author: Nicolas Chabanovsky, 2012-07-25

Source

2 answers

score 1 · Answer 1

According to the code: it would be nice to fill the graph with vertices/edges at the beginning).

And now a little advice: If you want to use graphs, it is better to use excellent library from Boost -- BGL(here is the link to the book), in which depth search is already implemented, as well as in width, path search algorithms and much more!

Well, if you want to implement these algorithms yourself, then, IMHO, it is better to use the normal representation of the graph from BGL, and not this list adjacencies.

P.S. Don't forget about the DRY(Don't Repeat Yourself) principle!

UPD: Here is the example code from dfs.cpp, see the sample output and the code of the main function, IMHO, very succinctly.

#include <boost/config.hpp>
#include <assert.h>
#include <iostream>

#include <vector>
#include <algorithm>
#include <utility>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/visitors.hpp>

/*
  This calculates the discover finishing time.

  Sample Output

  Tree edge: 0 --> 2
  Tree edge: 2 --> 1
  Back edge: 1 --> 1
  Tree edge: 1 --> 3
  Back edge: 3 --> 1
  Tree edge: 3 --> 4
  Back edge: 4 --> 0
  Back edge: 4 --> 1
  Forward or cross edge: 2 --> 3
  1 10
  3 8
  2 9
  4 7
  5 6

 */

using namespace boost;
using namespace std;

template <class VisitorList>
struct edge_categorizer : public dfs_visitor<VisitorList> {
  typedef dfs_visitor<VisitorList> Base;

  edge_categorizer(const VisitorList& v = null_visitor()) : Base(v) { }

  template <class Edge, class Graph>
  void tree_edge(Edge e, Graph& G) {
    cout << "Tree edge: " << source(e, G) <<
      " --> " <<  target(e, G) << endl;
    Base::tree_edge(e, G);
  }
  template <class Edge, class Graph>
  void back_edge(Edge e, Graph& G) {
    cout << "Back edge: " << source(e, G)
         << " --> " <<  target(e, G) << endl;
    Base::back_edge(e, G);
  }
  template <class Edge, class Graph>
  void forward_or_cross_edge(Edge e, Graph& G) {
    cout << "Forward or cross edge: " << source(e, G)
         << " --> " <<  target(e, G) << endl;
    Base::forward_or_cross_edge(e, G);
  }
};
template <class VisitorList>
edge_categorizer<VisitorList>
categorize_edges(const VisitorList& v) {
  return edge_categorizer<VisitorList>(v);
}

int 
main(int , char* [])
{

  using namespace boost;

  typedef adjacency_list<> Graph;

  Graph G(5);
  add_edge(0, 2, G);
  add_edge(1, 1, G);
  add_edge(1, 3, G);
  add_edge(2, 1, G);
  add_edge(2, 3, G);
  add_edge(3, 1, G);
  add_edge(3, 4, G);
  add_edge(4, 0, G);
  add_edge(4, 1, G);

  typedef graph_traits<Graph>::vertex_descriptor Vertex;
  typedef graph_traits<Graph>::vertices_size_type size_type;

  std::vector<size_type> d(num_vertices(G));  
  std::vector<size_type> f(num_vertices(G));
  int t = 0;
  depth_first_search(G, visitor(categorize_edges(
                     make_pair(stamp_times(&d[0], t, on_discover_vertex()),
                               stamp_times(&f[0], t, on_finish_vertex())))));

  std::vector<size_type>::iterator i, j;
  for (i = d.begin(), j = f.begin(); i != d.end(); ++i, ++j)
    cout << *i << " " << *j << endl;

  return 0;
}

score 0 · Answer 2

#include <iostream>
#include <vector>

using namespace std;

vector<bool> was; // вектор, в котором мы храним, были ли мы в вершине
vector<vector<int> > graph; // вектор, в котором мы храним наш граф в виде списка смежности

void dfs( int v){
    if (was[v]){ // если мы были в данной вершине, то уходим из нее
        return;
    }
    was[v] = 1; // говорим что уже были в этой вершине
    for (auto i : graph[v]){ 
        dfs(i); // запускаем новый dfs от каждого соседа
    }
}

int main() {
    int n, m;
    cin >> n >> m; // считываем количество вершин и ребер
    graph.resize(n);
    was.resize(n);
    for (int i = 0; i < n; i++){
        was[i] = 0; // говорим что мы нигде не были
    }

    for (int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--; //Обычно во входных данных вершину нумеруются с единицы
        graph[a].push_back(b); //считываем весь ориентированный граф
    }
    dfs(0); // запускаем дфс от начальной вершины, за которую взяли нулевую
    return 0;
}