图

图G由顶点集 和边集 组成，记为

图的顶点集 一定非空，但是边集 可以为空。

简单图：

  1. 不存在重复边
  2. 不存在顶点到自身的边

子图

设由两个图 和 ,若是的子集，且 是 的子集，，则称 是的子图。若子图顶点和原图顶点相同，该子图被称为生成子图。

连通图

在无向图中，若从顶点 到顶点 有路径存在，则称 和 是连通的。若图 任意两个顶点都是连通的，则 是连通图。

无向图中的极大连通子图称为连通分量。

有向图中，如果一对顶点、，有到和 到之间都有路径，则称两个顶点为强连通的。若图中任意一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有n-1条边。

顶点的度

无向图中的全部顶点的度之和等于边数的2倍。

有向图的度数之和=入度和+出度和

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

一个顶点的入度为0，其余顶点的入度均为1的有向图称为有向树。

图的存储

  1. 邻接矩阵

    无向图的邻接矩阵是对称的

  2. 邻接表法

  3. 十字链表（有向图）

弧结点
tailvex headvex hlink tlink (info)
顶点结点
data firstin firstout

tailvex、headvex分别存放了弧尾和弧头这两个顶点的编号

hlink指向弧头相同的下一个弧结点，tlink指向弧尾相同的下一个弧结点

firstin、firstout指示以该顶点为弧头、弧尾的第一个弧结点。

  1. 邻接多重表（无向图）
邻接矩阵 邻接表 十字链表 邻接多重表
空间复杂度 $O( V ^2)$ 无向图：$O( V +2 E )有向图：O( V + E )$ $O( V + E )$ $O( V + E )$
找相邻边 $O( V )$ 遍历整个邻接表 方便 方便

图的遍历

  1. 广度优先算法
    1. 空间复杂度
    2. 邻接表的复杂度为
    3. 邻接矩阵的复杂度为
  2. 深度优先算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void DFS（Graph G){
    for(int i=0;i<G.vexnum;i++){
        visited[i]=FALSE;
    }
    for(int i=0;i<G.vexnum;i++)
        if(!visited[i])	 // 		防止一次遍历不完
            DFS(G,i);
}
void dfs(MGraph G,int i){
    visit(i);
    visited[i]=True;
    for(j=0;j<G.vexnum;j++){
        if(visited[j]==FALSE && G.edge[i][j]==1){
            dfs(G,j);
        }
    }
}

时间和空间复杂度和BFS一样

图的应用

最小生成树（MST）

  1. 最小生成树不唯一，但是对应边的权值之和是唯一的，而且是最小的。
  2. 最小生成树的边数为顶点数-1
  3. 当各边权值是不一样的情况下，最小生成树是唯一的。

Prim算法

  1. 输入：一个加权连通图，其中顶点)集合为 𝑉，边集合为 𝐸 ；

  2. 初始化： 𝑉new={𝑥} ，其中 𝑥 为集合 𝑉 中的任一节点（起始点）, 𝐸new={} ；

  3. 重复下列操作，直到 𝑉new=𝑉 ：

    1. 在集合 𝐸 中选取权值最小的边 (𝑢,𝑣) ，其中 𝑢 为集合 𝑉new 中的元素，而 𝑣 则是 𝑉 中没有加入 𝑉new 的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
    2. 将 𝑣 加入集合 𝑉new 中，将 (𝑢,𝑣) 加入集合 𝐸new 中；

  5. 输出：使用集合 𝑉new 和 𝐸new 来描述所得到的最小生成树。

初始化：找一个点

循环找一个集合中的点最近的边，且该边的另外一个顶点目前不在生成树中，则加入该点

直到所有的点都加进来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void prim()
{
    int sum=0;
    memset(d,0x3f,sizeof d);        //初始化
    d[1]=0;
    for(int i=0;i<n;i++)        //循环n次
    {
        int t=0;
        for(int j=1;j<=n;j++)       //找出距离连通部分距离最小的顶点
            if(!st[j] and (d[j]<d[t] or !t))    
                t=j;
        st[t]=1;        //将该点加入连通部分
        sum+=d[t];      
        if(d[t]==INF)       //如果距离连通部分距离最小的顶点距离仍然是INF就说明图不连通，跳出循环。
        {
            cout<<"impossible"<<endl;
            return;
        }
        for(int j=1;j<=n;j++)       //遍历该点的所有的边，更新距离
            if(!st[j] and d[j]>g[t][j])
                d[j]=g[t][j];
    }
    cout<<sum<<endl;
}                 
//原文链接：https://blog.csdn.net/yourgrandfather_/article/details/135026901

Kruskal算法

初始化每条边都是一个连通分量。

循环找最小权重的边，若该边对应的两个顶点在不同的两个连通分量中，就把这个边加入最小生成树

直到最后是一个连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
struct edge
{
	int u, v;
	int weight;
};
vector<int> father; //记录每个节点的父亲
vector<int> result; //存储最后获得的各条边

bool compare(edge a, edge b)
{
	return a.weight < b.weight;
}

int findfather(int a)
{
	while (a != father[a])
	{
		a = father[a];
	}
	return a;
}
void kruskal(int n, vector<edge> Edge)
{
	father.resize(n);
	sort(Edge.begin(), Edge.end(), compare);
	for (int i = 0; i < n; ++i)
	{
		father[i] = i;
	}
	for (int i = 0; i < Edge.size() && result.size() < n-1; ++i)
	{
		int u = Edge[i].u;
		int v = Edge[i].v;
		if (findfather(u) != findfather(v)) //判断父节点是否相同
		{
			result.push_back(Edge[i].weight);
			father[findfather(u)] = father[findfather(v)]; //将两点并入一个集合中
		}
	}
	if (result.size() != n - 1)
	{
		cout <<  result.size()  << "该图不连通" << endl;
		return;
	}
	else
	{
		cout << "最小生成树的各边如下：" << endl;
		for (int i = 0; i < result.size(); ++i)
		{
			cout << result[i] << endl;
		}
	}
}                        
// 原文链接：https://blog.csdn.net/qq_46027243/article/details/108903948

最短路径

dijstra算法

  1. 初始化：选出第一个结点到，计算出所有其他点到该点的最小距离（点都在里面）。
  2. 从 里面选出到起点最近的那个点
  3. 根据已经加入的点来修改点最近距离
  4. 重复次该操作，直到所有顶点都包含在集合中

Floyd算法

可以计算负权值路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void Graph_DG::Floyd() {
    int row = 0;
    int col = 0;
    for (row = 0; row < this->vexnum; row++) {
        for (col = 0; col < this->vexnum; col++) {
            //把矩阵D初始化为邻接矩阵的值
            this->dis[row][col] = this->arc[row][col];
            //矩阵P的初值则为各个边的终点顶点的下标
            this->path[row][col] = col;
        }
    }

    //三重循环，用于计算每个点对的最短路径
    int temp = 0;
    int select = 0;
    for (temp = 0; temp < this->vexnum; temp++) {
        for (row = 0; row < this->vexnum; row++) {
            for (col = 0; col < this->vexnum; col++) {
                //为了防止溢出，所以需要引入一个select值
                select = (dis[row][temp] == INT_MAX || dis[temp][col] == INT_MAX) ? INT_MAX : (dis[row][temp] + dis[temp][col]);
                if (this->dis[row][col] > select) {
                    //更新我们的D矩阵
                    this->dis[row][col] = select;
                    //更新我们的P矩阵
                    this->path[row][col] = this->path[row][temp];
                }
            }
        }
    }
}

                        
// 原文链接：https://blog.csdn.net/qq_35644234/article/details/60875818

有环无向图：DAG

拓扑排序

AOV网： $\Large 表示活动V_i必须在V_j$之前完成，这样的有向图称为AOV网，顶点表示活动的网络

活动不能为自己的前驱或者后继

拓扑排序：

  1. 每个顶点都出现且只出现一次
  2. 若顶点在序列中排在顶点前面则在图中不存在从B到A的路径

找方式：

  1. 从AOV网中找一个每前驱的顶点并输出
  2. 从网中删除该顶点和所有以它为起点的有向边
  3. 重复1和2直到当前的AOV网为空或者当前网中不存在无前驱的顶点为止。后一种情况说明，有向图中一定存在环。
dfs实现拓扑排序的思想
  1. 若u是v的祖先，在dfs设置一个时间标记，在dfs结束时，对各结点记时，祖先的结束时间一定晚于子孙的时间。
  2. 没路径关系则u和v在拓扑序列的关系任意
AOV性质
  1. 只有在某个顶点所代表的时间发生后，从该顶点出发的各有向边所代表的活动才能开始
  2. 只有在进入某个顶点的各有向边所代表的活动都结束时，该顶点所代表的事件才能发生

关键路径

具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动。

  1. 事件最早发生时间
  2. 事件最晚发生时间
  3. 活动最早发生时间（边）
  4. 活动最晚开始时间

只有加快那些包含在所有关键路径上的关键活动才能达到缩短工期的目的。

Dijstra Floyd Prim Kruskal
邻接矩阵
邻接表
DFS BFS 拓扑排序 关键路径
邻接矩阵
邻接表