图的深度优先搜索算法DFS
1.问题描写叙述与理解
深度优先搜索（Depth First Search。DFS）所遵循的策略。如同其名称所云。是在图中尽可能“更深”地进行搜索。
在深度优先搜索中，对最新发现的顶点v若此顶点尚有未探索过从其出发的边就探索之。
当v的全部边都被探索过。搜索“回溯”到从其出发发现顶点v的顶点。此过程继续直至发现全部从源点可达的顶点。若图中还有未发现的顶点，则以当中之中的一个为新的源点反复搜索。直至全部的顶点都被发现。与BFS中源顶点是指定的稍有不同。 DFS搜索轨迹
在深度优先搜索过程中对每个顶点u跟踪两个时间：发现时间d[u]和完毕时间f [u]。d[u]记录首次发现（u由白色变成灰色）时刻，f [u]记录完毕v的邻接表检測（变成黑色）时刻。
输入：图
输出：G的深度优先森林
- 算法伪代码
DFS(G)
1 for each vertex uV[G]
2 do color[u]←WHITE
3 [u] ←NIL
4 time← 0
5 S←
6 for each vertex s V[G]
7 do if color[s] = WHITE
8 then color[s] ← GRAY
9 d[s] ← time← time +1
10 PUSH(S, s)
11 while S≠
12 do u←TOP(S)
13 if v Adj[u] and color[v] = WHITE
14 then color[v] ←GRAY
15 [v] ←u
16 d[v] ← time← time +1
17 PUSH(S, v)
18 else color[u] ← BLACK
19 f [u] ← time ← time +1
20 POP(S)
21 return d, f, and
DFS施于一个有向图的过程
3.程序实现
/***********************************
*@file:graph.h
*@ brif:图的邻接表的算法实现类
*@ author:sf
*@data：20150704
*@version 1.0
*
************************************/
#ifndef _GRAPH_H
#define _GRAPH_H
#include <list>
using namespace std;
struct vertex//邻接表节点结构
{
double weight;//边的权值
int index;//邻接顶点
};
class Graph
{
public:
list<vertex> *adj;//邻接表数组
int n;//顶点个数
Graph(double *a,int n);
~Graph();
};
#endif // _GRAPH_H#include "stdafx.h"
#include "Graph.h"
Graph::Graph(float *a,int n):n(n)//a是图的邻接矩阵
{
adj = new list<vertex>[n];
for (int i = 0; i < n;i++)//对每个顶点i
for (int j = 0; j < n;j++)
if (a[i*n+j]!=0.0)
{
vertex node = { a[i*n + j], j };//a[i,j]=weight 边的权重 j,邻接节点号
adj[i].push_back(node);
}
}
Graph::~Graph()
{
delete[] adj;
adj = NULL;
}#ifndef _DFS_H
#define _DFS_H
/***********************************
*@file:dfs.h
*@ brif:深度优先搜索算法实现
*@ author:sf
*@data：20150708
*@version 1.0
*
************************************/
#include "Graph.h"
#include <stack>
struct Parameter3
{
int* first;
int* second;
int* third;
};
/***********************************
*@function:dfs
*@ brif:图的邻接表的图的深度优先搜索(Depth First Search, DFS)算法实现
*@ input param: g 图的邻接表
*@ output param: pi g的深度优先森林 d ：发现时间 f:完毕时间
*@ author:sf
*@data：20150708
*@version 1.0
*
************************************/
Parameter3 dfs(const Graph& g);
#endif#include "dfs.h"
enum vertex_color{WHITE,GRAY,BLACK};
typedef enum vertex_color Color;
Parameter3 dfs(const Graph& g)
{
int n = g.n, u, v, s;
Color *color = new Color[n];
int *pi = new int[n], *d = new int[n], *f = new int[n], time = 0;
fill(pi, pi + n, -1);
fill(color, color + n, WHITE);
stack<int> S;//栈
list<vertex>::iterator *pos = new list<vertex>::iterator[n];
for (u = 0; u < n; ++u)
pos[u] = g.adj->begin();
for (s = 0; s < n;++s)
{
if (color[s]==WHITE)//以顶点s为根创建一颗深度优先树
{
color[s] = GRAY;
d[s] = ++time;
S.push(s);
while (!S.empty())
{
u = s = S.top();
list<vertex>::iterator p;
p = pos[u];
while ( g.adj[n].end()!=p )
//眼下程序有些问题，在訪问这个末尾迭代器是出错，眼下还没有解决
{
v = (*p).index;
if (color[v] == WHITE)
break;
else
++p;//u的邻接点中找尚存在的未发现点
}
pos[u] = p;
if (pos[u] != g.adj[n].end())//找到白色顶点将其压入栈
{
color[v] = GRAY;
d[v] = ++time;
pi[v] = u;
S.push(v);
}
else//否则完毕对u的訪问
{
color[u] = BLACK;
f[u] = ++time;
S.pop();
pos[u] = g.adj[n].begin();
}
}
}
}
delete[]color; delete[]pos;
Parameter3 reParams;
reParams.first = pi;
reParams.second = d;
reParams.third = f;
return reParams;
}// DFS.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "dfs.h"
#include "Graph.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int s = 1, n = 8;
Parameter3 ret;
double a[] =
{
0, 1, 0, 0, 1, 1,
1, 0, 0, 0, 0, 1,
0, 0, 0, 1, 0, 1,
0, 0, 1, 0, 0, 1,
1, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 0
};
Graph g(a, 6);
ret = dfs(g);
for (int i = 0; i < 6; ++i)
{
if (i != s)
{
cout << i << ";" << "parent " << ret.first[i];
cout << " discover/finish: " << ret.second[i]<<"/"<<ret.third[i] << endl;
}
}
system("pause");
return (EXIT_SUCCESS);
}
1、SpringBoot+Elasticsearch
2、rails中path、url路径解析，routes信息，form_for剖析,link_to示例，路由实例说明
3、二叉查找树的前序遍历，后序遍历和中序遍历互求算法模板
4、字符串的最长连接
5、B - Parentheses Balance （UVA - 673）