君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
BFS++培训材料
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口数据结构----BFS和DFS详解 - CSDN博客
数据结构----BFS和DFS详解
The art of teaching is the art of assisting discovery.
Name:Willam
这篇博客将会介绍两种遍历图的算法，一种是：DFS—-深度优先搜索，另外一种就是：BFS–广度优先搜索。
1、DFS （深度优先搜索）
算法思路：
从顶点V开始，访问这个顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径的相通的顶点都被访问了，如果此时还有顶点未被访问，则选择图中未被访问的那个顶点作为起点，重复上述动作。
具体的代码实现如下：
#include&iostream&
#include&string&
using namespace std;
struct Graph_array {
void createGraph_by_array(int **edge,Graph_array & g) {
int i = 0;
g.arc = new int*[g.vexnum];
for (i = 0; i & g. i++)
g.arc[i] = new int[g.vexnum];
for (int j = 0; j & g. j++)
g.arc[i][j] = 0;
for (i = 0; i & g. i++)
g.arc[edge[i][0] - 1][edge[i][1] - 1] = 1;
void print_array(Graph_array g) {
int i = 0;
for (i = 0; i &g. i++) {
for (int j = 0; j & g. j++) {
cout && g.arc[i][j] && " ";
void DFS_store_array(Graph_array g,int v,bool * & visit) {
cout && g.infromation[v] && " ";
visit[v] = true;
for (int i = 0; i & g. i++) {
if (g.arc[v][i] == 0 || g.arc[v][i] == INT_MAX) {
else if (!visit[i]) {
DFS_store_array(g, i, visit);
void DFS_array_travel(Graph_array g,int begin) {
visit = new bool[g.vexnum];
for (i = 0; i & g. i++) {
visit[i] = false;
cout && "图的DFS遍历结果：" &&
DFS_store_array(g,begin - 1,visit);
for (i = 0; i & g. i++) {
if (!visit[i])
DFS_store_array(g, i,visit);
struct ArcNode {
struct Vnode {
struct Graph_List {
void createGraph_list(Graph_List & g, int **edge) {
for (i = 0; i & g. i++)
ArcNode * next=new ArcN
next-&adfvex=edge[i][1]-1;
next-&next = NULL;
if (g.node[edge[i][0]-1].firstarc == NULL) {
g.node[edge[i][0]-1].firstarc =
now = g.node[edge[i][0]-1].
while (now-&next) {
now = now-&
now-&next =
void print_list(Graph_List g) {
for (i = 0; i & g. i++) {
cout && g.node[i].data && " ";
now = g.node[i].
while (now) {
cout && now-&adfvex && " ";
now = now-&
void DFS_store_list(Graph_List g, int v, bool * & visit) {
cout && g.node[v].data && " ";
visit[v] = true;
ArcNode * next = g.node[v].
while (next) {
if (!visit[next-&adfvex]) {
DFS_store_list(g, next-&adfvex, visit);
next = next-&
void DFS_list(Graph_List g, int begin) {
bool * visit = new bool[g.vexnum];
for (i = 0; i & g. i++) {
visit[i] = false;
cout && "图的DFS遍历结果：" &&
DFS_store_list(g, begin - 1, visit);
for (i = 0; i & g. i++) {
if(!visit[i])
DFS_store_list(g, i, visit);
int main()
Graph_List G;
cout && "输入图的种类：" &&
cin && g. G.kind = g.
cout && "输入图的顶点个数" &&
cin && g. G.vexnum = g.
cout && "输入图的边的个数（输入时注意，无向图的边要比看的边乘以2，然后输入的记得把重复的边也要输进去）" &&
cin && g. G.edge = g.
g.infromation = new string[g.vexnum];
G.node = new Vnode[G.vexnum];
cout && "输入每个顶点信息（如名称）:" &&
for (i = 0; i & g. i++) {
cin && g.infromation[i];
G.node[i].data = g.infromation[i];
G.node[i].firstarc = NULL;
int ** edge_
edge_information = new int*[g.edge];
cout && "输入每条边两个顶点的编号：" &&
for (i = 0; i & g. i++)
edge_information[i] = new int[2];
cin && edge_information[i][0];
cin && edge_information[i][1];
createGraph_by_array(edge_information,g);
cout && "图的邻接矩阵为：" &&
print_array(g);
DFS_array_travel(g, 1);
createGraph_list(G, edge_information);
cout && "图的邻接表为：" &&
print_list(G);
DFS_list(G, 1);
system("pause");
下面，我们对如下这个图进行遍历，
使用上述程序，输出的结果为：
（输入时注意，无向图的边要比看的边乘以2，然后输入的记得把重复的边也要输进去）
（广度优先搜索）
BFS就是我们所说的广度优先搜索，它的思路就是：假设从图中的顶点V出，在访问了v之后，依次访问v的各个未被访问的邻接点，然后，分别从这些邻接点出发，依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的邻接点”先被访问，直至图中所有的顶点都被访问到为止，防止出现非连通图的情况，我们需要最后遍历一遍，看是否所有的点都被访问了，如果有未被访问的点，那么就把该点作为一个新的起点。
代码实现如下：
#include&iostream&
#include&string&
#include&queue&
using namespace std;
struct Graph_array {
void createGraph_by_array(int **edge, Graph_array & g) {
int i = 0;
g.arc = new int*[g.vexnum];
for (i = 0; i & g. i++)
g.arc[i] = new int[g.vexnum];
for (int j = 0; j & g. j++)
g.arc[i][j] = 0;
for (i = 0; i & g. i++)
g.arc[edge[i][0] - 1][edge[i][1] - 1] = 1;
void print_array(Graph_array g) {
int i = 0;
for (i = 0; i &g. i++) {
for (int j = 0; j & g. j++) {
cout && g.arc[i][j] && " ";
void BFS_array_travel(Graph_array g, int begin) {
visit = new bool[g.vexnum];
for (i = 0; i & g. i++) {
visit[i] = false;
cout && "图的BFS遍历结果：" &&
queue&int&
for (int v = 0; v & g. v++) {
if (!visit[(begin-1 + v) % g.vexnum])
cout && g.infromation[(begin - 1 + v) % g.vexnum] && " ";
visit[(begin - 1 + v) % g.vexnum] = true;
q.push((begin - 1 + v) % g.vexnum);
while (!q.empty())
int u = q.front();
for (int j = 0; j & g. j++) {
if (g.arc[u][j] == 0 || g.arc[u][j] == INT_MAX) {
else if (!visit[j] ) {
cout && g.infromation[j] && " ";
visit[j] = true;
q.push(j);
cout && "完成" &&
struct ArcNode {
struct Vnode {
struct Graph_List {
void createGraph_list(Graph_List & g, int **edge) {
for (i = 0; i & g. i++)
ArcNode * next = new ArcN
next-&adfvex = edge[i][1] - 1;
next-&next = NULL;
if (g.node[edge[i][0] - 1].firstarc == NULL) {
g.node[edge[i][0] - 1].firstarc =
now = g.node[edge[i][0] - 1].
while (now-&next) {
now = now-&
now-&next =
void print_list(Graph_List g) {
for (i = 0; i & g. i++) {
cout && g.node[i].data && " ";
now = g.node[i].
while (now) {
cout && now-&adfvex && " ";
now = now-&
void BFS_list(Graph_List g, int begin) {
bool * visit = new bool[g.vexnum];
for (i = 0; i & g. i++) {
visit[i] = false;
cout && "图的BFS遍历结果：" &&
queue&int&
for (int v = 0; v & g. v++) {
if (!visit[(begin - 1 + v) % g.vexnum])
cout && g.node[(begin - 1 + v) % g.vexnum].data && " ";
visit[(begin - 1 + v) % g.vexnum] = true;
q.push((begin - 1 + v) % g.vexnum);
while (!q.empty())
int u = q.front();
next = g.node[u].
while (next) {
if (!visit[next-&adfvex]) {
cout && g.node[next-&adfvex].data && " ";
visit[next-&adfvex] = true;
q.push(next-&adfvex);
next = next-&
int main()
Graph_List G;
cout && "输入图的种类：" &&
cin && g. G.kind = g.
cout && "输入图的顶点个数" &&
cin && g. G.vexnum = g.
cout && "输入图的边的个数" &&
cin && g. G.edge = g.
g.infromation = new string[g.vexnum];
G.node = new Vnode[G.vexnum];
cout && "输入每个顶点信息（如名称）:" &&
for (i = 0; i & g. i++) {
cin && g.infromation[i];
G.node[i].data = g.infromation[i];
G.node[i].firstarc = NULL;
int ** edge_
edge_information = new int*[g.edge];
cout && "输入每条边两个顶点的编号：" &&
for (i = 0; i & g. i++)
edge_information[i] = new int[2];
cin && edge_information[i][0];
cin && edge_information[i][1];
createGraph_by_array(edge_information, g);
cout && "图的邻接矩阵为：" &&
print_array(g);
BFS_array_travel(g, 1);
createGraph_list(G, edge_information);
cout && "图的邻接表为：" &&
print_list(G);
BFS_list(G, 1);
system("pause");
同样是对DFS遍历的那个图进行遍历，结果如下：
上述我们采用两种方式对图进行的了遍历包括了两种表达方式：邻接表和邻接矩阵，首先我们看遍历的方法上的选择，其实这两种遍历算法的时间复杂度是一样的，它们的不同就是在于遍历顶点的顺序不同，另外，对于两种图的不同的表示方式，我们可以发现邻接矩阵的表示下，图遍历的时间复杂度为：o（n*n），而在邻接表的下，遍历的时间复杂度只是：O(n+e),其中n为顶点个数，e为边的条数，所以，在实际中需要进行图的遍历的情况下，我们最好是采用邻接表的方式进行表示我们的图。
本文已收录于以下专栏：
相关文章推荐
本文主要包括以下内容
邻接矩阵实现无向图的BFS与DFS
邻接表实现无向图的BFS与DFS
理论介绍深度优先搜索介绍图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似...
写在最前的三点：
1、所谓图的遍历就是按照某种次序访问图的每一顶点一次仅且一次。
2、实现bfs和dfs都需要解决的一个问题就是如何存储图。一般有两种方法：邻接矩阵和邻接表。这里为简单起
深度优先搜索(DFS)
【算法入门】
深度优先搜索（缩写DFS）有点类似广度优先搜索，也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发...
思想：一直往深处走，直到找到解或者走不下去为止
DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。...
本文的重点在于图的深度优先搜索（DFS）和广度优先搜索（BFS），因此不再对图的基本概念做过多的介绍，但是要先大致了解下图的几种常见的存储结构。
邻接矩阵既可以用来存储无向图，也可以用来存储有...
在做pat的时候，用dfs写了一道题的解超时，看别人的解法时，发现别人用了Dijkstra算法，瞬间自己就混乱了，因为之前也看过Dijkstra，bfs算法，但是当时居然都傻傻分不清楚了，所以决定写一...
题目地址/problems/longest-increasing-path-in-a-matrix/题目描述Given an integer matrix, f...
最近为了保研在复习数据结构和算法，想来可以用博客记录一些，以后或许能用的上。首先说一下图的定义。
图是一种数据结构，图和树一样可以用二元组表示。它可定义为Graph=(V,R)其中，V＝{x|x∈...
从这几天通过啊哈算法，遇到的搜索中，大致总结出这几点规律：
对于DFS：可有第一个点先确定的，做一下标记，以第一个为基础进行搜索；也可有从第一个点就没确定的，先去找第一个点，如1,2,3的全排列
LeetCode 里面很大一部分题目都是属于这个范围，例如Path Sum用的就是递归+DFS，Path Sum2用的是递归+DFS+回溯
这里参考了一些网上写得很不错的文章，总结一下理解与模板
他的最新文章
讲师：何宇健
讲师：董岩
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)博客分类：
社交网络中的图模型经常需要构造一棵树型结构：从一个特定的节点出发，例如，构造mary的朋友以及mary朋友的朋友的一棵树。
为构造这样的一棵树，最简单的方法是使用广度优先算法：
经常使用链表来表示图的节点以及节点之间的链接关系，如
frank -& {mary, jill}
jill -& {frank, bob, james}
mary -& {william, joe, erin}
表示，mary有3个朋友，分别是william，joe和erin
将上述关系形式化表示为
0-& {1, 2}
2-& {3, 4, 5}
1-& {6, 7, 8}
有了上述链表结构，我们可以得到：
单线程的BFS如下：
1、节点对象建模Node.java
import java.util.*;
public class Node {
public static enum Color {
WHITE, GRAY, BLACK
private int parent = Integer.MAX_VALUE;
private int distance = Integer.MAX_VALUE;
private List&Integer& edges =
private Color color = Color.WHITE;
public Node(int id) {
public int getId() {
return this.
public int getParent() {
return this.
public void setParent(int parent) {
this.parent =
public int getDistance() {
return this.
public void setDistance(int distance) {
this.distance =
public Color getColor() {
return this.
public void setColor(Color color) {
this.color =
public List&Integer& getEdges() {
return this.
public void setEdges(List&Integer& vertices) {
this.edges =
2、BFS算法 Graph.java
import java.util.*;
public class Graph {
private Map&Integer, Node&
public Graph() {
this.nodes = new HashMap&Integer, Node&();
public void breadthFirstSearch(int source) {
// Set the initial conditions for the source node
Node snode = nodes.get(source);
snode.setColor(Node.Color.GRAY);
snode.setDistance(0);
Queue&Integer& q = new LinkedList&Integer&();
q.add(source);
while (!q.isEmpty()) {
Node unode = nodes.get(q.poll());
for (int v : unode.getEdges()) {
Node vnode = nodes.get(v);
if (vnode.getColor() == Node.Color.WHITE) {
vnode.setColor(Node.Color.GRAY);
vnode.setDistance(unode.getDistance() + 1);
vnode.setParent(unode.getId());
unode.setColor(Node.Color.BLACK);
public void addNode(int id, int[] edges) {
// A couple lines of hacky code to transform our
// input integer arrays (which are most comprehensible
// write out in our main method) into List&Integer&
List&Integer& list = new ArrayList&Integer&();
for (int edge : edges)
list.add(edge);
Node node = new Node(id);
node.setEdges(list);
nodes.put(id, node);
public void print() {
for (int v : nodes.keySet()) {
Node vnode = nodes.get(v);
System.out.printf("v = %2d parent = %2d distance = %2d \n", vnode.getId(), vnode.getParent(),
vnode.getDistance());
public static void main(String[] args) {
Graph graph = new Graph();
graph.addNode(1, new int[] { 2, 5 });
graph.addNode(2, new int[] { 1, 5, 3, 4 });
graph.addNode(3, new int[] { 2, 4 });
graph.addNode(4, new int[] { 2, 5, 3 });
graph.addNode(5, new int[] { 4, 1, 2 });
graph.breadthFirstSearch(1);
graph.print();
但是以上BFS单线程构造树形结构对于大数据的时候，显得苍白无力。
对此，下面提出基于MapReduce的BFS并行构造社交网络中的树图算法
使用MapReduce计算图模型，基本思想是在每个Map slot的迭代中“makes a mess” 而在 Reduce slot中“cleans up the mess”
假设，我们用如下方式表示一个节点：
EDGES|DISTANCE_FROM_SOURCE|COLOR|
其中，EDGES是一个用“，”隔开的链接到本节点的其他节点链表List，对于我们不知道链表中的节点到本节点的距离，
使用Integer.MAX_VALUE表示"unknown"。
从COLOR，我们可以知道本节点我们计算过没有，WHITE表示计算过。
假设，我们的输入数据如下，我们从节点1开始广度优先搜索，因此，初始时，标记节点1的距离为0，color为GRAY
2,5|0|GRAY|
1,3,4,5|Integer.MAX_VALUE|WHITE|
2,4|Integer.MAX_VALUE|WHITE|
2,3,5|Integer.MAX_VALUE|WHITE|
1,2,4|Integer.MAX_VALUE|WHITE|
map slot负责找出所有COLOR为GEAY的节点。而，对于每个我们计算过的节点，即COLOR为GRAY的节点，对应地，map slot的输出为一个COLOR为BLACK的节点，其中的DISTANCE = DISTANCE + 1。同时，map slot也输出所有不是GEAY的节点，其中距离不变。
因此，上述输入的输出形式如下：
2,5|0|BLACK|
NULL|1|GRAY|
NULL|1|GRAY|
1,3,4,5|Integer.MAX_VALUE|WHITE|
2,4|Integer.MAX_VALUE|WHITE|
2,3,5|Integer.MAX_VALUE|WHITE|
1,2,4|Integer.MAX_VALUE|WHITE|
在reduce slot获取的数据都具有同一个key。例如，获取key=2的reduce slot的对应values值为：
NULL|1|GRAY|
1,3,4,5|Integer.MAX_VALUE|WHITE|
reduce slot的任务是从获取到的数据，经过采用：
1、有邻接节点的节点
2、所有有邻接节点的节点中的最小距离
3、所有有邻接节点中颜色最深的节点
构造出新的输出，如，经过第一次MapReduce过程，我们得到如下形式的数据：
2,5,|0|BLACK
1,3,4,5,|1|GRAY
2,4,|Integer.MAX_VALUE|WHITE
2,3,5,|Integer.MAX_VALUE|WHITE
1,2,4,|1|GRAY
第二次MapReduce过程，采用上述输出作为输入，以相同的逻辑运算，得到如下结果：
2,5,|0|BLACK
1,3,4,5,|1|BLACK
2,4,|2|GRAY
2,3,5,|2|GRAY
1,2,4,|1|BLACK
第三次的输出为：
2,5,|0|BLACK
1,3,4,5,|1|BLACK
2,4,|2|BLACK
2,3,5,|2|BLACK
1,2,4,|1|BLACK
MapReduce迭代过程直到所有节点不为GRAY为止。
而如果有节点没有连接到源节点，那么可能迭代过程每次都有COLOR为WHITE的节点。
MapReduce的代码如下：
1、节点对象建模:Node.java
package org.apache.hadoop.
import java.util.*;
import org.apache.hadoop.io.T
public class Node {
public static enum Color {
WHITE, GRAY, BLACK
private List&Integer& edges = new ArrayList&Integer&();
private Color color = Color.WHITE;
public Node(String str) {
String[] map = str.split("\t");
String key = map[0];
String value = map[1];
String[] tokens = value.split("\\|");
this.id = Integer.parseInt(key);
for (String s : tokens[0].split(",")) {
if (s.length() & 0) {
edges.add(Integer.parseInt(s));
if (tokens[1].equals("Integer.MAX_VALUE")) {
this.distance = Integer.MAX_VALUE;
this.distance = Integer.parseInt(tokens[1]);
this.color = Color.valueOf(tokens[2]);
public Node(int id) {
public int getId() {
return this.
public int getDistance() {
return this.
public void setDistance(int distance) {
this.distance =
public Color getColor() {
return this.
public void setColor(Color color) {
this.color =
public List&Integer& getEdges() {
return this.
public void setEdges(List&Integer& edges) {
this.edges =
public Text getLine() {
StringBuffer s = new StringBuffer();
for (int v : edges) {
s.append(v).append(",");
s.append("|");
if (this.distance & Integer.MAX_VALUE) {
s.append(this.distance).append("|");
s.append("Integer.MAX_VALUE").append("|");
s.append(color.toString());
return new Text(s.toString());
2、MapRecue广度优先搜索:
package org.apache.hadoop.
import java.io.IOE
import java.util.I
import java.util.L
import mons.logging.L
import mons.logging.LogF
import org.apache.hadoop.conf.C
import org.apache.hadoop.conf.C
import org.apache.hadoop.fs.P
import org.apache.hadoop.io.IntW
import org.apache.hadoop.io.LongW
import org.apache.hadoop.io.T
import org.apache.hadoop.mapred.*;
import org.apache.hadoop.util.T
import org.apache.hadoop.util.ToolR
* This is an example Hadoop Map/Reduce application.
* It inputs a map in adjacency list format, and performs a breadth-first search.
* The input format is
EDGES|DISTANCE|COLOR
* ID = the unique identifier for a node (assumed to be an int here)
* EDGES = the list of edges emanating from the node (e.g. 3,8,9,12)
* DISTANCE = the to be determined distance of the node from the source
* COLOR = a simple status tracking field to keep track of when we're finished with a node
* It assumes that the source node (the node from which to start the search) has
* been marked with distance 0 and color GRAY in the original input.
* nodes will have input distance Integer.MAX_VALUE and color WHITE.
public class GraphSearch extends Configured implements Tool {
public static final Log LOG = LogFactory.getLog("org.apache.hadoop.examples.GraphSearch");
* Nodes that are Color.WHITE or Color.BLACK are emitted, as is. For every
* edge of a Color.GRAY node, we emit a new Node with distance incremented by
* one. The Color.GRAY node is then colored black and is also emitted.
public static class MapClass extends MapReduceBase implements
Mapper&LongWritable, Text, IntWritable, Text& {
public void map(LongWritable key, Text value, OutputCollector&IntWritable, Text& output,
Reporter reporter) throws IOException {
Node node = new Node(value.toString());
// For each GRAY node, emit each of the edges as a new node (also GRAY)
if (node.getColor() == Node.Color.GRAY) {
for (int v : node.getEdges()) {
Node vnode = new Node(v);
vnode.setDistance(node.getDistance() + 1);
vnode.setColor(Node.Color.GRAY);
output.collect(new IntWritable(vnode.getId()), vnode.getLine());
// We're done with this node now, color it BLACK
node.setColor(Node.Color.BLACK);
// No matter what, we emit the input node
// If the node came into this method GRAY, it will be output as BLACK
output.collect(new IntWritable(node.getId()), node.getLine());
* A reducer class that just emits the sum of the input values.
public static class Reduce extends MapReduceBase implements
Reducer&IntWritable, Text, IntWritable, Text& {
* Make a new node which combines all information for this single node id.
* The new node should have
* - The full list of edges
* - The minimum distance
* - The darkest Color
public void reduce(IntWritable key, Iterator&Text& values,
OutputCollector&IntWritable, Text& output, Reporter reporter) throws IOException {
List&Integer& edges =
int distance = Integer.MAX_VALUE;
Node.Color color = Node.Color.WHITE;
while (values.hasNext()) {
Text value = values.next();
Node u = new Node(key.get() + "\t" + value.toString());
// One (and only one) copy of the node will be the fully expanded
// version, which includes the edges
if (u.getEdges().size() & 0) {
edges = u.getEdges();
// Save the minimum distance
if (u.getDistance() & distance) {
distance = u.getDistance();
// Save the darkest color
if (u.getColor().ordinal() & color.ordinal()) {
color = u.getColor();
Node n = new Node(key.get());
n.setDistance(distance);
n.setEdges(edges);
n.setColor(color);
output.collect(key, new Text(n.getLine()));
static int printUsage() {
System.out.println("graphsearch [-m &num mappers&] [-r &num reducers&]");
ToolRunner.printGenericCommandUsage(System.out);
return -1;
private JobConf getJobConf(String[] args) {
JobConf conf = new JobConf(getConf(), GraphSearch.class);
conf.setJobName("graphsearch");
// the keys are the unique identifiers for a Node (ints in this case).
conf.setOutputKeyClass(IntWritable.class);
// the values are the string representation of a Node
conf.setOutputValueClass(Text.class);
conf.setMapperClass(MapClass.class);
conf.setReducerClass(Reduce.class);
for (int i = 0; i & args. ++i) {
if ("-m".equals(args[i])) {
conf.setNumMapTasks(Integer.parseInt(args[++i]));
} else if ("-r".equals(args[i])) {
conf.setNumReduceTasks(Integer.parseInt(args[++i]));
* The main driver for word count map/reduce program. Invoke this method to
* submit the map/reduce job.
* @throws IOException
When there is communication problems with the job tracker.
public int run(String[] args) throws Exception {
int iterationCount = 0;
while (keepGoing(iterationCount)) {
if (iterationCount == 0)
input = "input-graph";
input = "output-graph-" + iterationC
String output = "output-graph-" + (iterationCount + 1);
JobConf conf = getJobConf(args);
FileInputFormat.setInputPaths(conf, new Path(input));
FileOutputFormat.setOutputPath(conf, new Path(output));
RunningJob job = JobClient.runJob(conf);
iterationCount++;
private boolean keepGoing(int iterationCount) {
if(iterationCount &= 4) {
public static void main(String[] args) throws Exception {
int res = ToolRunner.run(new Configuration(), new GraphSearch(), args);
System.exit(res);
breadth-first graph search using an iterative map-reduce algorithm
浏览: 349728 次
来自: 济南
楼主你好，问个问题，为什么我写的如下的：JobConf pha ...
Molisa 写道mapred.min.split.size指 ...
mapred.min.split.size指的是block数， ...
请问导入之后，那些错误怎么解决？
看了你的文章深受启发，想请教你几个问题我的数据都放到hbase ...
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'}