图算法总结

图算法(数组版)

1.1最短路径Dijkstra算法:

• 假设顶点是$V_0到V_5$ 六个点，开始时候是没有连线的，但是已知能互相到达的顶点之间的边权。
• 步骤是每次从顶点0开始查找，找出距离顶点最短的点，然后标记该点为true,再查询该点能直达的其他点加上边权会不会比原先记录的距离值小—->即更新最短距离；遍历完了所有从该点能到的点后再次回到起点。

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXV=1000;
const int INF = 1000000000;//很大的数九位0

int n,m,s,G[MAXV][MAXV];//n为顶点数量，m为边数，s为起点
int d[MAXV];//起点到各点的最短路径长度
bool vis[MAXV]={false}; //标记访问数组 false为没有访问，true 为访问过
/*本题输入:
6 8 0 //6个顶点  8条边  起点为0号
0 1 1 从0点到1点距离为1
0 3 4
0 4 4
1 3 2
2 5 1
3 2 2
3 4 3
4 5 3
*/
void Dijkstra(int s){
    fill(d,d+MAXV,INF); 
    d[s]=0; //初始化操作
    for(int i=0;i<n;i++){//每次更新完都要回到起点,循环n次
        int u=-1,MIN=INF; //比较下面，u使得d[u]最小，MIN存放该最小的d[u]
        for(int j=0;j<n-1;j++){
            if(vis[j]==false && d[j]<MIN){
                u = j;
                MIN = d[j];
            }
        }
        if(u == -1) return;//剩下的顶点和起点s不通
        vis[u]= true;//找出距离起点最短的点 u
        for(int v=0;v<n;v++){//从 u 开始走，更新最短距离
            if(vis[v]==false && G[u][v]!=INF && d[u]+G[u][v]<d[v]){//G[u][v]是从u到v顶点的直通距离
                d[v]=d[u]+G[u][v];
            }
        }
    }
}
int main(){
    int u,v,w;
    cin>>n>>m>>s;
    fill(G[0],G[0]+MAXV*MAXV,INF);
    for(int i=0;i<m;i++){
        cin>>u>>v>>w;
        G[u][v]=w;
    }
    Dijkstra(s);
    for(int i=0;i<n;i++){
        cout<<d[i];//输出结果最短路径
    }
    return 0;
}

1.2基本模板

//初始化
for(循环n次){
    u = 使得d[u]最小且还未被访问的顶点的标号;
    记u已被访问;
    for(从u出发能到达的所有顶点v){
        if(v未被访问 && 以u为中介点使s到顶点v 的最短距离d[v]更优){
            优化d[v];
       }

2.1图的存储

树与图的存储

树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。

(1) 邻接矩阵：g[a][b] 存储边a->b

(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);

2.2树与图的遍历

时间复杂度O(n+m),n表示点数，m表示边数

(1)深度优先遍历

int dfs(int u)
{
    st[u] = true;
    for(int i = h[u];i!= - 1;i = ne[i])
    {
        int j = e[i];
        if(!st[j])	dfs(j);
    }
}

(2)宽度优先遍历

queue<int> q;
st[1] = true;
q.push(1);
while(q.size())
{
    int t = q.front();
    q.pop();
    for(int i = h[t];h!=-1;i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            st[j] = true;
            q.push(j);
        }
    }
}

3.朴素$dijkstra$算法

时间复杂是 $O(n^2+m)$, n 表示点数，m 表示边数

算法设计：贪心

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

4.$Bellman-Ford$算法

单源最短路径算法

对于带权有向图 G = (V, E)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford 算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。

设计：动态规划

时间复杂度：$O(V*E)$ 顶点数 边数, $n顶点数，m边数$

理解：对所有边进行$n-1$次松弛操作,因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1条边，

换句话说，第1轮在所有边进行松弛后，得到的是源点最多经过1条边到达其他顶点的最短距离；

第2轮在对所有的边进行松弛后，得到的是源点最多经过2条边到达其他顶点的最短距离；

算法描述：

1、$dist[N]$数组表示源顶点到所有顶点的距离，初始化为$infinte$,$dist[1][1]=0$,

2、计算最短路径，执行$V-1$次遍历

对于图中的每条边：如果起点u的距离d加上权值w小于终点v的距离，更新终点v的距离值d

$if(dist[b]>dist[a]+w) dist[b]=dist[a]+w$

例如以下加上一个拷贝数组就可以求最多经过k条边的最短距离

int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离
int backup[N]; // 拷贝数组,这样就保证轮数与边数一致
struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
	
    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        memcpy(backup,dist,sizeof dist);
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > backup[a] + w)
                dist[b] = backup[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

判断是否有负权环，再对边进行一次额外的遍历，如果还能更新说明仍然存在一条边使得两点距离更短，事实上再更新多次还是有更新的情况。

5、$SPFA$算法

时间复杂度 平均情况下 $O(m)$，最坏情况下 $O(nm)$, n 表示点数，m 表示边数

$SPFA算法$是对上面的$bellman_ford$算法的队列优化

算法描述：首先建立一个队列，初始队列里只有起始点，建立一个表格记录起始点到所有点的最短路径(初始值赋为极大值)，然后进行松弛操作，依次用队列中的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把其加入到队列中。

求负环：如果某个点进入队列的次数超过N次则存在负环(N为图的顶点数)

int n; // 总点数
int h[N],w[N],e[N],ne[N],idx; // 邻接表存储所有边
int dist[N];
bool st[N];// 存储每个点是否在队列中
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    // 取出队列中的一个元素来更新距离
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        
        st[t] = false; // 先弹出队列标记为false，因为后面可能还会有更新
        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t]+w[i])
            {
                 // 先更新最短距离 
                dist[j] = dist[t] + w[i];
                // 如果被更新的点不在队列中，就要加入，因为后面需要用到其最短值
                if(!st[j])
                {
                    q.pusj(j);
                    st[j] = true;
                }
            }
        }
    }
     if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

5、$Floyd$算法

$Floyd$算法属于暴力求解，时间复杂度$O(n^3)$,$n$表示点数

// 初始化
	for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
        {
            d[i][j] = (i == j ? 0 : INF);
        }

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}