2018-06-15 00:08:59

深度优先遍历 免费编辑 添加义项名

B 添加义项
?
义项指多义词的不同概念,如李娜的义项:网球运动员、歌手等;非诚勿扰的义项:冯小刚执导电影、江苏卫视交友节目等。 查看详细规范>>
所属类别 :
其他
其他
编辑分类

深度优先搜索,是图论中的经典算法。其利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。

基本信息

  • 中文名

    深度优先遍历

  • 外文名

    Depth-First Traversa

  • 学科

    数据结构

  • 属于

目录

折叠 编辑本段 递归定义

深度优先遍历(Depth-First Traversal)

假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。

图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地,用此方法遍历图就很自然地称之为图的深度优先遍历。

折叠 编辑本段 过程

设x是当前被访问顶点,在对x做过访问标记后,选择一条从x出发的未检测过的边(x,y)。若发现顶点y已访问过,则重新选择另一条从x出发的未检测过的边,否则沿边(x,y)到达未曾访问过的y,对y访问并将其标记为已访问过;然后从y开始搜索,直到搜索完从y出发的所有路径,即访问完所有从y出发可达的顶点之后,才回溯到顶点x,并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时,若x不是源点,则回溯到在x之前被访问过的顶点;否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过,若图G是连通图,则遍历过程结束,否则继续选择一个尚未被访问的顶点作为新的顶点,继续遍历。

template <int max_size>void Digraph<max_size> :: depth_first(void (*visit)(Vertex &)) const

/* Post: The function *visit has been performed at each vertex of the Digraph in depth-first order.

Uses: Method traverse to produce the recursive depth-first order. */

{

bool visited [max_size];

Vertex v;

for (all v in G) visited [v] = false;

for (all v in G) if (!visited [v])

traverse (v, visited, visit);

}

template <int max_size>

void Digraph<max_size>::traverse(Vertex &v, bool visited[ ],void (*visit)(Vertex &)) const

/* Pre: v is a vertex of the Digraph.

Post: The depth-first traversal, using function *visit, has been completed for v and for all vertices that can be reached from v.

Uses: traverse recursively. */

{

Vertex w;

visited [v] = true;

(*visit) (v);

for (all w adjacent to v)

if (!visited [w])

traverse (w, visited, visit);

}

java代码如下:

//求DFS的深度优先递归算法

public class DNFSreach {

/**

* 这里是文档说明

* 算法如下

*开始

*Start;

*

* procedure DFS_visit(G,u)

* color[u] = Gray;//白色结点u已被发现

* for each edge (u,v)do

* if color[u] = White then

* DFS_visit(G,v);

* repeat color[u]=black;//完成后置u为黑色

* end;

*

* procedure DFS(G)

* for each vertex u 属于V do

* color[u] = white

* for vertex each u 属于 V do

* if color[u]=white

* then DFS_visit(G,u)

* repeat

*

*

* 构建一个无向图

* 无穷大表示这两个点无边,1表示两者有边

* 白色用1表示,灰色用2表示,黑色用3表示

* 初始状态均为白色

* 搜索中被发现的顶点置为灰色

* 结束时,即其邻接表被完全检索之后,其被置为黑色

* 构建一个color[8]数组,其中color[0]不用

* 初始化为0

* S表示无穷大

* 0 1 2 3 4 5 6 7 8

* -------------------------

* 0

* 1 s 1 1 s s s s s

* 2 1 s s 1 1 s s s

* 3 1 s s s s 1 1 s

* 4 s 1 s s s s s 1

* 5 s 1 s s s s s 1

* 6 s s 1 s s s 1 s

* 7 s s 1 s s 1 s s

* 8 s s s 1 1 s s s

*

* 深度优先搜索的结果应该为

* 1-2-4-8-5-3-6-7

*

* @param args

*/

static int color[];

static int d =0;

public static void main(String[] args) {

int s = Integer.MAX_VALUE;

int G[][]={{s,s,s,s,s,s,s,s,s},

{s,s,1,1,s,s,s,s,s},

{s,1,s,s,1,1,s,s,s},

{s,1,s,s,s,s,1,1,s},

{s,s,1,s,s,s,s,s,1},

{s,s,1,s,s,s,s,s,1},

{s,s,s,1,s,s,s,1,s},

{s,s,s,1,s,s,1,s,s},

{s,s,s,s,1,1,s,s,s}};

color = new int [9];

ProcedureDFS(G,9);

}

public static void ProcedureDFS(int [][]G,int n){

//图是以二维数组的形式保存

//n是二维数组的维数

for(int i=1;i <= n-1;i++){

color[i]=1;//把每一个顶点都置为白色,表示还没搜索

}

for(int i=1;i<= n-1;i++){

//对于每一个顶点没被访问的顶点进行访问

if(color[i] == 1){

DFS_visit(G,i);//遍历其访问的顶点

}

}

}

private static void DFS_visit(int[][] g, int i) {

// TODO 自动生成的方法存根

color[i] = 2;//标志为灰色,表示被访问过

d++;

if(d != g.length-1)

System.out.print(""+i+" -> ");

if(d == g.length-1){

System.out.println(""+i);

}

for(int t=1;t<= g.length-1;t++){

//邻接点没有被访问到

if(color[t] == 1 && g[i][t] != Integer.MAX_VALUE){

DFS_visit(g,t);

}

}

color[i] = 3;//标志位黑色

}

}

最小花费举例:

package test1;

import java.io.FileInputStream;

import java.util.Scanner;

class Deptfsearch {

static int Answer, N, sum, cost;

static int[][] input, mark;

static int[] visit;

static boolean check() {

for (int v = 1; v <= N; v++) {

if (visit[v] == 0)

return false;

}

return true;

}

static void Try(int u) {

if (check()) {

if (input[u][1] != 0 && Answer > cost + input[u][1])

Answer = cost + input[u][1];

return;

}

if (Answer < cost)

return;

for (int v = 1; v <= N; v++) {

if (input[u][v] != 0 && visit[v] == 0) {

visit[v] = 1;

cost = cost + input[u][v];

Try(v);

cost = cost - input[u][v];

visit[v] = 0;

}

}

}

public static void main(String args[]) throws Exception {

@SuppressWarnings("resource")

Scanner sc = new Scanner(System.in);

sc = new Scanner(new FileInputStream("sample_input.txt"));

int T = sc.nextInt();

for (int test_case = 0; test_case < T; test_case++) {

sum = 0;

cost = 0;

N = sc.nextInt();

input = new int[N + 1][N + 1];

mark = new int[N + 1][N + 1];

visit = new int[N + 1];

for (int i = 1; i <= N; i++) {

for (int j = 1; j <= N; j++) {

input[i][j] = sc.nextInt();

sum = sum + input[i][j];

}

}

Answer = sum + 1;

visit[1] = 1;

if (N == 1)

Answer = input[1][1];

else

Try(1);

// Print the answer to standard output(screen).

System.out.println("Case #" + (test_case + 1));

System.out.println(Answer);

}

}

}

阅读全文

热点资讯

我的关注