图的算法 - 数据结构 | CLee = CL&love = 厚积而薄发，博观而约取。

# 前情提要：

这里的算法只是记录个大致思路，并不能运行（未经过运行测试）

可能存在的部分错误（因为懒加健忘）：

1、忘了在每个结构体的前面加 struct

# 图

# BFS

	// 以邻接表为存储结构的 BFS-- 层次遍历（广度优先遍历）
	//
	//
	#define MAXSIZE 50;

	typedef struct ArcNode
	{
	int adjvex;// 该边所指的节点位置
	struct ArcNode *nextArc;
	int info;
	}ArcNode;

	typedef struct
	{
	char data;
	struct ArcNode *firstArc;
	}VNode;

	typedef struct
	{
	struct VNode *adjlist[MAXSIZE];
	int n;
	int e;
	}AGraph;

	// 访问当前节点

	void Visit(VNode *v){
	printf("当前的顶点为%s\n",v);
	}





	void BFS(AGraph G,int v,int visit[MAXSIZE]){
	//v 表示顶点的起点编号
	int queue[MAXSIZE];//queue 用来存储已被访问过的节点编号
	struct ArcNode *p;
	int front = rear = 0;
	int j;
	rear = (rear+1)%MAXSIZE;
	queue[rear] = v;
	Visti(v);// 访问
	visit[v] = 1;
	while(front!=rear){
	front = (front+1)%MAXSIZE;
	j = queue[front];
	p = G->adjlist[j].firstArc;
	while(p!=NULL){
	if(visit[p]->adjvex){
	Visit(p->adjvex);
	visit[p->adjvex] = 1;
	rear = (rear+1)%MAXSIZE;
	queue[rear] = p->adjvex;
	}
	p->nextArc;
	}
	}
	}
	// 以上是对连通图的遍历，若是对待非连通图

	void gotobfs(AGraph *G){
	int i = 0;
	for(i = 0;i<G->n;i++){
	if(visti[i]==0)// 若当前节点未被访问过
	{
	bfs(G,visit[i],visit);
	}
	}
	}

# DFS

	// 以邻接表为存储结构的 DFS--（前序遍历）-- 深度优先遍历
	#define MAXSIZE 50;

	typedef struct ArcNode
	{
	int adjvex;
	struct ArcNode *nextArc;
	}ArcNode;

	typedef struct
	{
	char data;
	struct ArcNode *firstArc;
	}VNode;

	typedef struct
	{
	struct VNode adjlist[MAXSIZE];
	int n;
	int e;
	}AGraph;

	void Visit(VNode v){

	}

	int visit[MAXSIZE];
	void DFS(AGraph G,int v){
	// 无论是 dfs 还是 bfs 这里的 v 都是表示 VNode 的起点编号；
	Visit(v);
	visit[v] = 1;
	ArcNode *p;
	p = G->adjlist[v]->firstArc;
	while(p!=NULL){
	if(visit[p->adjvex] == 0){
	DFS(G,p->adjvex);
	}
	p = p->nextArc;
	}
	}

	void gotoDfs(AGraph G,int v){
	for(int i=0;i<G->n;i++){
	if(visit[v] == 0){
	DFS(G,v);
	}
	}
	}

# 图的应用

	// 二叉数的深度
	// 主体思路
	// 前序遍历，若该根节点拥有孩子节点则，deepth

	#define MAXSIZE 50
	typedef struct BiNode
	{
	int data;
	int deepth;
	BiNode *lchild;
	BiNode *rchild;
	}BiNode,*BiTree;

	void findDeepth(BiTree bt){
	int d = 0;
	int p = 0;
	BiNode *s = bt;
	if(s!=NULL){
	d = findDeepth(s->lchild);
	if(d>p){
	p = d;
	}
	d = findDeepth(s->rchild);
	if(d>p){
	p = d;
	}
	}
	p = p+1;
	}

	// 无代权值的无向连通图中寻找距离顶点 v 最远的顶点
	// 采用邻接表作为存储结构
	//tips：广度优先遍历。
	#define MAXSIZE 50

	typedef struct ArcNode
	{
	int adjvex;
	ArcNode *nextArc;
	}ArcNode;

	typedef struct
	{
	char data;
	ArcNode *firstArc;
	}VNode;

	typedef struct
	{
	VNode adjlist[MAXSIZE];
	int n;
	int e;
	}AGraph;

	int findTheLongestVex(AGraph G,int v,int visit[MAXSIZE]){
	int j;
	int queue[MAXSIZE],front = rear = 0;
	rear = (rear+1)%MAXSIZE;
	visit[v] = 1;
	queue[rear] = v;
	while(front!=rear){
	front = (front+1)%MAXSIZE;
	j = queue[front];
	p = G->adjlist[j]->firstArc;
	while(p!=NULL){
	if(visit[p->adjvex] == 0){
	visit[p->adjvex] = 1;
	rear = (rear+1)%MAXSIZE;
	queue[rear] = p->adjvex;
	findTheLongestVex(G,p->adjvex,visit);
	}
	}
	p = p->nextArc;

	}
	return j;//visit 数组遍历完后，当前的顶点编号 j 就是最远的点
	}

# 邻接表、邻接矩阵的定义

	// 邻接表和邻接矩阵的结构体定义

	#define MAXSIZE 50;

	// 邻接矩阵 -- 顺序存储结构
	// 主要需要存储的信息如下：
	//1. 具体包含哪些顶点
	//2. 顶点和顶点之间的关系（通过数组下标之间的值来表示，如：顶点 1 和顶点 2 之间存在路径则 A [1][2]=1, 否则 A [1][2]=0）
	// 邻接矩阵的顶点类型定义如下
	typedef struct VertexType
	{
	int no;// 顶点的编号
	char info;// 顶点的其他信息，题目未要求的话，可不写
	}VertexType;

	// 邻接矩阵的图定义
	typedef struct Mgraph
	{
	// 定义一个二维矩阵
	// 需要注意的是：如果要求的是带有权值的节点，则要变成 float edges [MAXSIZE][MAXSIZE]
	int edges[MAXSIZE][MAXSIZE];// 存放顶点和顶点之间的关系
	int n;// 顶点数
	int e;// 边数
	VertexType vex[MAXSIZE];// 存放具体包含哪些顶点
	}Mgraph;



	// 邻接表 -- 链式存储
	// 主要需要存储的信息如下：
	//1. 指向边表节点的边 {或者称之为指向下一个边表节点的指针}
	//2. 单链表表头顶点
	//
	// 指向边表节点的边
	typedef struct ArcNode
	{
	int adjvex;// 该边所指向的边表节点的位置（当前边表节点）
	ArcNode *nextarc;// 指向下一条边的指针
	char info;// 当前边的权值或其他信息
	}ArcNode;

	// 单链表表头顶点
	typedef struct
	{
	ArcNode *firstnode;// 指向第一条边表节点的边
	char data;// 顶点信息
	}VNode;

	// 邻接表图的定义
	typedef struct AGraph
	{
	VNode adjlist[MAXSIZE];// 邻接表
	int n;// 顶点数
	int e;// 边数
	}AGraph;

# 邻接表和邻接矩阵的应用

	// 根据邻接表存储，判断顶点 i 和顶点 j 之间是否存在路径。
	//tips:
	// 1.DFS (注：一般而言无需需要计算路径长度才需要使用 BFS，而为了更方便的遍历顶点，一般采用 DFS)
	// 2. 从 i 开始进行 DFS 递归遍历所有顶点，当遇到 j 时代表 i 与 j 之间存在路径

	#define MAXSIZE 50
	typedef struct ArcNode
	{
	int adjvex;
	int info;
	ArcNode *nextArc;
	}ArcNode;

	typedef struct
	{
	char data;
	ArcNode *firstArc;
	}VNode;

	typedef struct
	{
	VNode adjlist[MAXSIZE];
	int n;
	int e;
	}AGraph;

	int visit[MAXSIZE];

	bool DFS(AGraph G,int i,int j){
	ArcNode *p;
	for(int k = 0;k<G->n;k++){
	visit[k] = 0;
	}
	visit[i] = 1;
	if(visit[j] == 1){
	return true;
	}else{
	p = G->adjlist[i]->firstArc;
	while(p!=NULL){
	if(visit[p->adjvex] == 0){
	DFS(G,p->adjvex);
	}
	p = p->nextArc;
	}

	}
	return false;
	}

	// 判断邻接表中的每个节点是否为根
	#define MAXSIZE 50
	typedef struct ArcNode
	{
	int adjvex;
	ArcNode *nextArc;
	}ArcNode;

	typedef struct
	{
	char data;
	ArcNode *firstArc;
	int info;
	}VNode;

	typedef struct
	{
	VNode adjlist[MAXSIZE];
	int n;
	int e;
	}AGragh;
	//DFS
	int count;
	bool judgeWhetherIsRoot(AGragh G,int v){
	ArcNode *p;
	count = count+1;
	visit[v] = 1;
	p = G->adjlist[v].firstArc;
	while(p!=NULL){
	if(visit[p->adjvex] == 0){
	judgeWhetherIsRoot(G,p->adjvex);
	}
	p = p->nextArc;
	}
	}

	int main(AGragh G)
	{
	bool flag = false;
	int visit[MAXSIZE];

	for(int j = 0;j<G->n;j++){
	count = 0;// 没遍历一个顶点就要把 visit 和 count 数值重新初始化
	for(int k = 0;k<G->n;k++){
	visit[k] = 0;
	}
	DFS(G,j);
	if(count == G->n){
	return 1;
	}else{
	return 0;
	}
	}
	}

	// 判断无向连通图是否是一颗树
	// tips:
	// 1.dfs
	// 2. 无向连通图是树的充要条件 -- 有 n-1 条边，n 个顶点

	#define MAXSIZE 50;

	typedef struct ArcNode
	{
	int adjvex;
	ArcNode *nextArc;
	}ArcNode;

	typedef struct
	{
	char data;
	ArcNode *firstArc;
	}VNode;

	typedef struct
	{
	VNode adjlist[MAXSIZE];
	int n;
	int e;
	}AGraph;


	int visit[MAXSIZE];
	void judgeWhetherTree(AGraph G,int v,int i,int j){
	// 边数和顶点数分别用 j 和 i 来表示
	i++;// 顶点数自增
	visit[v] = 1;
	ArcNode *p;
	p = G->adjlist[v]->firstArc;
	while(p!=NULL){
	j++;// 边数自增
	if(visit[p->adjvex] == 0){
	judgeWhetherTree(G,p->adjvex,i);
	}
	p = p->nextArc;
	}
	judge(G,i,j)
	}

	bool judge(AGraph G,int i,int j){
	if(G->n != (G->e)+1){
	return false;
	}
	// 注意！！！
	// 这里的边数判断应判断 G->n-1==j/2 是否成立而不是 G->n-1 == j 是否成立
	// 因为遍历的时候边数是实际的两倍。
	if(G->n!=i\|\|G->n-1)!=j/2){
	return false
	}else{
	return true;
	}
	}

# 图的高级算法 -- 极有可能考

恶心人有一手啊北科～～！

# Kruskal

	// 克鲁斯卡尔算法
	// 主要思想就是每次选取点的时候选的都是边权值最短的顶点
	// 该算法要用到并查集和顶点之间所构成的数组集合


	/* 总体思路：
	1. 任选一个顶点作为起始节点，而后选择与其相邻边中权值最小的那个进行连接
	2. 逐次递归完成连接即可

	算法思路
	1. 定义一个 Road 路径类（阐明每一条边的起点和终点对应的顶点编号，及该边的权值）
	2. 定义一个并查集数组 vex [MAXSIZE], 用来判断是否形成回路
	3. 针对二中的如何判断是否形成回路这一问题，采用的解决方法是 -- 通过查找每条边中所对应的顶点中二者各自的根节点
	若二者根节点相同，说明父节点一致形成了回路，反之未形成回路，即可将该边作为最小生成树的备选边 */


	#define MAXSIZE 50

	typedef struct
	{
	int a;
	int b;
	int weight;
	}Road;//a,b 分别表示该条路径首尾的两个顶点

	typedef struct
	{
	int no;
	char info;
	}vertexType;

	typedef struct
	{
	vertexType vex = [MAXSIZE];
	int edges[MAXSIZE][MAXSIZE]
	int n;
	int e;
	}MGraph;

	//road 存储每个顶点之间的边权值和顶点分别是谁
	Road road[MAXSIZE];
	//vex 存储每个根节点
	int vex[MAXSIZE];


	// 在并查集中查找根节点
	int getRoot(int a){
	//a 表示当前顶点的编号
	// 并查集 vex 中存储的每个值初始化时其值的大小均为节点编号值本身
	// 故：若当 a 的值不等于 v [a] 表明当前顶点并不是根节点
	while(a!=v[a]){
	a = v[a];
	}
	return a;
	}


	void kruskal(MGraph G,int &sum,Road road){
	int a;
	int b;
	for(int i = 0;i<G->n;i++){
	v[i] = i;
	}
	sort(G,G->e);// 将边权值大小进行递增排序。
	// 这里还没写排序算法！！！！建议把查找和排序搞完了之后返回来重构
	for(int j = 0;j<G->e;j++){
	a = getRoot(road[j].a);
	b = getRoot(road[j].b);
	}
	if(a!=b){
	v[a] = b;// 将 a 变为 b 的下一条边的节点；
	sum = sum+road[j].weight;
	}
	}

# Prim

	// 普利姆算法
	// 总体思路：
	// 1. 逐次选择边权值最短的边，连接边两端的顶点

	// 算法思路：
	// 1. 定义一个 lowcost [v] 存储当前顶点附近所拥有的最短边权值
	// 2. 定义一个 vex [v] 判断当前节点是否已经被并入生成树

	#define MAXSIZE 50
	#define INF 100
	typedef struct
	{
	int no;
	char info;
	}vertexType;

	typedef struct
	{
	int edges[MAXSIZE][MAXSIZE];
	vertexType vex[MAXSIZE];
	int n;
	int e
	}MGraph;

	void prim(MGraph G,int sum,int lowcost[MAXSIZE],int v){
	// 对 lowcost,vex 进行初始化
	for(int i = 0;i<G.n;i++){
	lowcost[i] = G.edges[v][i];
	vex[i] = 0;
	}

	vex[v] = 1;
	// 需要注意的是：每一次遍历都要找到当前顶点与剩余节点之间存在的最短路径关系
	int min;
	int temp;
	for(int j = 0;i<G.n-1;j++){
	min = INF;
	for(int k = 0;k<G.n;k++){
	if(vex[k] == 0&&G.edges[v][k]<min){
	min = G.edges[v][k];
	temp = k;
	}
	}
	}
	v[k] = 1;
	v = k;
	for(int x = 0;x<G.n;x++){
	if(G.edges[v][x]<lowcost[x]){
	lowcost[x] = G.edges[v][x];
	}
	}
	}

# Floyd

	// 弗洛伊德算法
	// 一般而言迪杰斯特拉求的是 --- 任意一点到其他顶点之间为止的最短路径 went
	// 而弗洛伊德算法往往求的是 --- 任意一对具有最短路径边权值的顶点

	#define MAXSIZE 50
	#define INF 1000
	typedef struct
	{
	int no;
	char info;
	}vertexType;

	typedef struct
	{
	int edges[MAXSIZE][MAXSIZE];
	vertexType vex[MAXSIZE];
	int n;
	int e
	}MGraph;

	void floyd(MGraph G,int path[][MAXSIZE],int cost[][MAXSIZE]){
	//path 表示当前路径是否进行了修改
	//cost 存储每对顶点间的边权值
	for(int i = 0;i<G.n;i++){
	for(int j = 0;j<G.n;j++){
	cost[i][j] = G.edges[i][j];
	path[i][j] = -1;// 默认将 path 中未被修改过的下一个节点设置为 - 1
	}
	}
	for(int x = 0;x<G.n;x++){
	for(int y = 0;y<G.n;y++){
	for(int z = 0;z<G.n;z++){
	if(cost[y][z]>cost[y][x]+cost[x][z]){
	cost[y][z] = cost[y][x]+cost[x][z]
	path[y][z] = x;
	}
	}
	}
	}
	}

	// 计算邻接表存储结构图的度

	// 指向边表节点的边
	typedef struct ArcNode
	{
	int adjvex;// 该边所指向的边表节点的位置（当前边表节点）
	struct ArcNode *nextarc;// 指向下一条边的指针
	struct ArcNode *priorarc;
	char info;// 当前边的权值或其他信息
	}ArcNode;

	// 单链表表头顶点
	typedef struct
	{
	struct ArcNode *firstnode;// 指向第一条边表节点的边
	char data;// 顶点信息
	}VNode;

	// 邻接表图的定义
	typedef struct AGraph
	{
	struct VNode adjlist[MAXSIZE];// 邻接表
	int n;// 顶点数
	int e;// 边数
	}AGraph;

	// 计算出度
	int getOuter(AGraph *G){
	int outer = 0;
	struct ArcNode *p;
	if(i=0;i<MAXSIZE;i++){
	p = G->adjlist[v]->firstArc;
	while(p!=NULL){
	outer++;
	p = p->nextarc;
	}
	}
	return outer;
	}

	// 计算入度
	int getInner(AGraph *G){
	int inner = 0;
	struct ArcNode *p;
	if(i=0;i<MAXSIZE;i++){
	p = G->adjlist[v]->firstArc;
	while(p!=NULL){
	inner++;
	p = p->priorarc;
	}
	}
	return inner;
	}

	sum = outer+inner;

	// 深度优先搜索求出图中各联通分量顶点集

	// 翻译：就是通过 dfs 或 bfs 来遍历图，然后返回 visit 数组
	//


	#define MAXSIZE 50;

	typedef struct ArcNode
	{
	int adjvex;
	ArcNode *nextArc;
	}ArcNode;

	typedef struct
	{
	char data;
	ArcNode *firstArc;
	}VNode;

	typedef struct
	{
	VNode adjlist[MAXSIZE];
	int n;
	int e;
	}AGraph;

	void Visit(VNode v){

	}

	int visit[MAXSIZE];
	void DFS(AGraph G,int v){
	// 无论是 dfs 还是 bfs 这里的 v 都是表示 VNode 的起点编号；
	visit[v] = 1;
	ArcNode *p;
	p = G->adjlist[v]->firstArc;
	while(p!=NULL){
	if(visit[p->adjvex] == 0){
	DFS(G,p->adjvex);
	}
	p = p->nextArc;
	}
	}

	// 将邻接表转换成邻接矩阵
	// 即将图的顺序存储改为链式存储

	#define MAXSIZE 50;
	typedef struct ArcNode
	{
	int adjvex;// 该边所指向的边表节点的位置（当前所指向的边表节点的下标）
	struct ArcNode *nextarc;// 指向下一条边的指针
	char info;// 当前边的权值或其他信息
	}ArcNode;

	// 单链表表头顶点
	typedef struct
	{
	ArcNode *firstnode;// 指向第一条边表节点的边
	char data;// 顶点信息
	}VNode;

	// 邻接表图的定义
	typedef struct
	{
	VNode adjlist[MAXSIZE];// 邻接表
	int n;// 顶点数
	int e;// 边数
	}AGraph;

	// 邻接矩阵的图定义
	typedef struct
	{
	int no;// 顶点的编号
	char info;// 顶点的其他信息，题目未要求的话，可不写
	}VertexType;


	typedef struct
	{
	// 定义一个二维矩阵
	// 需要注意的是：如果要求的是带有权值的节点，则要变成 float edges [MAXSIZE][MAXSIZE]
	int edges[MAXSIZE][MAXSIZE];// 存放顶点和顶点之间的关系
	int n;// 顶点数
	int e;// 边数
	VertexType vex[MAXSIZE];// 存放具体包含哪些顶点
	}Mgraph;

	void change(AGraph &aG){
	Mgraph mG;
	ArcNode *p;// 定义一个边表指针
	for(int i=0;i<MAXSIZE;i++){
	p = (ag.adjlist[i])->firstnode;
	// 注意这里是 while
	// 有一条边表，就要把边表相关的所有节点的关系全都联上
	while(p!=NULL){
	mg.edges[i][p->adjvex] = 1;
	p = p->nextarc;
	}
	}
	}

# 简答题

1. 图的拓扑排序可以用于解决什么问题，说明一种应用场景

图的算法

# 前情提要：

# 图

# BFS

# DFS

# 图的应用

# 邻接表、邻接矩阵的定义

# 邻接表和邻接矩阵的应用

# 图的高级算法 -- 极有可能考

# Kruskal

# Prim

# Floyd

# 简答题

树的算法

排序算法