图论算法总结

2022/11/2-------2022/11/3

目录

文章目录

1.图的存储

1.1邻接矩阵

1.2邻接表

2.最短路算法

2.1   Dijkstra算法

2.2   spfa算法

2.3   Floyd算法

3.最小生成树算法

3.1    Prim算法

3.2    Kruskal算法

---

1.图的存储

1.1邻接矩阵

g[a][b] = c;
a 到 b 路上权值是c

1.2邻接表

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
 
// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
 
// 初始化
idx = 0;
memset(h, -1, sizeof h);
 
//遍历点t的所有边
for(int i = h[t];i != -1;i = ne[i]){
    //取出这点的元素
    int j = e[i];
    //进行其他操作即可
}

2.最短路算法

        2.1   Dijkstra算法

                        朴素版Dijkstra算法_星河边采花的博客-CSDN博客

        2.2   spfa算法

                        spfa算法（Bellman-Ford算法改进）_星河边采花的博客-CSDN博客

        2.3   Floyd算法

                        Floyd求最短路_星河边采花的博客-CSDN博客

3.最小生成树算法

        3.1    Prim算法

                        Prim算法求最小生成树_星河边采花的博客-CSDN博客

        3.2    Kruskal算法

                        Kruskal算法求最小生成树_星河边采花的博客-CSDN博客