王道408---DS---图-526互联

图有关的概念

1、连通图、连通分量是相对于无向图说的，而强连通图、强连通分量是相对于有向图说的

2、生成树，连通图的生成树是包含图中全部顶点的一个极小连通子图。若砍去一条边，则一定变得非连通

3、极大连通子图与极小连通子图，极小连通子图就是生成树，极大连通子图就是无向图的连通分量

极大要求包含该连通子图的所有边，极小要求保持连通且边最小

连通图的连通分量/极大连通子图就是它自己

4、简单路径、简单回路:

在路径序列中，顶点不重复出现的路径称为简单路径。

除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

图的存储

一般有四种方法---邻接矩阵法、邻接表法、十字链表法、邻接多重表，常用的只有前两种

邻接矩阵法

#define N 8  		//顶点数目的最大值，根据题目要求自己定义
typedef struct{
	char vex[N];	//N个顶点信息，每个顶点存储一个char字符，可根据题目要求将char改为其他类型
    int weight[N][N];	//N*N邻接矩阵，每条边的权值用int变量表示
	int vexnum,arcnum; 	//图的当前顶点数和弧数
}MGraph;

需要注意的是

1、无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储。

2、稠密图适合使用邻接矩阵的存储表示。

3、

邻接表法

#define N 8		//图中顶点数目的最大值，根据题目要求自己定义
typedef struct ArcNode{			//弧结点
	int vexIndex;				//该弧所指向的顶点编号
    int weight;                //该弧的权值
	struct ArcNode *next;		//指向下一个弧结点
}ArcNode; 

typedef struct VNode{	//顶点结点
	char data; 			//顶点信息，每个顶点存储一个char字符，可根据题目要求将char改为其他类型
	ArcNode *first; 	//指向第一条依附该顶点的弧的指针
}VNode;

typedef struct{
	VNode vex[N];    		//N个顶点
	int vexnum,arcnum; 		//图的顶点数和弧数
} ALGraph;

对于稀疏图，采用邻接表存储比较好

求度的时候需要遍历整个邻接表，为此引出了十字链表法:

十字链表法

十字链表法用于有向图

之前写过一篇:

https://www.cnblogs.com/lordtianqiyi/p/17739953.html

邻接多重表

邻接多重表的画法

比我想象中的简单

https://www.bilibili.com/video/BV1Ae41137Jd/?spm_id_from=333.337.search-card.all.click&vd_source=87f7ad8544d4c3ad070c5c2ff28b7698

https://www.bilibili.com/video/BV1TL411b7V3/?spm_id_from=333.337.search-card.all.click&vd_source=87f7ad8544d4c3ad070c5c2ff28b7698

1、写出所有的边的关系

2、先画出顶点以及边

3、链接

边的第二个数据项ilink代表指向下一条依附于顶点ivex的边

第四个数据项jlink指向下一个依附于顶点jvex的边

图的遍历

BFS

类似于二叉树的层序遍历

Dijkstra、prim算法就使用到了广度优先的思想

空间复杂度: O(V)

时间复杂度: O(V+E) // 邻接表法或 O(V^2) // 邻接矩阵法

BFS---广度优先生成树

DFS

类型于二叉树的先序遍历

需要一个递归的栈，空间复杂度为O(V)

邻阶矩阵的时间复杂度是O(V^2)

邻阶表的时间复杂度是O(V+E)

深度优先遍历还可以判断是否存在回路

DFS---深度优先生成树

Prim算法

MST，最小生成树

类似于Dijkstra算法

适合求稠密图的MST

时间复杂度： O(V^2)

Kruskal算法

时间复杂度:O(ElogE)

适合求边稀疏顶点多的图的MST

Dijkstra算法求单源最短路径

不适用于负权值

时间复杂度为O(V^2)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=520;
int n,m;
int g[N][N];    // 存储点到点的距离，即边 ，或者说邻接矩阵 
int dist[N];    // 存储点到原点的距离
bool st[N];        // 标记是否确定了最短路径 

int dijkstra(){
    memset(dist,0x3f,sizeof dist);                            // 为最后的 if(dist[n]==0x3f3f3f3f) return -1;   做铺垫 
    dist[1]=0;                                                // 注意，这里 dist 是从1开始计数的 !!!
    for(int i=0;i<n;i++){    
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j] && (t==-1 || dist[t]>dist[j]))        // 找到距离原点最短距离的点   ，并附加标记   // 有点贪心的思想 
                t=j;
            
        st[t]=true;　　　　　　　　　　　　　　　　　　　　　　　　// 附加标记，即最短路径点，收录到最短路径中
        for(int j=1;j<=n;j++) 
            dist[j] = min(dist[j],dist[t]+g[t][j]);            //依次更新每个点所到相邻的点路径值 // dist[t] <=> 0->t | g[t][j] <=> t->j |  ===>  dist[t]+g[t][j] <=> 0->j
    }
    
    if(dist[n]==0x3f3f3f3f) return -1;  
    return dist[n]; 
}

int main(){
    cin >> n >> m;
    memset(g,0x3f,sizeof g);                                // 为 g[a][b] = min(g[a][b],x); 做铺垫 
    while(m--){
        int a,b,x;
        scanf("%d%d%d",&a,&b,&x);
        g[a][b] = min(g[a][b],x);
    }
    
    int t=dijkstra();
    printf("%d\n",t);
    
    return 0;
}

Dijkstra 算法思路

1、每次从未标记的节点中选择距离出发点最近的节点，标记，收录到最优路径集合中。

2、计算刚加入节点A的邻近节点B的距离（不包含标记的节点）

若（节点A的距离+节点A到节点B的边长）<节点B的距离，就更新节点B的距离和前面点。

3、反复循环

Floyd算法求多源最短路径

时间复杂度为O(V^3)

算法思想：

floyd 算法遍历每个点，每个点都会找到从该点到其他所有点的最短路径，我们从一个点来入手研究，比如我们选取点 0
选取点 0后，遍历除0外的所有点，每遍历一个点就把该点作为中轴节点x，并比较所有的A[i][x] + A[x][0] 与 A[i][0]的大小，若前者小，则更新A_i中最短路径的大小，且更新 Path_i中的记录的中轴节点

Path_i 表的作用: 这个表记录所有最短路径的中轴节点如" Path[0][2] = 3" 代表的含义是: A[0][2] > A[0][3] + A[3][2] ，也就是说以3为转轴的时候节点0到2 的直接距离小于先从 0到3，再从3到2的距离和

当然，上图中是已经比较后且修改过的图，下图是比较前的图:

/*
 * floyd最短路径。
 * 即，统计图中各个顶点间的最短路径。
 *
 * 参数说明：
 *        G -- 图
 *     path -- 路径。path[i][j]=k表示，"顶点i"到"顶点j"的最短路径会经过顶点k。
 *     dist -- 长度数组。即，dist[i][j]=sum表示，"顶点i"到"顶点j"的最短路径的长度是sum。
 */
void floyd(Graph G, int path[][MAX], int dist[][MAX])
{
    int i,j,k;
    int tmp;

    // 初始化
    for (i = 0; i < G.vexnum; i++)
    {
        for (j = 0; j < G.vexnum; j++)
        {
            dist[i][j] = G.matrix[i][j];    // "顶点i"到"顶点j"的路径长度为"i到j的权值"。
            path[i][j] = j;                 // "顶点i"到"顶点j"的最短路径是经过顶点j。
        }
    }

    // 计算最短路径
    for (k = 0; k < G.vexnum; k++)
    {
        for (i = 0; i < G.vexnum; i++)
        {
            for (j = 0; j < G.vexnum; j++)
            {
                // 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和path[i][j]
                tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]);
                if (dist[i][j] > tmp)
                {
                    // "i到j最短路径"对应的值设，为更小的一个(即经过k)
                    dist[i][j] = tmp;
                    // "i到j最短路径"对应的路径，经过k
                    path[i][j] = path[i][k];
                }
            }
        }
    }

    // 打印floyd最短路径的结果
    printf("floyd: \n");
    for (i = 0; i < G.vexnum; i++)
    {
        for (j = 0; j < G.vexnum; j++)
            printf("%2d  ", dist[i][j]);
        printf("\n");
    }
}

这个算法还是比较简单的，需要注意的是，floyd算法每次选取一个中介点，然后进行两重循环