第一章 Kruskal 最小生成树
1. 前提条件
使用条件

Kruskal 用来求：

最小生成树（MST）

要求：无向连通带权图

和 Prim 一样。

和 Prim 的区别

Prim：长点

从一个点开始,不断加入新的点

Kruskal：挑边

每次挑最短的边,直到所有点连通

2. 核心概念

例如：

A----1----B

A----4----C

B----2----C

所有边：

AB 1

BC 2

AC 4

Kruskal：

第一步：
排序：
AB 1
BC 2
AC 4

然后：依次加入。

第一条：AB加入。

第二条：BC加入。

第三条：AC如果加入：

 A

/ \

B-C

会形成环

所以：不能加入->结束

核心思想

按边权从小到大排序
能加就加
形成环就跳过

3. 为什么要并查集？

问题：如何知道：

加入一条边

会不会形成环？

例如：已经有：

A-B

B-C

现在：A-C加入。

其实：A已经能到C,所以：加入以后形成环

用：并查集（Union Find）判断：两个点是不是已经连通。

4. 并查集

维护：parent[]

例如：

0

1

2

开始：

parent

0

1

2

说明：自己是一棵树

加入0-1以后：

parent

0

0

2

表示：

0

|

1

再加入：

1-2

得到：

parent

0

0

0

表示：

0

|

1

|

2

三个已经连通。

5. 并查集代码

初始化：

void init(int n)
{
    for(int i=0;i<n;i++)
    {
        parent[i]=i;
    }
}

查找根：

int find(int x)
{
    if(parent[x]!=x)
    {
        parent[x]=find(parent[x]);
    }

    return parent[x];
}
//查找如果不等于自己就返回他的根节点

这是：路径压缩

合并：

void unite(int x,int y)
{
    int fx=find(x);
    int fy=find(y);

    if(fx!=fy)
    {
        parent[fx]=fy;
    }
}
//把两个树合并到一块

6. 边结构
struct Edge
{
    int u;
    int v;
    int w;
};

表示：

u

↓

边

↓

v

权值w

7. Kruskal代码
int cmp(const void* a,const void* b)
{
    return ((struct Edge*)a)->w
         - ((struct Edge*)b)->w;
}
//先写比较权重的函数
int kruskal(struct Edge edge[],
            int n,
            int m)
{
    init(n);
//初始化创建树
    qsort(edge,
          m,
          sizeof(struct Edge),
          cmp);
//之后qsort自动排序，排边结构，m个元素，边结构，按照cmp的顺序
    int total=0;
    int cnt=0;

    for(int i=0;i<m;i++)
    {
        int u=edge[i].u;
        int v=edge[i].v;
//这里就是查找到边结构，如果说两个对应不是一个根，那就把他们合起来，之后total最小生成树增加
        if(find(u)!=find(v))
        {
            unite(u,v);

            total+=edge[i].w;

            cnt++;
        }
    }
//不等于n-1说明有断开了，没有最小生成树
    if(cnt!=n-1)
    {
        return -1;
    }

    return total;
}

总结就是：
把所有边按长度排队。从最短开始。

如果不会形成环：就拿。

如果会形成环：就丢掉。

直到拿够n-1条边。
第一章 深度优先搜索（DFS）
1. 前提条件

DFS（Depth First Search）是一种图和树的遍历算法。

主要解决：

① 图遍历

② 树遍历

③ 连通块

④ 判断是否连通

⑤ 回溯搜索

⑥ 岛屿问题

⑦ 路径搜索

适用于：树、图（有向图、无向图）、迷宫

2. 核心思想

一条路走到底
走不通再回来

例如：

        0
      /   \
     1     2
    /
   3

DFS访问顺序：

0

↓

1

↓

3

↑

↓

2


一直往下面钻

钻不动返回上一层

继续其它分支

这就是：回溯（Backtracking）

3. DFS为什么要递归？

例如：dfs(0)

发现：

0

↓

1

于是：dfs(1)

继续：

1

↓

3

于是：dfs(3)

3没有儿子。

于是：dfs(3)结束

自动：返回dfs(1)

继续：dfs(1)结束

返回：dfs(0)

继续：2

整个过程：

dfs(0)

↓

dfs(1)

↓

dfs(3)

↑

dfs(1)

↑

dfs(0)

↓

dfs(2)

4. DFS递归树

例如：

        0
      /   \
     1     2
    /
   3

真正调用过程：

dfs(0)

│

├────dfs(1)

│      │

│      └────dfs(3)

│

└────dfs(2)

特别容易理解。

5. 图的DFS代码

图采用邻接表：

struct EdgeNode
{
    int to;
    struct EdgeNode* next;
};

struct EdgeNode* adj[MAXN];

DFS：

int visited[MAXN];

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

    printf("%d ", u);

    struct EdgeNode* cur = adj[u];

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

        if(!visited[v])
        {
            dfs(v);
        }

        cur = cur->next;
    }
}

7. 每一句代码解释

第一句：

visited[u] = 1;

表示：已经访问过u以后不能再访问

第二句：printf("%d ",u);

访问当前节点。

第三句：

struct EdgeNode* cur = adj[u];

表示：找到u所有邻居

例如：

0

↓

1

↓

2

此时：

cur

↓

1

↓

2

↓

NULL

第四句：while(cur!=NULL)

表示：依次遍历所有邻居

第五句：

int v = cur->to;

得到：当前邻居是谁

例如：

u=0

↓

1

得到：v=1

第六句：

if(!visited[v])

表示：没访问过

继续DFS

否则：

跳过

避免死循环。

最后：

cur = cur->next;

表示：

继续看下一个邻居

8. 完整例子

图：

        0
      /   \
     1     2
    /
   3

邻接表：

adj[0]

↓

1

↓

2

↓

NULL

adj[1]

↓

3

↓

NULL

开始：

dfs(0)

第一次：

visited

1

0

0

0

打印：

0

进入：

dfs(1)

第二次：

visited

1

1

0

0

打印：

0 1

进入：

dfs(3)

第三次：

visited

1

1

0

1

打印：0 1 3

没有邻居。

返回。

回到：dfs(1)结束。

返回：dfs(0)继续：2

进入：

dfs(2)

打印：

0 1 3 2

结束。

最终：

访问顺序
0

↓

1

↓

3

↓

2

9. 树的DFS

树更简单。

因为：没有环

所以：不用：visited[]

例如：

void dfs(struct TreeNode* root)
{
    if(root == NULL)
    {
        return;
    }

    printf("%d ",root->val);

    dfs(root->left);

    dfs(root->right);
}

其实就是：前序遍历

所以：树的DFS

就是递归遍历。
10. 图DFS和树DFS区别

树：

没有环

不用visited

图：

可能有环

必须visited


11. DFS复杂度

邻接表：

每个点访问一次

每条边访问一次

时间：O(V+E)

V：顶点

E：边

空间：递归栈：O(V)

12. DFS固定模板
int visited[MAXN];

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

    //处理当前点

    struct EdgeNode* cur = adj[u];

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

        if(!visited[v])
        {
            dfs(v);
        }

        cur = cur->next;
    }
}

 DFS总结
DFS（Depth First Search）

核心思想：

    一条路走到底

    走不通返回上一层

数据结构：

    系统递归栈（或显式栈）

图：

    必须visited[]

树：

    不需要visited

时间复杂度：

    O(V+E)

模板：

    visited[u]=1

    遍历所有邻居

    没访问继续dfs(v)

应用：

    图遍历
    连通块
    岛屿问题
    回溯
    树遍历