dfsbfs算法

❶ 基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）

        深度优先搜索和广度优先搜索，都是图形搜索算法，它两相似，又却不同，在应用上也被用到不同的地方。这里拿一起讨论，方便比较。

一、深度优先搜索

        深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

基本步奏

（1）对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。

（2）从stack中访问栈顶的点；

（3）找出与此点邻接的且尚未遍历的点，进行标记，然后放入stack中，依次进行；

（4）如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照（3）依次进行；

（5）直到遍历完整个树，stack里的元素都将弹出，最后栈为空，DFS遍历完成。

二、广度优先搜索

        广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。

基本步奏

（1）给出一连通图，如图，初始化全是白色（未访问）；

（2）搜索起点V1（灰色）；

（3）已搜索V1（黑色），即将搜索V2，V3，V4（标灰）；

（4）对V2，V3，V4重复以上操作；

（5）直到终点V7被染灰，终止；

（6）最短路径为V1，V4，V7.

❷ 数据结构C语言版 图的遍历 DFS和BFS算法，用邻接矩阵储存 急阿在线等 求大神指点

#include <iostream>
#include<string.h>
#include<stack>
#include<queue>
const int Max=100;
const int VISITED=101010;
const int UNVISITED=111111;
const int AFFINITY=101010;
const int INFINITY=111111;
using namespace std;
class Edge
{
public:
int start;
int end;
int weight;

Edge(int st=0,int en=0,int w=0):start(st),end(en),weight(w){}
bool operator>(Edge oneEdge){return weight>oneEdge.weight?true:false;}
bool operator<(Edge oneEdge){return weight<oneEdge.weight?true:false;}
bool operator!=(Edge oneEdge)
{
if(weight!=oneEdge.weight||start!=oneEdge.start||end!=oneEdge.end)
return true;
return false;
}

};

class AdjGraf
{
private:
int verticesNum;
int edgeNum;

int **matrix;

int *Mark;
public:

AdjGraf(int vert)
{
int i=0,j=0;
verticesNum=vert;
matrix=(int**)new int*[vert];
for(i=0;i<vert;i++)
matrix[i]=new int[vert];

Mark=new int[vert];
for(i=0;i<vert;i++)
for(j=0;j<vert;j++)
{
matrix[i][j]=0;

}
for( int m=0;m<verticesNum;m++)

Mark[m]=UNVISITED;

}

~AdjGraf();
//返回与顶点oneVertex相关联的第一条边
Edge FirstEdge(int oneVertex);
//返回与边PreEdge有相同关联顶点oneVertex的下一条边
Edge NextEdge( Edge preEdge);

//添加一条边
void setEdge(int fromVertex,int toVertex,int weight);
//删一条边
void delEdge(int fromVertex,int toVertex);
//如果oneEdge是边则返回TRUE，否则返回FALSE
bool IsEdge( Edge oneEdge)
{
if(oneEdge.start>=0&&oneEdge.start<verticesNum&&
oneEdge.end>=0&&oneEdge.end<verticesNum)
return true;
else return false;
}
//返回边oneEdge的始点
int FromVertex(Edge oneEdge){return oneEdge.start;}
//返回边oneEdge的终点
int ToVertex(Edge oneEdge){return oneEdge.end;}
//返回边oneEdge的权
int Weight(Edge oneEdge){return oneEdge.weight;}
void visit(int i){cout<<i+1<<" ";}
void BFS(int i=1);
void DFS(int i);
void DFSTraverse(int v);
void DFSNoReverse(int f=1);

Edge UNVISITEDEdge(int f);
};

AdjGraf::~AdjGraf()
{
for(int i=0;i<verticesNum;i++)
delete[]matrix[i];
delete[]matrix;
}

Edge AdjGraf::FirstEdge(int oneVertex)
{ int i;
Edge tempEdge;
tempEdge.start=oneVertex;
for( i=0;i<verticesNum;i++)
if(matrix[oneVertex][i]!=0)
break;
tempEdge.end=i;
tempEdge.weight=matrix[oneVertex][i];
return tempEdge;
}

Edge AdjGraf ::NextEdge( Edge preEdge)
{
Edge tempEdge;
tempEdge.start=preEdge.start;
int i=0;
for(i=preEdge.end+1;i<verticesNum;i++)
if(matrix[preEdge.start][i]!=0)
break;
tempEdge.end=i;
tempEdge.weight=matrix[preEdge.start][i];

return tempEdge;

}

void AdjGraf::setEdge(int fromVertex,int toVertex,int weight)
{
if(matrix[fromVertex-1][toVertex-1]==0)

edgeNum++;
matrix[fromVertex-1][toVertex-1]=weight;

}

void AdjGraf::delEdge(int fromVertex,int toVertex)
{
if(matrix[fromVertex][toVertex]==0)
edgeNum--;
matrix[fromVertex][toVertex]=0;

}
/*************递归实现深度优先****************/
void AdjGraf::DFS(int i)
{

visit(i);
Mark[i]=VISITED;
for(Edge e=FirstEdge(i);IsEdge(e);e=NextEdge(e))
if(Mark[ToVertex(e)] == UNVISITED)
DFS(ToVertex(e));

}
void AdjGraf::DFSTraverse(int v)
{
v--;
int i;
for(i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;
for(i=v;i<v+verticesNum;i++)
if (Mark[i]== UNVISITED)
DFS(i);
}

Edge AdjGraf::UNVISITEDEdge(int f)
{ int i;

for( Edge e=FirstEdge(f);IsEdge(e);e=NextEdge(e))
if(Mark[e.end]==UNVISITED)
return e;

return Edge(verticesNum,verticesNum,0) ;

}
/*************非递归实现深度优先**************/
void AdjGraf::DFSNoReverse(int f)
{
f--;
int i,counter=0,j,flag;
stack<int>Temp;
for(i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;
flag=f;
while(counter<12)
{

while(flag!=verticesNum&&IsEdge(UNVISITEDEdge(flag))||!Temp.empty())
{
// Edge tempEdge=UNVISITEDEdge(j);
while(flag!=verticesNum&&Mark[flag]==UNVISITED)
{

visit(flag);
Mark[flag]=VISITED;
Temp.push(flag);
flag=UNVISITEDEdge(flag).end;
}

if(!Temp.empty())
{

flag=UNVISITEDEdge(Temp.top()).end;
Temp.pop();
}

}

if(Mark[counter]==UNVISITED) flag=counter;
else counter++;
}
}

/*************非递归实现广度优先**************/
void AdjGraf::BFS(int v)
{
int i;
v--;
for( i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;

queue<int>tempqueue;
i=0;
/*********v先从指定位置开始，然后从v=0,1,2......
依次检查是否有孤立结点*****************/
while(i<verticesNum)
{
tempqueue.push(v);
while(!tempqueue.empty())
{
v=tempqueue.front();
tempqueue.pop();
if(Mark[v]==UNVISITED)
{
visit(v);
Mark[v]=VISITED;

for(Edge e=FirstEdge(v);IsEdge(e);e=NextEdge(e))
{
v=ToVertex(e);
tempqueue.push(v);

}

}

}
/***********防止出现孤立点****************/
if(Mark[i]==VISITED) i++;
else v=i;
}

}

int main()
{
AdjGraf Graph(12);
Graph.setEdge(1,2,1);
Graph.setEdge(2,1,1);
Graph.setEdge(1,3,5);
Graph.setEdge(3,1,5);/** V1 V12 V11 */
Graph.setEdge(2,4,3);/** / \ / \ */
Graph.setEdge(4,2,3);/** v2 v3 V10 V9 */
Graph.setEdge(2,5,7);/** / \ / \ */
Graph.setEdge(5,2,7);/** v4 v5 v6-v7 */
Graph.setEdge(4,8,4);/** \ / */
Graph.setEdge(8,4,4);/** v8 */
Graph.setEdge(5,8,3);
Graph.setEdge(8,5,3);
Graph.setEdge(3,6,2);
Graph.setEdge(6,3,2);
Graph.setEdge(3,7,1);
Graph.setEdge(7,3,1);
Graph.setEdge(6,7,6);
Graph.setEdge(7,6,6);
Graph.setEdge(12,9,6);
Graph.setEdge(9,12,6);
Graph.setEdge(12,10,6);
Graph.setEdge(10,12,6);
Graph.setEdge(11,11,6);
cout<<"DFSTraverse:"<<endl;
Graph.DFSTraverse(3);
cout<<endl;
cout<<"DFSNoReverse:"<<endl;
Graph.DFSNoReverse(3);
cout<<endl;
cout<<"BFS:"<<endl;
Graph.BFS(3);
cout<<endl;

return 0;

}

以上代码运行环境codeblocks 程序采用DFS递归算法 DFS非递归算法 BFS非递归算法
望采纳~

❸ （转）BFS与DFS

广度优先搜索（BFS）和深度优先搜索（DFS）都是图遍历算法中的重要成员。BFS采用的策略是：越早被访问到的顶点，其邻居越优先被访问。类似于树的层次遍历。DFS采用的策略是：优先选取最后一个被访问到的顶点的邻居。类似于树的前序遍历。

BFS算法的时间比较简单。
顶点的状态有三种：（1）visited；（2）discovered；（3）undiscovered；
采用辅助队列Q存放已经遍历的顶点。每一次迭代都从Q中取出当前的首顶点v；在逐一核对其邻居状态u的状态并做相应的处理，最后将顶点v置为visited，即可进入下一步迭代。

DFS算法是优先选取最后一个被访问到的顶点的邻居。因此可以栈作为辅助的数据结构（当然不用也行，只是为了好实现）。DFS的每一次迭代中，都先将当前节点v标记为discovered状态，再逐一核对其各邻居u的状态并做相应的处理，待其所有邻居均已处理完毕之后，将顶点v设置为visited状态，然后进行回溯。

DFS算法重要的有一个活跃期的时间区间。通过活跃期可以判断两个顶点之间是否是祖先-后代关系，判断的充要条件是两个顶点的活跃期是否相互包含。

BFS和DFS的时间复杂度都是O(n+e)，其中n是顶点数，e是边的数量。

参考：
https://www.cnblogs.com/brucekun/p/8503042.html

❹ 用C语言编写三个算法，BFS或DFS，爬山算法，遗传算法实现八皇后问题

网络算法名，加上八皇后
比如
BFS 八皇后问题 C语言。
或者
遗传算法 八皇后问题 C语言

然后根据搜索结果 就可以得到算法和代码了。

❺ 小弟是ACM弱渣，一直不知道DFS和bfs在哪种场合用更加好

DFS 和 BFS使用哪种跟具体的数据（源点和目标的位置）有关，比如你数据结构是树，要搜索根节点到某一叶子节点的路径。这时候，如果这个叶子节点距离根节点比较远，使用深度优先DFS效率最高。如果这个叶子节点距离根节点比较近，使用广度优先BFS效率更高。你可以自己画一个树，自己用脑子模拟一下这两个算法，一下子就明白了。

❻ dfs生成森林和bfs生成森林怎么画

对强连通有向图，用DFS和BFS算法可分别求得DFS和BFS生成树，对非强连通图，则一般只能得到生成森林。

❼ 求解关于DFS,BFS的算法时间复杂度分析

记住就行了，DFS、BFS时间复杂度对于采用临接矩阵存储时是O(n)；对于采用临接表时是O(n+e).

❽ 图的dfs,bfs是否唯一,导致不唯一的因素有哪些

DFS 和 BFS 都是唯一的,
DFS = 贪婪算法 = 一条道走到结尾(有可能这不是最短的).
BFS = 常用路径算法 = 就是你也三条路, 你第一条路走一步,第二条也走一步,第三条路也走一步.
BFS 肯定是唯一的, 因为是平均走的, dfs有可能不是唯一的假如你选择的顺序不一样,比如
路径 A->B or D->C 你想先从D走那就是ADC 然后 ABC 反之亦然.
所以BFS是稳定的,唯一的，也是最常用的路径算法。

❾ JS 深度优先遍历(DFS)和广度优先遍历(BFS)

深度优先遍历DFS

自定义：深度单线游走，从根走完最后一个节点，在游走兄弟节点，走完兄弟的所有子节点，循环之。

     递归算法：

function deepFirstSearch(node, nodeList = []) {

  if (node) {

    nodeList.push(node);

    var children = node.children;

    for (var i = 0; i < children.length; i++)

      //每次递归的时候将 需要遍历的节点 和 节点所存储的数组传下去

      deepFirstSearch(children[i], nodeList);

  }

  return nodeList;

}

非递归算法：

function deepFirstSearch(node) {

  var nodes = [];

  if (node != null) {

    var stack = [];

    stack.push(node);

    while (stack.length != 0) {

      var item = stack.pop();

      nodes.push(item);

      var children = item.children;

      for (var i = children.length - 1; i >= 0; i--)

        stack.push(children[i]);

    }

  }

  return nodes;

}

广度优先遍历(BFS)

自定义：从根开始 层层推进 走完一层 走下一层 （犹如爬楼，走完一层的楼梯，继续下一层的楼梯）

递归算法：（容易栈溢出）

function breadthFirstSearch(node) {

  var nodes = [];

  var i = 0;

  if (!(node == null)) {

    nodes.push(node);

    breadthFirstSearch(node.nextElementSibling);

    node = nodes[i++];

    breadthFirstSearch(node.firstElementChild);

  }

  return nodes;

}

非递归算法：（推荐）

function breadthFirstSearch(node) {

  var nodes = [];

  if (node != null) {

    var queue = [];

    queue.unshift(node);

    while (queue.length != 0) {

      var item = queue.shift();

      nodes.push(item);

      var children = item.children;

      for (var i = 0; i < children.length; i++)

        queue.push(children[i]);

    }

  }

  return nodes;

}

❿ 网络流的最大流算法

1、augment path，直译为“增广路径”，其思想大致如下：
原有网络为G，设有一辅助图G'，其定义为V(G') = V(G)，E(G')初始值（也就是容量）与E(G)相同。每次操作时从Source点搜索出一条到Sink点的路径，然后将该路径上所有的容量减去该路径上容量的最小值，然后对路径上每一条边<u,v>添加或扩大反方向的容量，大小就是刚才减去的容量。一直到没有路为止。此时辅助图上的正向流就是最大流。
我们很容易觉得这个算法会陷入死循环，但事实上不是这样的。我们只需要注意到每次网络中由Source到Sink的流都增加了，若容量都是整数，则这个算法必然会结束。
寻找通路的时候可以用DFS，BFS最短路等算法。就这两者来说,BFS要比DFS快得多，但是编码量也会相应上一个数量级。
增广路方法可以解决最大流问题，然而它有一个不可避免的缺陷，就是在极端情况下每次只能将流扩大1（假设容量、流为整数），这样会造成性能上的很大问题，解决这个问题有一个复杂得多的算法，就是预推进算法。
2、push label，直译为“预推进”算法。
3、压入与重标记(Push-Relabel)算法
除了用各种方法在剩余网络中不断找增广路(augmenting)的Ford-Fulkerson系的算法外，还有一种求最大流的算法被称为压入与重标记(Push-Relabel)算法。它的基本操作有：压入，作用于一条边，将边的始点的预流尽可能多的压向终点；重标记，作用于一个点，将它的高度（也就是label）设为所有邻接点的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快，但是缺点是相对难以理解。
Relabel-to-Front使用一个链表保存溢出顶点，用Discharge操作不断使溢出顶点不再溢出。Discharge的操作过程是：若找不到可被压入的临边，则重标记，否则对临边压入，直至点不再溢出。算法的主过程是：首先将源点出发的所有边充满，然后将除源和汇外的所有顶点保存在一个链表里，从链表头开始进行Discharge，如果完成后顶点的高度有所增加，则将这个顶点置于链表的头部，对下一个顶点开始Discharge。
Relabel-to-Front算法的时间复杂度是O(V^3)，还有一个叫Highest Label Preflow Push的算法复杂度据说是O(V^2*E^0.5)。我研究了一下HLPP，感觉它和Relabel-to-Front本质上没有区别，因为Relabel-to-Front每次前移的都是高度最高的顶点，所以也相当于每次选择最高的标号进行更新。还有一个感觉也会很好实现的算法是使用队列维护溢出顶点，每次对pop出来的顶点discharge，出现了新的溢出顶点时入队。
Push-Relabel类的算法有一个名为gap heuristic的优化，就是当存在一个整数0<k<V，没有任何顶点满足h[v]=k时，对所有h[v]>k的顶点v做更新，若它小于V+1就置为V+1。
cpp程序: #include<cstdio>#include<cstring>#include<algorithm>#include<queue>#;inttt,kase;intnn,m;intH[45],X[1004],P[1004],flow[1004],tot,cap[1005];intd[45];intS,T;voidadd(intx,inty,intz){P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;cap[tot]=flow[tot];}queue<int>q;boolbfs(){memset(d,0,sizeof(d));d[S]=1;intx;q.push(S);while(!q.empty()){x=q.front();q.pop();for(inti=H[x];i;i=X[i]){if(flow[i]>0&&!d[P[i]]){d[P[i]]=d[x]+1;q.push(P[i]);}}}returnd[T];}intdfs(intx,inta){if(x==T||a==0)returna;intf=a,tmp;for(inti=H[x];i;i=X[i]){if(flow[i]>0&&d[P[i]]==d[x]+1){tmp=dfs(P[i],min(flow[i],a));flow[i]-=tmp;a-=tmp;flow[i^1]+=tmp;if(!a)break;}}if(f==a)d[x]=-1;returnf-a;}intDinic(){intf=0;while(bfs())f+=dfs(S,inf);returnf;}intmain(){/**输入过程省略**/intmaxflow=Dinic();printf(%d ,maxflow);return0;}