kruskal算法和深度优先搜索

第一章 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)

应用：

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