STL

Coding Session: BFS and DFS

• Graph representation
  • std::vector to represent edge information based on adjacency list.
• Graph traversal
  • std::stack and std::queue for DFS and BFS, respectively.

Example

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

class Graph
{
public:
  int nV, nE;

  vector<int> *edges;

  void Init(const char *_filename)
  {
    FILE *input = fopen(_filename, "r");
    fscanf(input, "%d", &nV);
    fscanf(input, "%d", &nE);
    edges= new vector<int>[nV];
    for(int i=0;i<nE;i++)
    {
        char a, b;
        fscanf(input, " %c %c", &a, &b);
        int x, y;
        x = a-'A';
        y = b-'A';
        edges[x].push_back(y);
    }
    fclose(input);
  }

};

void BFS(Graph &_g, int_stIdx=0)
{
  bool *visit = new bool [_g.nV];
  for(int i=0;i<_g.nV; i++)
  {
    visit[i] = false;
  }

  queue<int> q;
  q.push(_stIdx);
  visit[_stIdx]= true;

  while(!q.empty())
  {
    int x = q.front();
    q.pop();
    printf("%c ", x+'A');

    for(int i=0;i<_g.edges[x].size(); i++)
    {
      if(!visit[_g.edges[x][i]])
      {
        q.push(_g.edges[x][i]);
        visit[_g.edges[x][i]]=true;
      }
    }
  }
  delete [] visit;
}

void DFS(Graph &_g, int _stIndex = 0)
{
bool *visit = new bool [_g.nV];
  /*for(int i=0;i<_g.nV; i++)
  {
    visit[i] = false;*/
    //don't need this part as we already made new bool visited
}

  stack<int> s;
  s.push(_stIdx);
  visit[_stIdx]= true;

  while(!s.empty())
  {
    int x = s.top();
    s.pop();
    printf("%c ", x+'A');

    //To order alphabetically, for(int i=_g.edges[x].size() - 1; i>=0; i--)
    for(int i=0;i<_g.edges[x].size(); i++)
    {
      if(!visit[_g.edges[x][i]])
      {
        s.push(_g.edges[x][i]);
        visit[_g.edges[x][i]]=true;
      }
    }
  }
  delete [] visit;
}

int main(int argc, char **argv)
{
  Graph g;
  g.Init( argv[1] );

  printf("\n");
  printf("BFS: ");
  BFS( g );
  printf("\n");
  printf("\n");

  printf("DFS: ");
  DFS( g );
  printf("\n");


  return 1;
}

source “K-MOOC 허재필 교수님의 <인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고> 강좌의 4-2 그래프 탐색의 STL 활용 구현 중(http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2020_T1)”

back next

Comments

Post comment

Loading...