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：

    比较所有可能