DFS栈非递归和贪婪算法

DFS（非递归，栈实现）

1. 前提条件

我们前面写的是：

void dfs(int u)
{
visited[u]=1;

...

dfs(v);

}

这里：dfs(v)

其实就是：系统帮你压栈

所以：递归 = 系统栈

那么：不用递归

自己写一个栈

效果完全一样。

2. 为什么递归就是栈？

例如：

图：

0

↓

1

↓

2

递归：

dfs(0)

↓

dfs(1)

↓

dfs(2)

实际上系统维护：

栈

↓

0

↓

1

↓

2

当：dfs(2)

结束以后：

弹栈回到1

结束：弹栈回到0

所以：递归

本质就是系统维护一个栈。

3. 自己维护栈

数组实现：

int stack[MAXN];

int top = -1;

压栈：

stack[++top] = x;

弹栈：

int x = stack[top--];

4. DFS 非递归模板

void dfs(int start)
{
int stack[MAXN];
int top = -1;

stack[++top] = start;
visited[start] = 1;

//先定义start的位置top是0
while(top != -1)
{
int u = stack[top--];

    printf("%d ", u);
 //这里是往外面弹栈
 //弹空了之后重新入栈
    struct EdgeNode* cur = adj[u];

    while(cur != NULL)
    {
        int v = cur->to;

        if(!visited[v])
        {
            visited[v] = 1;
            stack[++top] = v;
        }
    //也就是后进先出
        cur = cur->next;
    }
}

}

5. 为什么压栈时就 visited？

弹栈再visited

容易：重复入栈

例如：

0

/ \

1 2
/

3

如果：3没有提前visited

那么：1会压一次3

2又压一次3

于是3进栈两次

所以：

入栈立刻visited
保证：最多入栈一次。

6. 举例

图：

0
/ \

1 2

|

3

开始：

stack

0

弹：

0

访问：

0

压：

1

2

栈：

2

1

（注意栈先进后出）

弹：2

访问：

0 2

弹：1

访问：

0 2 1

压：3

弹：3

访问：

0 2 1 3

结束。

7. 为什么顺序可能不同？

栈先进后出

所以：如果想和递归一样。

通常：逆序压栈

只要求DFS。

8. DFS总结

递归DFS

系统栈

---

非递归DFS

自己写栈

---

本质一样

都是：一路走到底再回来

贪心算法（Greedy Algorithm）

1. 前提条件

贪心算法不是一种具体算法，而是一种：

算法设计思想

核心思想：

每一步都选择当前最优

希望最后得到全局最优

例如：

每次选最小

每次选最大

每次选最近

每次选最便宜

都是贪心。

2. 贪心算法什么时候能用？

不是所有题都能贪心。

必须满足： 贪心选择性质

局部最优一定能推出

全局最优

最优子结构：

问题可以拆成很多子问题

每个子问题最优
整体仍然最优

3. 贪心算法的一般步骤

① 建立数据

↓

② 排序

↓

③ 从前往后扫描

↓

④ 当前最优就选择

↓

⑤ 更新状态

↓

⑥ 重复直到结束

4. 贪心算法固定模板

虽然没有统一模板，但大多数都长这样：

//① 排序
qsort(...);

//② 扫描
for(int i = 0; i < n; i++)
{
if(当前元素满足条件)
{
选择当前元素;

    更新答案;

    更新状态;
}

}

其实就是：排序+不断做局部最优

5. 例子一：Kruskal

边：

0-1 2

0-2 5

1-2 1

排序：

1

2

5

代码：

qsort(edge,
m,
sizeof(struct Edge),
cmp);

for(int i = 0; i < m; i++)
{
if(find(edge[i].u) != find(edge[i].v))
{
unite(edge[i].u,
edge[i].v);

    total += edge[i].w;
}

}

这里：

贪心就是：

每次挑最短边

6. 例子二：Prim

Prim没有排序。

因为：

lowCost[]

已经保存了

当前最便宜

所以：

int u = -1;

for(int i = 0; i < n; i++)
{
if(!visited[i] &&
(u == -1 ||
lowCost[i] < lowCost[u]))
{
u = i;
}
}

实际上：

就是：每次挑当前最便宜的点

也是：贪心。

7. 例子三：Dijkstra

代码：

int u = -1;

for(int i = 0; i < n; i++)
{
if(!visited[i] &&
(u == -1 ||
dist[i] < dist[u]))
{
u = i;
}
}

这里：贪心选择：

dist最小

直接确定。

然后：

dist[v] =
min(dist[v],
dist[u]+w);

更新。

8. 一个贪心例子（活动安排）

例如：

会议：
A

8~10

B

9~11

C

10~12

目标：

最多安排多少场？

步骤：

① 排序

按：结束时间

排序。

② 扫描：

sort(endTime);

int lastEnd = -1;

for(int i = 0; i < n; i++)
{
if(start[i] >= lastEnd)
{
ans++;

    lastEnd = end[i];
}

}

为什么？

因为：结束越早

给后面的空间越大。

这是：经典贪心。

9. 一个失败例子（为什么不能乱贪）

硬币：

1

3

4

找：

6

贪心：

4

↓

1

↓

1

三个硬币。

但是：

3

↓

3

两个硬币。

说明：贪心失败。

所以：不是所有题

都能贪心。

10. 贪心 vs 动态规划

例如：零钱兑换。

DP：

dp[i] =
min(dp[i],
dp[i-coin]+1);

比较：所有可能。

而贪心：直接拿最大的。

DP：会回头比较。

贪心：不会回头。

11. 贪心常见代码模式
    模式一：排序+扫描（最常见）
    qsort(...);

for(...)
{
if(满足条件)
{
更新答案;
}
}

例如：Kruskal

活动安排

区间覆盖

模式二：不断找当前最优
int best = -1;

for(...)
{
if(更优)
{
best = i;
}
}

例如：

Prim

Dijkstra

模式三：优先队列

以后会学：

while(heap不空)
{
取最优;

更新;

}

例如：

Huffman树

Dijkstra堆优化

总结
Greedy（贪心）

核心思想：

每一步选择当前最优

希望得到整体最优

基本步骤：

建立数据

↓

排序（很多题）

↓

扫描

↓

当前最优就选

↓

更新状态

↓

重复

常见代码：

① 排序+扫描

qsort()

for()

② 不断找最优

best

③ 优先队列

heap

经典算法：

Prim
Kruskal
Dijkstra
Huffman
活动安排
区间覆盖

与DP区别：

Greedy：

不回头

DP：

比较所有可能