dfs算法
‘壹’ DFS 算法 简介
Int visited[]; //初始化辅助数组,元素均为0
Void DFS(List,v,p)
{
visit(v); //访问起点
visited[v]=1; //起点已访问,0变1
while(p->link) //当存在起点的第一个邻接点时
{ p=p->link;
v=p->data;
if(!visited[v])
DFS(List,v,p); //进行递归
}
return;
}
下面是您的程序:
void DFS(List,v,p)
{
visit(v);
visited[v]=1;
while(p) //此处不该用p,应该判断它的邻接点是否存在
{
if(!visited[v])DFS(List,v,p);
p=p->link;
v=p->data; //此处的顺序肯定不对
}
return;
}
‘贰’ 数据结构图的遍历 1)先任意创建一个图； 2)图的DFS,BFS的递归和非递归算法的实现 3)要求用有向图和无向图
//DFS,无向图+有向图，邻接矩阵实现。
//你的东西太多了。一个一个问吧。而且200分太少了。你这么多种情况。至少也得写8种吧。
#include<string>
#include<string.h>
#include<stdio.h>
#include<vector>
#include<iostream>
#include<set>
#include<math.h>
#include<map>
#include<algorithm>
#include<queue>
usingnamespacestd;
constintMAX=210000;
intmat[10][10];
boolvis[10]={false};
voidDFS(ints,intn)
{
inti;
vis[s]=true;
printf("%d",s);
for(i=0;i<n;i++)
{
if(mat[s][i]&&!vis[i])
{
DFS(i,n);
}
}
}
intmain()
{
inti,n;
intj;
n=10;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
mat[i][j]=1;
}
DFS(0,n);
return0;
}
/*
*/
‘叁’ 深度优先法(DFS)算法
从根节点开始，顺着它的某一子节点往下搜，所以再下一个是这个子节点的某一子节点，所以是个递归形式，当搜到子节点为NULL或者已经访问过了，于是回退到上一次的节点，若它还有没访问过的子节点继续往下搜，重复上述。当最后退回到根节点时，说明全部访问完毕，遍历完成。
‘肆’ 数据结构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非递归算法
望采纳~
‘伍’ 算法分析DFS求解
上网上查一查，这样的题我也不会。
‘陆’ 如何修改基于dfs的算法，使得可以避免对dfs生成的顶点序列进行逆序
可以把有限长非周期序列假设为一无限长周期序列的一个主直周期，即对有限长非周期序列进行周期延拓，延拓后的序列完全可以采用DFS进行处理，即采用复指数
第一题，DFS（深度优先遍历）是一个递归算法，在遍历的过程中，先访问的点被压入栈底（栈是先进后出），再说：拓扑有序是指如果点U到点V有一条弧，则在拓扑序列中U一定在V之前。深度优先算法搜索路径恰恰是一条弧，栈的输出是从最后一个被访问点开始输出，最后一个输出的点是第一个被访问的点。所以是逆的拓扑有序序列
第二题：无向图路径长度是指两个顶点之间弧的条数，如果两顶点路径长度有2条弧，则有3个顶点例如A——B——C；
第三题：A：极小连通图是一棵生成树，只有N-1条边，但是连通分量可能有N条边，例如极小连通图A—— B——C，连通分量“A”——B——C——“A”(这里的最后一个“A”跟第一个“A”一致）：；
‘柒’ 图的DFS遍历 先任意创建一个图； 图的DFS的递归和非递归算法的实现 用邻接矩阵、邻接表两种结构存储实现
java">packagecom.graphic;
publicclassDFS_Graph{
/**
*@paramargs
*/
publicstaticvoidmain(String[]args){
intmatrix[][]={{0,1,0,0,1},{1,0,1,1,1},
{0,1,0,1,0},{0,1,1,0,1},{1,1,0,1,0}};
DFS_Graphgraph=newDFS_Graph();
graph.init(matrix);
}
inttime=0;
GNodearray[];
publicvoidinit(intmatrix[][]){
array=newGNode[matrix.length];
for(inti=0;i<array.length;i++)//初始化
{
array[i]=newGNode(i);
}
for(inti=0;i<array.length;i++){
if(array[i].color.equals("w"))
{
DFS(array[i],matrix,array);
for(intj=0;j<array.length;j++)
{
if(j>0)
{
System.out.println(array[j].id+"color="+array[j].color
+"d_time="+array[j].d_time+"f_time="
+array[j].f_time+"par="+array[j].par.id);
}
else
{
System.out.println(array[j].id+"color="+array[j].color
+"d_time="+array[j].d_time+"f_time="
+array[j].f_time);
}
}
System.out.println();
System.out.println();
}
}
//DFS(array[0],matrix,array);
}
publicvoidDFS(GNodeu,intmatrix[][],GNodearray[]){
u.color="g";
time++;
u.d_time=time;
for(inti=0;i<matrix.length;i++){
if(matrix[u.id][i]==1&&array[i].color.equals("w")){
array[i].par=u;
DFS(array[i],matrix,array);
}
}
u.color="b";
time++;
u.f_time=time;
}
}
classGNode{
Stringcolor;//color=black没有访问，//color=gray正在访问//color=black已经访问结束了
intid;
intd_time;
intf_time;
GNodepar;
publicGNode(){
}
publicGNode(intid){
this.color="w";
this.d_time=0;
this.f_time=0;
this.par=null;
this.id=id;
}
}
别人写的代码你可能不容易理解的。给你个参考吧：算法导论第二版22章，图的基本算法，里面有关于图的DFS和BFS算法。代码是用伪代码写的，但是讲解很详细，慢慢看，就当做学习的过程吧。
‘捌’ 分别用DFS和BFS算法给电脑设置AI(JAVA)
有必胜策略的吧。。状态空间的上限是3^9也就是不到20000实际上没有这么多。所以直接采用BFS标记会比较好。算法的话就是填充表，把表（九个格子）填为必胜、必败，己胜，开始的时候全部标为必败，再从胜状态开始向回BFS（或者DFS也可以），己胜状态向回标的一定是败状态，必胜状态的上一状态为必败态，必败态的上一状态可能是必败或者必胜（这就是因为这家伙走错棋了所以要输！）
我的习惯。不写代码。没有意思。
‘玖’ 求有权无向图的DFS算法
深度优先遍历类似于树的先序遍历，俗称一条路走到黑，然后再考虑回溯的问题，回溯到最近访问的顶点并看它是否还有相邻顶点未访问，若无继续往前回溯。
我下面写写核心伪代码，其他诸如图的类型定义、还有你要对每个结点做的具体操作（我在代码中用visit()函数来代替了，具体做啥操作根据题目来）我就不写了。
bool visited[MSX_VERTEX_NUM]; //标记访问数组
void DFS_Traverse(Grath G) //对图G进行DFS
{
for(v=0;v<G.vexnum;++v)
{
visited[v]=false; //初始化已访问标记数据
}
for(v=0;v<G.vexnum;++v) //假设从v=0开始遍历
{
if(!visited[v])
DFS(G,v);
}
}
void DFS(Graph G,int v) //从顶点v出发，用递归的思想，深度优先遍历
{
visit(v); //这里的visit()就是对顶点v的具体操作，题目是啥就自己写啥
visited[v]=true; //标记已访问
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
//从最近结点开始，依次找相邻结点
{
if(!visited[w]) //w为还未访问的相邻结点
{
DFS(G,w);
}
}
}
‘拾’ c++DFS算法问题。
这个题是比较基本的DFS问题，建议你自己多看多试一下，自己做出来意义更大一点。我想提供给你另外一种思路，时间复杂度更低，对于每个坐标（X，Y）可以从（x-1，y）和（x，y-1）到达，所以到这一点的可能数就是到达两个先驱点的方案数量的和，把黑洞设置成0就行了