深度优先搜索及常用剪枝方法

深度优先搜索（DFS）
主要有邻接表和邻接矩阵两种。
主要的剪枝方法有：
1.标记已经走过的点，避免重复路过。但需要将其撤回标记，以保证新的路线能够经过该点。
2.加以判断，如果当前状态已经不是最优解可以不再继续搜索。
3.动态存储和比较最优解。
OpenJudge - 1724:ROADS
#include
#include
#include
using namespace std;
int K, N, R;
struct Road {
int d, L, t;
};
int minLen;
int totalLen, totalcost;
int visited[55];
int minL[101][10010];
vector> G(110);
void dfs(int s)
{
if (s == N)
{
minLen = min(minLen, totalLen);
return;
}
for (int i = 0; i < G

深度优先搜索及常用剪枝方法最先出现在Python成神之路。