Implement the Depth First Search Algorithm in Graph using Simple

  • 时间:2020-09-19 10:45:07
  • 分类:网络文摘
  • 阅读:142 次

Given a graph represented by G(V, E) where V is the vertices and E represents the edges, we can do a Depth First Search Algorithm (DFS) on any node/vertex. The DFS will mark the current node visited and visit the node using using the (*visit) function (C++ function pointer), and recursively call itself with the connected edges.

1
2
3
4
5
6
7
8
9
10
void traverseDepthFirstSearch(int node, void(*visit)(int)) {
  link t;
  (*visit)(k);
  visited[k] = 1; // mark the node as visited
  for (t = adj[k]; t != NULL; t = t->next) {
     if (!visited[t->v]) { // avoid cycle
         traverseDepthFirstSearch(t->v, visit);
     }
  }
}
void traverseDepthFirstSearch(int node, void(*visit)(int)) {
  link t;
  (*visit)(k);
  visited[k] = 1; // mark the node as visited
  for (t = adj[k]; t != NULL; t = t->next) {
     if (!visited[t->v]) { // avoid cycle
         traverseDepthFirstSearch(t->v, visit);
     }
  }
}
three-nodes Implement the Depth First Search Algorithm in Graph using Simple C/C++ algorithms c / c++ DFS graph

three-nodes

The algorithimic complexity is O(N) where N is the number of nodes connected to the given vertex. The space complexity is also O(N).

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
如何为小型企业定制SEO  内容页关键词布局优化解析  网站SEO优化基本的四项规则  内容页关键词布局优化解析  中小企业需求在改变:SEO从业者需要顺应潮流  深度解析搜索引擎蜘蛛工作的原理  外贸网站建设不要忽视这6个网站设计操作  百度不再支持sitemapXML地图文档  站群推广的优点,SEO站群爆炸流量  谷歌外链用自动化工具发,真的靠谱吗 
评论列表
添加评论