基础算法小结:

一.图论和搜索

1. DFS

void dfs(int a)
{
    出口条件 //一般是 递归层数 == 需要的数量

    for循环n次
    {
        设置状态;
        dfs(下一层);
        恢复状态;
    }
}

2.BFS (用到队列)

int BFS()
{
    初始化队列,起点信息,起点入队;

    while(队列不空)
    {
        出队一个

        具体操作....
    }
    return 最短距离
}

3.朴素dijkstra算法:

int dijkstra(){
    初始化dist数组为0x3f;
    置起点dist为0;
    遍历n次,每次更新一个点的最短值
    {
        for循环,找出dist 最短的点;

        将最短的点的st置true;

        for循环,遍历所有点,更改dist的值;

    }
    如果dist终点为0x3f3f3f3f, 则没有路径
    否则输出;

}

4.prim最小生成树 (类比dijkstra)

int prim()
{
    初始化dist数组为无穷
    初始化最小距离res = 0;
    for //迭代n次,每次更新一个点
    {
        for循环选一个离集合最近的点t

        if(此时不是第一个点 && 距离为无穷)  reuturn -1 // 代表有个点没有到集合的边,也就没有生成树

        if(此时不是第一个点) 更新最小距离res

        for循环,更新其他店到集合的距离
            d = min(d, 到t的权值)   

        把t加入集合
    }
    return res;
}

5. kruskal最小生成树

定义一个结构体
{
    顶点a,顶点b,a->b的权值
}

将边的权值从小到大排序

初始化并查集

for循环m次  // 因为一次添加一条边, 一共有m条边
{
    用并查集的find 查找a,b的祖宗
    if(a,b的祖宗不相等)     //说明他们不连通
    {
         合并并查集
         更新路径长度
         边数+1
    }
}