算法学习dijkstra,dfs,bfs,查并集

dijkstra算法

dijkstra算法是一种用于解决单源最短路径问题的算法，即从一个顶点到其他所有顶点的最短路径。

dijkstra算法的基本思想是：从源点开始，每次选择距离源点最近的顶点，将其加入到已访问的顶点集合中，然后更新其他顶点的距离。

dijkstra算法的时间复杂度为O(n^2)，其中n为顶点数。

算法步骤

1. 初始化距离数组dist，dist[i]表示源点到顶点i的最短距离，初始时dist[i]为无穷大，dist[source]为0。
2. 初始化已访问顶点集合visited，初始时visited为空。
3. 重复以下步骤n次（n为顶点数）：
   1. 从距离数组dist中选择距离源点最近的顶点u(使用优先队列)，将其加入到已访问顶点集合visited中。
   2. 更新其他顶点的距离(根据题目,有不同的更新方式)：如果顶点v未被访问，且通过u到达v的距离小于当前dist[v]，则更新dist[v]为通过u到达v的距离。
4. 最终dist数组中的值即为源点到其他所有顶点的最短距离。

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

const int N = 100;
const int INF = 100000;

int p[N][N], d[N], path[N];//存放结点，距离，路径

void dijkstra(int bgn, int n){
    int i,j,min,min_num;
    int mark[N] = {0};//标记数组
    for(i=1;i<=n;i++){
        d[i] = p[bgn][i];
    }
    mark[bgn] = 1;
    d[bgn] = 0;

    for(i=1;i<n;i++){
        min = INF;
        for(j=1;j<=n;j++){
            //寻找距离目标点最近且没有别寻找过的点
            if(mark[j] == 0 && d[j]<min){
                min = d[j];
                min_num = j;
            }
        }
        mark[min_num] = 1;//修改标记点
        for(j=1;j<=n;j++){
            //更新距离
            if(mark[j] == 0 && d[j] > d[min_num] + p[min_num][j]){
                d[j] = d[min_num] + p[min_num][j];
                path[j] = min_num;
            }
        }
    }
}

void print(int bgn, int n)       //bgn为出发节点，n表示图中节点总数
{
    int i, j;
    stack<int> q;               //由于记录的中途节点是倒序的，所以使用栈（先进后出），获得正序
    for (i = 2; i <=n; i++)            //打印从出发节点到各节点的最短距离和经过的路径
    {
        j = i;
        while (path[j] != -1)      //如果j有中途节点
        {
            q.push(j);          //将j压入堆
            j = path[j];          //将j的前个中途节点赋给j
        }
        q.push(j);
        cout << bgn << "=>" << i <<" length:"<< d[i]<<" path  " << bgn;
        while (!q.empty())       //先进后出,获得正序
        {
            cout << q.top();
            //printf("%d ", q.top());//打印堆的头节点
            q.pop();            //将堆的头节点弹出
        }
        printf("\n");
    }
}

dfs算法(深度优先搜索)

dfs算法是一种用于遍历或搜索树或图的算法。

dfs算法的基本思想是：从起始顶点开始，每次选择一个未被访问的邻接顶点，将其加入到已访问的顶点集合中，然后递归地访问该顶点的未被访问的邻接顶点。

dfs算法的时间复杂度为O(n+m)，其中n为顶点数，m为边数。

算法步骤

1. 初始化已访问顶点集合visited，初始时visited为空。
2. 从起始顶点开始，执行以下步骤：
   1. 如果当前顶点未被访问，则将其加入到已访问顶点集合visited中。
   2. 递归地访问当前顶点的未被访问的邻接顶点。
3. 重复步骤2，直到所有顶点都被访问。

bfs算法(广度优先搜索)

bfs算法是一种用于遍历或搜索树或图的算法。

bfs算法的基本思想是：从起始顶点开始，每次选择距离源点最近的顶点，将其加入到已访问的顶点集合中，然后递归地访问该顶点的未被访问的邻接顶点。

bfs算法的时间复杂度为O(n+m)，其中n为顶点数，m为边数。

算法步骤

1. 初始化已访问顶点集合visited，初始时visited为空。
2. 从起始顶点开始，执行以下步骤：
   1. 如果当前顶点未被访问，则将其加入到已访问顶点集合visited中。
   2. 将当前顶点的未被访问的邻接顶点加入到队列中。
3. 重复步骤2，直到所有顶点都被访问。

dfs和bfs的区别

1. dfs是一种递归算法，而bfs是一种非递归算法。
2. dfs的搜索顺序是深度优先，而bfs的搜索顺序是广度优先。

查并集算法

查并集算法是一种用于处理不相交集合的数据结构。

查并集算法的基本操作包括：查找（find）和合并（merge）。

查找操作用于确定一个元素属于哪个集合，合并操作用于将两个集合合并为一个集合。

算法步骤

1. 初始化每个元素的父节点为自身，表示每个元素都是一个独立的集合。
2. 查找操作：对于一个元素x，递归地查找其父节点，直到找到根节点。
3. 合并操作：对于两个元素x和y，分别查找它们的根节点rx和ry，如果rx和ry不同，则将ry的父节点设为rx，表示将两个集合合并为一个集合。

变式

简单的查并集算法查找和合并操作的时间复杂度较高,可以考虑带秩优化,即将树的高度限制在一个较小的范围内,从而提高查找和合并操作的效率。