科林算法_3 图

一、图论基础

多对多的关系

定义：G=(V,E) Vertex顶点 Edge边

顶点的集合V={v1,v2}

边的结合E={(v1,v2)}

顶点不用来存储数据，图的重点在于点与点之间的关系

无向图(1,2)

有向图<1,2>

依附：边(v1,v2)依附于顶点v1,v2

路径：（v1,v2)(v2,v3)

无权路径最短：边最少

连通：一个点到另外一个点，有路径可通

无向图的连通图：图中任意两点之间均有路径连通

有向图的强连通图：任意相异成对顶点之间均有路径可通

子图

极大连通子图（连通分量/强连通分量）

完全图：图中所有的边均存在

无向完全图边数：Cn2=n(n-1)/2

有向完全图边数：An2=n(n-1)

简单图：没有指向自己的路径

简单路径：除起点和终点可以相同，其他点不可重复

度：几条邻接关系，最多n-1

有向图：入度、出度

n个顶点无向图中，最少n-1条边，可以是连通图

n个顶点无向图中，最少C(n-1)2 + 1条边，一定是连通图

二、图的存储结构

2.1 邻接矩阵

二维数组，存储顶点之间的边关系

唯一的

适合边多，稠密图

2.2 邻接链表

不唯一，表示与表头顶点连接

适合边少，稀疏图

结构体：

（1）顶点个数

（2）边的条数

（3）邻接矩阵 

创建链表：

① 顶点个数

② 矩阵申请

③ 放边（a,h）矩阵对应行列赋值

#include<iostream>
using namespace std;

#define M 10

typedef struct node {
	int nVertex;
	int nEdge;
	int matrix[M][M];	//邻接矩阵
}Graph;

Graph* CreateGraph() {
	//结构体
	Graph* pGraph = (Graph*)malloc(sizeof(Graph));
	int nV, nE;
	printf("请输入顶点个数与边的条数:\n");
	cin >> nV >> nE;
	pGraph->nVertex = nV;
	pGraph->nEdge = nE;
	memset(pGraph->matrix, 0, sizeof(int) * M * M);

	//放边
	int va, vb;
	for (int i = 0; i < nE; i++) {
		printf("请输入两个顶点确定一条边:\n");
		cin >> va >> vb;
		if (va >= 1 && va <= nV && vb >= 1 && vb <= nV && va != vb && pGraph->matrix[va - 1][vb - 1] == 0) {
			pGraph->matrix[va - 1][vb - 1] = 1;
			pGraph->matrix[vb - 1][va - 1] = 1;
		}
		else i--;
	}
	return pGraph;
}

int main() {
	Graph* pGraph = CreateGraph();
	for (int i = 0; i < pGraph->nVertex; i++) {
		for (int j = 0; j < pGraph->nVertex; j++) {
			cout << pGraph->matrix[i][j] << ' ';
		}
		cout << endl;
	}
}

三、图的遍历

3.1 回溯法 BackTracking

回溯树（树不仅是存储结构，也是分析过程）：横向循环(Loop)，纵向递归

回溯本身是一种暴力解法，有些时候暴力是问题的唯一解

应用：子集问题、集合集合、排列问题、棋盘问题、迷宫问题

void BackTracking(参数(传入|传出)){
    if(结束条件){
        结果收集;
        return;
    }
    for(当前的可能性){
        选择/处理其中一个可能性;
        BackTracking(下一层);
        撤销当前的选择;
    }
}

例：全排列

LCR 083. 全排列 - 力扣（LeetCode）

LCR 084. 全排列 II - 力扣（LeetCode）

3.2 深度优先遍历 DFS

（1）标记数组

（2）遍历

① 打印顶点

② 标记

③ 遍历邻接点，找到邻接且未打印的顶点处理

void DFS(Graph* pGraph, int x, bool* pVis) {
	cout << x << ' ';
	pVis[x - 1] = 1;
	for (int i = 0; i < pGraph->nVertex; i++) {
		if (pGraph->matrix[x - 1][i] && pVis[i] == 0) {
			DFS(pGraph, i + 1, pVis);
		}
	}
}

void MyDFS(Graph* pGraph, int x) {
	//标记数组
	bool* pVis = (bool*)malloc(sizeof(bool) * pGraph->nVertex);
	memset(pVis, 0, sizeof(bool) * pGraph->nVertex);

	DFS(pGraph, x, pVis);

	//释放空间
	free(pVis);
	pVis = nullptr;

}

3.3 广度优先遍历 BFS

（1）辅助队列

（2）标记数组

（3）起始顶点入队、标记

（4）遍历

① 弹出队首

② 打印队首顶点

③ 遍历队首顶点邻接点且未标记的入队并标记

void BFS(Graph* pGraph, int x) {
	//标记数组
	bool* pVis = (bool*)malloc(sizeof(bool) * pGraph->nVertex);
	memset(pVis, 0, sizeof(bool) * pGraph->nVertex);

	queue<int> q;
	pVis[x - 1] = 1;
	q.push(x - 1);

	while (!q.empty()) {
		x = q.front();
		cout << x + 1 << ' ';
		q.pop();
		for (int i = 0; i < pGraph->nVertex; i++) {
			if (pGraph->matrix[x][i] && !pVis[i]) {
				q.push(i);
				pVis[i] = 1;
			}
		}
	}
	cout << endl;
	//释放空间
	free(pVis);
	pVis = nullptr;
}

四、图的应用

4.1 最短路径问题 Dijkstra

使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题（得到一个点到其他各个点的最短路径），算法最终得到一个最短路径树。

最短路？有权图：路径上权值和最小。无权图：经过的边数最少

贪心的思想：只关心下一步的最优选择，不考虑后续

每次从 「未求出最短路径的点」中 取出 距离距离起点 最小路径的点，以这个点为桥梁 刷新「未求出最短路径的点」的距离

最短路径问题---Dijkstra算法详解-CSDN博客

4.2 最小生成树

4.2.1 Kruskal 稀疏图

Kruskal首先将所有的边按从小到大顺序排序，并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合（环），就跳过。直到选取了n-1条边为止。

利用贪心的思想通过并查集来求最小生成树，依次选择不会构成环路的最小的边加入

4.2.2 Prim 稠密图

1. 建立边set用来存放结果，建立节点set用来存放节点同时用于标记是否被访问过，建立边的最小堆
2. 开始遍历所有节点，如果没有访问，则添加到节点set，然后将其相连的边入堆。
3. 从堆中取最小的边，然后判断to节点是否被访问过，如果没有，将这个边加入生成树（我们想要的边），并标记该节点访问。
4. 然后将to节点所相连的边添加到最小堆中，不然这个网络就不会向外扩展了（这个步骤是必须的）。
5. 循环上面的操作，直到所有的节点遍历完。

4.3 二部图

G=(U,V,E)

U,V顶点集合，E边：集合和集合之间存在边关系，集合内部无边关系

染色法，区分一个图是否是二部图
 

4.4 拓扑排序

例：魔法天女

课程表选课问题：图的拓扑排序

1.数据集A100个元素，数据集B500个整数对，依照B对A排序

2.游戏模块加载

拓扑排序(Topolopical)：为一个项目内具备依赖关系的活动求得可以执行的线性顺序

拓扑排序为有向无环图(DAG)服务，只有DAG才有拓扑排序

顶点代表活动，边表示活动间的依赖关系

AOV网不一定是DAG，DAG是AOV网

AOE

验证DAG、求拓扑序列

（1）计算顶点入度

（2）入度为0的顶点入队

（3）出队

（4）邻接点入度更新

（5）入度为0顶点入队