图

邻接表

最小生成树

最小生成树的两种算法核心思想都是贪心

普利姆算法

思路：整个算法分为三步

预准备数组初始化
找与当前边相接的最短的打印且储存
更新最小权值的数组
唯一最小生成树无论从哪个节点出发生成的树都是一样的

所以我们从0出发

这只是最基本的方法，有很大的优化空间

完整代码

void Kruskal() {
	EDG b[20];//*(&b[0])@10
	int markz[10] = {0};
	int size = EDGinit(b);
	printf("\n");
	sort(size, b);
	int start, end;
	for (int i = 0; i <= size; i++) {
		start = DEBUG(b[i].start, markz);
		end = DEBUG(b[i].end, markz);
		if (start != end) {
			markz[start] = end;
			printf("(%d %d)\n", b[i].start, b[i].end);
		}
	}//应该可以考虑加一个判断是否已经使用完了的方式来减少时间?

}

预备数组初始化

void  primeinit() { 
	int i;
	shortest[0] = 0; //已经加入了节点不参与寻路
	adjek[0] = 0; //第一个节点为x
	for (i = 1; i < MAX - 1; i++) {

		shortest[i] = b.b[0][i];
		adjek[i] = 0;
	}
}
//adjek数组存储的是其对应的最小的权值是那条边的
//short数组的作用是存储与该边相连的最小的权值

找到与当前边相接的最短的储存并打印

min = INF;
	k = 0;
	for (j = 1; j < MAX - 1; j++) {
		if (shortest[j] != 0 && shortest[j] < min) {
			min = shortest[j];
			k = j;
		}
	}//找出与现在这条边最短的相连边
	//short数组为0时代表该节点已经被选上了
	printf("(%d %d)\n", adjek[k], k);
	shortest[k] = 0;//标记已经被选上了

更新最小权值的数组

for (j = 1; j < MAX - 1; j++) {
			if (shortest[j] != 0 && shortest[j] > b.b[k][j]) {
				shortest[j] = b.b[k][j];
				adjek[j] = k;
			}
		}
//k为上处的k，即为与当前节点最相近的节点
//因为是贪心算法，所以当当前节点与a节点的权值要小于名为k节点的与a节点的值时，代表当前与a最近的是k。

注意其中的1，2是在一个大循环中实现的，因为要遍历所有的点

int j, i, k, min;
k = 0;
for (i = 1; i < MAX - 1; i++) {
	min = INF;
	k = 0;
	for (j = 1; j < MAX - 1; j++) {
		if (shortest[j] != 0 && shortest[j] < min) {
			min = shortest[j];
			k = j;
		}
	}//找出与现在这条边最短的相连边
	printf("(%d %d)\n", adjek[k], k);
	shortest[k] = 0;
	for (j = 1; j < MAX - 1; j++) {
		if (shortest[j] != 0 && shortest[j] > b.b[k][j]) {
			shortest[j] = b.b[k][j];
			adjek[j] = k;
		}
	}
}

Kruskal算法

基本思路：把每条路径的权值储存起来，然后从小到大依次选择，只要不形成回路即可

定义一个边集数组，存储起始节点和权值,定义一个可以并查集的数组来判断是否形成了循环
遍历边集数组并排序
遍历排序后到边集数组

注意并查集的判断来防止形成循环

完整代码（不包含调用的自定义函数）

void Kruskal() {
	EDG b[20];//*(&b[0])@10
	int markz[10] = {0};
	int size = EDGinit(b);
	printf("\n");
	sort(size, b);
	int start, end;
	for (int i = 0; i <= size; i++) {
		start = DEBUG(b[i].start, markz);
		end = DEBUG(b[i].end, markz);
		if (start != end) {
			markz[start] = end;
			printf("(%d %d)\n", b[i].start, b[i].end);
		}
	}//应该可以考虑加一个判断是否已经使用完了的方式来减少时间?

}

边集数组以及存储数据

int EDGinit(EDG *p) {
	//*(&p[0])@10
	int i = 0, j = 0, head = -1;
	for (i = 0; i < MAX - 1; i++) {
		for (j = 0; j < MAX - 1; j++) {
			if (b.b[i][j] != INF && b.b[i][j] != 0) {
				(p)[++head].start = i;
				(p)[head].end = j;
				(p)[head].power = b.b[i][j];
				b.b[i][j] = 0;
				b.b[j][i] = 0;
			}
		}
	}
	return head;
}//*p指向边集数组

2.边集数组的排序

使用不同的排序方式可以该边该算法的效率

void sort(int size, EDG b[]) {
	int i, j;
	EDG temp;
	for (i = size; i > 0; i--) {
		for (j = i - 1; j >= 0; j--) {
			if (b[i].power < b[j].power) {
				temp = b[i];
				b[i] = b[j];
				b[j] = temp;
			}
		}
	}
	return ;
}//一个垃圾的垃圾冒泡

3.开始输出

for (int i = 0; i <= size; i++) {
		start = DEBUG(b[i].start, markz);
		end = DEBUG(b[i].end, markz);
		if (start != end) {
			markz[start] = end;
			printf("(%d %d)\n", b[i].start, b[i].end);
		}
	}

int DEBUG(int x, int mark[]) {
	while (mark[x] > 0) {
		x = mark[x];
	}
	return x;
}

mark为并查集数组，将end位置放上start的值即mark[end]为它的头，当mark[x]==0时说明其没有前一个节点，其自身就是最开始的节点

最短路径

Dijkstra算法

主要应用到某点到其余点之间的最短路

思路：广搜找最短路径

完整代码：

void Dijkstra(int v1) {
	int low[MAX] = {0};
	int final[MAX] = {0};
	int i, j, k, min, w;
	//初始化
	for ( i = 0; i < MAX - 1; i++) {
		low[i] = b.b[v1][i];
	}
	//开始寻路
	for (i = 0; i < MAX - 1; i++) {
		min = INF;
		//与如今节点直接相接的最近的点
		for (j = 0; j < MAX - 1; j++) {
			if (!final[j] && low[j] < min) {
				min = low[j];
				w = j;
			}
		}
		final[w] = 1;
		//更新经过了w节点后会不会有比当前路径更好的选择

		/*假设当前时0-1是最短的，其余的也还是0直达
		那么下边就是找0经过1后到达某个节点会不会变短*/
		for (j = 0; j < MAX - 1; j++) {
			if (!final[j] && min + b.b[w][j] < low[j]) {
				low[j] = min + b.b[w][j];
				path[j] = w;
			}
		}

	}

}

弗洛伊德（Floyd）算法

思想：和Dijkstra算法类似，~~广搜找最短，然后去找加入这个点后是否有比以前的路更短的方法，因为要记录的东西更多了所以把记录最短路径和前一个节点的数组开到了两位而已~~==完全不一样好嘛==

因为弗洛伊德算法是找每个点到每个点之间最短的路径要通过改变每个点到每个点经过的节点来进行遍历。

拓扑排序和关键路径

拓扑排序

基本思路：用栈存储了入度为0的节点，采用BFS的形式查找，将查找到的节点入度减一，如果为0，就存入栈，如果输出的节点小于总数，那么便是路径中有环

结构体的定义：

边节点：

typedef struct line {
	int name;
	int power;
	struct line *next;
} Line, *linep;

顶点

typedef struct node {
	int in;//入度
	linep head;
} node;
node Node[MAX];//用的数组便于查找

实现

void toposort(int num) {
	int stack[MAX] = {0};//定义了一个数组记录节点如果节点不是数组形式，可以开一个指针数组
	int top = -1;
	int temp;
	int count = 0;
	//默认0是起始点
	for (int i = 0; i <= num; i++) {
		if (Node[i].in == 0) {
			stack[++top] = i;
		}
	}
    //初始化栈，将入度为0的节点存进去
	linep p = NULL;
	while (top != -1) {
		temp = stack[top--];//从栈中间取出节点
		p = Node[temp].head;
		printf("%d->", temp);
		count++;//记录打印了几个节点
		while (p != NULL) {//从节点寻找与他相接的
			Node[p->name].in--;
			if (Node[p->name].in == 0) {//等于0就存进去
				stack[++top] = p->name;
			}
			p = p->next;
		}
	}
	if (count < num) { //说明存在循环
		//如果是存在循环应该打印什么

	}
}

关键路径

因为是aov图所以要等前置时间完成后才能够开始下一步，所以是多路时间值取最大

在记录最晚发生实际取最小的值的原因是如果比上一个节点的最早的节点晚的画，就会造成工期拖延

比如：22：00洗脸10，22：00刷牙5分钟，22：20睡觉。

前置事件是是洗脸和刷牙，要等刷完牙才能睡觉，所以睡觉的最早开始时间应该取刷完牙的时间

而最晚的发生时间则要看洗脸的时间，因为刷牙完成了可能洗脸还没洗完

主要思路：四个提前定义的基本类型：

int ete[];//储存发生的最早时间
int lte[];
int e;
int l;

// 用到的定义    
int stack[MAX] = {0};
	int stack1[MAX] = {0};

	int etv[MAX] = {0};
	int ltv[MAX] = {0};

	int ete;
	int lte;

	int top = -1;
	int top1 = -1; //stack1的指针
	int temp;

第一部分：在拓扑排序的时候记录下顺序存到另一个专门存排序顺序的栈里，便于后续的求最晚发生时间

while (top != -1) {
	temp = stack[top--];
	stack1[++top1] = temp; //存储拓扑排序的顺序
	p = Node[temp].head;
	while (p != NULL) {
		Node[p->name].in--;
		if (Node[p->name].in == 0) {
			stack[++top] = p->name;
		}
		if (etv[temp] + p->power > etv[p->name]) {//记录了最晚的发生时间
			etv[p->name] = etv[temp] + p->power;
		}
		p = p->next;
	}
}
if (top1 < num) { //说明存在循环
	
}

第二部分：初始化最早时间：

for (int i = 0; i <= num; i++) {
		ltv[i] = etv[num];
	}

第三部分找最找的时间

while (top1 != -1) {
	temp = stack1[top1--];
	p = Node[temp].head;
	while (p) {
		if (ltv[p->name] - p->power < ltv[temp]) {//取最小的原因上边已经说了
			ltv[temp] = ltv[p->name] - p->power;
		}
		p = p->next;
	}
}

第四部分当最短时间和最早时间相等时便输出

for (int i = 0; i <= num; i++) {
		//*(&etv[0])@10
		//*(&ltv[0])@10
		for (p = Node[i].head; p; p = p->next) {
			temp = p->name;
			ete = etv[i];
			lte = ltv[temp] - p->power;//找的是每一条路 那自然是有起始点和末节点啊
            //当末节点减去这条路的时间等于起始节点的最晚开始时间的时候，那这条路就是关键路径
			if (ete == lte) {
				printf("<%d,%d> lenth:%d\n",
				       i, temp, p->power);
			}
		}
	}