C语言图结构总结（一） - 算法与数据结构

不同于线性表的一对一和树型结构的一对多的简单结构，图结构是一种元素多对多的复杂结构。

这里主要介绍：

图的各种定义

图的顶点与边之间的关系

图的存储结构（邻接矩阵、邻接列表等）

图的遍历方法（深度优先、广度优先）

最小生成树算法（Prim 算法、Kruskal 算法）

# 图的各种定义

G (V,E)：V 为顶点的集合，E 为边的集合
无向边：顶点 Vi 到 Vj 之间的边没有方向，用无序偶(Vi,Vj)来表示，(Vi,Vj) 与 (Vj,Vi) 一个意思
有向边：也称为弧，用有序偶<Vi,Vj>来表示，Vi 为弧尾，Vj 为弧头
无向完全图：无向图中，任意两个顶点之间都存在边。含有 n 个顶点的无向完全图有 $\frac{n(n-1)}{2}$ 条边。
有向完全图：有向图中，任意两个顶点之间都存在方向互为相反的两条弧。含有 n 个顶点的有向完全图有 $n(n-1)$ 条边。
稀疏图和稠密图：边或弧数以 $n\cdot logn$ 为分界。
网：即带权的图。
子图：假设 G1=(V1,E1),G2=(V2,E2)，V2 $\subseteq$ V1 并且 E2 $\subseteq$ E1，则 G2 为 G1 的子图。

# 图的顶点与边之间的关系

对于无向图：

邻接点：G=(V,E)，(V1,V2) $\in$ E，则 V1 和 V2 互为邻接点。(V1,V2) 依附于 V1 和 V2，(V1,V2) 与 V1 和 V2 相关联。
对于有向图：

邻接：G=(V,E)，<V1,V2> $\in$ E，则 V1 邻接到 V2，V2 邻接自 V1。

ID (V)：V 的入度（箭头指向 V 的数目）。

OD (V)：V 的出度（从 V 指出去的箭头数）。

TD (V)：和 V 相关联的边的数目。[TD(V)=ID(V)+OD(V)]
路径：从 V1 到 V2 能走的路。
路径的长度：路径上的边或弧的数目。
环 (回路)：第一个顶点到最后一个顶点相同的路径。
简单环：除首尾顶点（相同的一个顶点）外其余顶点不重复出现的环。
连通：V1 到 V2 有路径，则 V1 和 V2 是连通的。
连通图 / 强连通图：图中任意顶点 Vi 和 Vj 都是连通的。（有向图符合 -> 强）
连通分量 / 强连通分量：无向图中的极大连通子图。（同上）
连通图的生成树：即一个极小的连通子图，含有图中全部的 n 个顶点，但只有 n-1 条边（对一个图删去多余的边）。
有向树：恰有一个顶点的入度为 0，其余顶点的入度均为 1 的有向图。

# 图的存储结构

下面使用 C语言 来描述数据结构

先把最小单位定义一下：

	typedef char[4] Vertex;// 顶点信息
	typedef int Weight;// 权重
	typedef int Number;// 数值类

# 邻接矩阵

邻接矩阵

	typedef Weight** Matrix;// 矩阵
	typedef struct GMatrix {// 邻接矩阵存储结构
	Vertex* data;// 一维数组存放顶点信息
	Number n;// 顶点数
	Matrix M;// 二维数组
	};

# 邻接列表

这种存储结构对于 边数相对顶点较少 的图可以极大程度的节省存储空间，避免浪费

邻接列表

	typedef struct UGLBox {// 无权邻接表项
	Number v;//Vertex 顶点索引
	UGLBox* next;// 指向下一无权表项
	};
	typedef struct WGLBox {// 有权邻接表项
	Number v;//Vertex 顶点索引
	Weight w;
	WGLBox* next;// 指向下一有权表项
	};
	typedef struct GLHead {// 邻接列表头
	Vertex data;// 顶点名称
	void* B;//Box 表项
	};
	typedef struct GList {// 邻接列表存储结构
	Number len;// 表长
	GLHead* Head;// 指向表头数组
	};

针对有向图还可以改进为十字链表

十字链表 >folded

	typedef struct GOBox {// 十字链表项
	Number tailV;
	Number headV;
	GOBox* tail;
	GOBox* head;
	};
	typedef struct GOHead {// 十字链表头
	Vertex data;
	GOBox* tail;
	GOBox* head;
	};
	typedef struct GOList {// 十字链表存储结构
	Number len;
	GOHead* Head;
	};

同样的，针对无向图也可以改进为邻接多重表，减少增减表项时的开支

邻接多重表 >folded

	typedef struct GMBox {
	Number tailV;
	GMBox* tail;
	Number headV;
	GMBox* head;
	};
	typedef struct GMHead {
	Vertex data;
	GMBox* first;
	};
	typedef struct GMList {
	Number len;
	GMHead* Head;
	};

# 边集数组

	typedef struct Edge {
	Number begin;
	Number end;
	Weight w;
	};
	typedef struct Edges {
	Number len;
	Vertex* v;
	Edge* e;
	};

最后还可以把输入数据规范化

>folded

	typedef struct UEdge {// 无权边
	Number t;//tailVertex
	Number h;//headVertex
	};
	typedef struct WEdge {// 有权边
	Number t;//tailVertex
	Number h;//headVertex
	Weight w;
	};
	typedef struct GInput {// 图输入
	Vertex* data;// 顶点
	Number n;// 顶点数
	void* Edges;// 边的关系
	Number len;// 边的关系的数量
	};

# 图的遍历方法

# 深度优先遍历

按照右手原则，每次选择上一顶点的最右边的下一顶点，走过一个顶点标记一个顶点，不能走被标记过的顶点，一条路走到黑，直到无路可走，然后回溯。
这个就是先走到最大深度，不能再深入后，再返回到有支路可走的顶点继续深入到最下面。

总结：层层递归，碰壁回溯。（或是使用栈：出栈入栈，依次访问。）

# Example: `马踏棋盘算法`

马踏棋盘算法，也称骑士周游问题。在一个 8x8 的国际象棋棋盘上，用一个马按照马步（即走日字，同中国象棋的马的走法）跳遍整个棋盘，要求每个格子都只跳一次，最后回到出发点。

问题分析

棋盘的表示（二维数组）
计算马的下一步可能的位置
关于马的走法：

通过对位移参数 1 和 2，y 轴对称，y=x 对称，y=-x 对称三步可以列出所有可能的下一步位置。（或者直接手写 8 个坐标偏移）
判断可能的位置是否合法（没有超出边界且该位置还没有被遍历过）
递归，回溯，直到找出解
这一步还可以用贪心算法优化：
我们要走的下一步位置，它的可选下一步位置数（记为权重）应当最少；
对下一步位置的权重集合进行非递减排序（可以有重复值的递增排序）；
然后按照这个排序结果遍历，就可以少很多次递归。

代码

马踏棋盘算法.cpp >folded

	#include <stdio.h>
	#include <stdlib.h>
	#include <math.h>
	#define X 8
	#define Y 8

	int chess[Y][X];
	int Tag;// 遍历顺序
	bool isFind;
	int solveCount;

	// 定义两个数据结构，分别用来存放坐标信息和权值信息
	typedef struct xybox {
	int x;
	int y;
	};
	typedef struct weightbox {
	int len;
	xybox xy[8];
	int w[8];
	};
	// 下一个可能跳的坐标
	inline xybox nextxy(int x,int y,int count,xybox* data) {
	xybox xy;
	xy.x = x + data[count].x;
	xy.y = y + data[count].y;
	return xy;
	}
	// 建立马跳的格子的增量数据，总共 8 种情况返回指针指向 xybox [8]
	xybox* buildData() {
	int i;
	xybox* data = (xybox)malloc(8 sizeof(xybox));
	data[0].x = -1;data[0].y = -2;
	data[1].x = 1; data[1].y = -2;
	//y=x 镜像处理
	for (i = 2; i < 4; i++) {
	data[i].x = data[i - 2].y;
	data[i].y = data[i - 2].x;
	}
	//y=-x 镜像处理
	for (i = 4; i < 8; i++) {
	data[i].x = -data[i - 4].y;
	data[i].y = -data[i - 4].x;
	}
	return data;
	}
	// 遍历棋盘，深度优先，使用贪心算法优化
	bool traverse(int x,int y,xybox* data) {
	if (Tag == X * Y) {
	// 找到解，输出
	isFind = true;// 已找到解
	printf("第%d个解：\n", ++solveCount);
	for (int i = 0; i < Y; i++) {
	for (int j = 0; j < X; j++) {
	printf("%d\t", chess[i][j]);
	}
	printf("\n");
	}
	return false;
	}
	int i;
	xybox xy;
	weightbox weight;
	bool flag = 1;
	weight.len = 0;
	for (i = 0; i < 8; i++) {
	xy = nextxy(x, y, i, data);
	if (xy.x<0 \|\| xy.x>=X \|\| xy.y<0 \|\| xy.y>=Y \|\| chess[xy.y][xy.x]) {
	// 超出边界或已被遍历，下次循环
	continue;
	}
	else {
	// 否则标记，并继续递归
	weight.xy[weight.len++] = { xy.x,xy.y };
	flag = 0;
	chess[xy.y][xy.x] = ++Tag;
	xybox xytmp;
	// 模拟下一次遍历，并将遍历后可走格子数记为权重存入权重数组
	for (int i = 0; i < 8; i++) {
	xytmp = nextxy(xy.x, xy.y, i, data);
	if (xytmp.x < 0 \|\| xytmp.x >= X \|\| xytmp.y < 0 \|\| xytmp.y >= Y \|\| chess[xytmp.y][xytmp.x]) {
	// 超出边界或已被遍历，下次循环
	continue;
	}
	else {
	weight.w[weight.len - 1]++;
	}
	}
	chess[xy.y][xy.x] = 0;
	Tag--;
	}
	}
	if (flag) {
	// 遍历失败，回溯
	return false;
	}
	// 按权值从小到大排序
	int min, minIdx, j;
	for (i = 0; i < weight.len; i++) {
	min = weight.w[i]; minIdx = i;
	for (j = i + 1; j < weight.len; j++) {
	if (min < weight.w[j]) { min = weight.w[j]; minIdx = j; }
	}
	xybox tmp = weight.xy[i];
	int tmp2 = weight.w[i];
	weight.xy[i] = weight.xy[minIdx];
	weight.w[i] = weight.w[minIdx];
	weight.xy[minIdx] = tmp;
	weight.w[minIdx] = tmp2;
	}
	// 依次遍历（贪心算法）
	flag = 0;
	for (i = 0; i < weight.len; i++) {
	chess[weight.xy[i].y][weight.xy[i].x] = ++Tag;
	if (!traverse(weight.xy[i].x, weight.xy[i].y, data)) {
	chess[weight.xy[i].y][weight.xy[i].x] = 0;
	Tag--;
	flag = 1;
	}
	}
	if (flag) {
	// 遍历失败，回溯
	return false;
	}
	return true;
	}
	int main() {
	xybox* data = buildData();
	// 这边数组输入 X 和 Y 是反过来的 chess [Y][X]
	chess[0][0] = ++Tag;
	if (!traverse(0, 0, data)) {
	printf("算法失败！\n");
	}
	free(data);
	return 0;
	}