邻接表

最小生成树

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

普利姆算法

思路：整个算法分为三步

  • 预准备数组初始化

  • 找与当前边相接的最短的打印且储存

  • 更新最小权值的数组

  • 唯一最小生成树无论从哪个节点出发生成的树都是一样的

所以我们从0出发

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

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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  b.b[k][j]) {
				shortest[j] = b.b[k][j];
				adjek[j] = k;
			}
		}
//k为上处的k，即为与当前节点最相近的节点
//因为是贪心算法，所以当当前节点与a节点的权值要小于名为k节点的与a节点的值时，代表当前与a最近的是k。

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

1
2
3
4
5
6
7
8
int j, i, k, min;
k = 0;
for (i = 1; i  b.b[k][j]) {
			shortest[j] = b.b[k][j];
			adjek[j] = k;
		}
	}
}

Kruskal算法

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

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

  • 遍历边集数组并排序

  • 遍历排序后到边集数组

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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  0; i--) {
		for (j = i - 1; j >= 0; j--) {
			if (b[i].power  0) {
		x = mark[x];
	}
	return x;
}

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

最短路径

Dijkstra算法

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

思路：广搜找最短路径

完整代码：

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 Dijkstra(int v1) {
	int low[MAX] = {0};
	int final[MAX] = {0};
	int i, j, k, min, w;
	//初始化
	for ( i = 0; i 广搜找最短，然后去找加入这个点后是否有比以前的路更短的方法，因为要记录的东西更多了所以把记录最短路径和前一个节点的数组开到了两位而已==**完全不一样好嘛**==


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


## 拓扑排序和关键路径

### 拓扑排序

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


结构体的定义：



- 边节点：




```c
typedef struct line {
	int name;
	int power;
	struct line *next;
} Line, *linep;
  • 顶点
1
2
3
4
5
typedef struct node {
	int in;//入度
	linep head;
} node;
node Node[MAX];//用的数组便于查找

实现

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
void toposort(int num) {
	int stack[MAX] = {0};//定义了一个数组记录节点如果节点不是数组形式，可以开一个指针数组
	int top = -1;
	int temp;
	int count = 0;
	//默认0是起始点
	for (int i = 0; i ", 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 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 name] - p->power name] - p->power;
		}
		p = p->next;
	}
}

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

1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i next) {
			temp = p->name;
			ete = etv[i];
			lte = ltv[temp] - p->power;//找的是每一条路 那自然是有起始点和末节点啊
            //当末节点减去这条路的时间等于起始节点的最晚开始时间的时候，那这条路就是关键路径
			if (ete == lte) {
				printf(" lenth:%d\n",
				       i, temp, p->power);
			}
		}
	}