首页 > 代码库 > 吉林省2017年冬令营DAY5

吉林省2017年冬令营DAY5

DAY5 图论

       最短路径,最小生成树,拓扑排序,连通分量,二分图。

  总的来说,day5这一天讲的东西听得不怎么明白,准备冬令营过后回去慢慢理解。

首先讲的是邻接矩阵

假如有n个点,则建立一个n*n的二维数组,在i行的j位上做一个标记表示i与j连通。

  

      第二点讲的是链式前向星

  当天听的时候,听得很不明白,后来听大佬讲了一下,上网搜索了一些资料,还算是懂了些。

  先建立一个_edge结构体,内含{to,next,val},一个Head[]数组,一个计数器tot

  

技术分享
1 #define MX 10000
2 struct _edge
3 {
4     int to,next,val;
5 }edge[MX];
6 int head[MX],tot;
代码

  因为最后是从后向前遍历,所以,在构建的时候把edge[tot].to指向v,把权值w赋于edge[].val,把edge[].next指向head[u](起点之前最后一个边),head[u]指向tot。

技术分享
1 void add(int u,int v,int w)
2 {
3     edge[tot].to=v;
4     edge[tot].val=w;
5     edge[tot].next=head[u];
6     head[u]=tot++;
7 }
代码(add)

  

 

吉林省2017年冬令营DAY5