第一天
TOP1:概念
图论是什么?
就是一个图,图中有许多点,点之间有许多边。大概就是:你在一个村庄里,村庄中有一些房子(你的邻居啦),而这些房子有许多小路连接(为了串门呗)。现在就有一堆关于这个村庄的问题。
那么有路径,路就会有长度和方向,在今后各位做题目时,题目就会有描述: 有向边、无向边 和 有权图、无权图 。
有向边、无向边 : 有向边就是固定这一条边只能从x通往y,y通往x则另寻别路。无向边就是两地互相通往。
有权图、无权图 :权值就是一条边的长度或代价。有权图好理解,无权图这里要注意: 不是边的权值为0,而是全都为1!!!
Top2:图的记录方法
首先,大家应该对图有一定的概念了,那么,该怎么去记录图呢?
邻接矩阵
这是一个很实用的东东,在比赛时好写,好用好调用,是新手必备之物。
矩阵矩阵,那么肯定那就是平行四边形了。我们想一想,平行四边形有哪两个条件?没错,是 长 与 宽 。所以,我们可以得到一个结论——
邻接矩阵是 二维数据 :例如,dis[ ][ ]
那么我们都知道,二维数组(矩阵)对于每一位有三个元素——所在行,所在列,和当前行列里面存的值。我们再好好想一下,可得——
邻接矩阵每一位存的是 一条边 ,行代表的是 起始点 ,列代表的是 终止点 ,而里面存的值就是 这条边的权值。
那么有一张4个点(A、B、C、D),3条边的图:
A连着B,B连着C,C连着A,D单独点;
无向,无权,那么连接表会是这样:
A B C D
A 0 1 1 INF
B 1 0 1 INF
C 1 1 0 INF
D INF INF INF 0
显而易见:
-
无向图的邻接矩阵是对称的 , 而有向图不同。
-
一个点到自己的距离是0,到没有直接边连接的点的权值是无穷大。
所以:邻接矩阵要初始化
如下:
for(int i = 1; i <= n; i++)
{
for(int j = i + 1; j <= n; j++)
{
dis[i][j] = dis[j][i] = (i == j) ? 0 : INF;
}
}
分割线
分割线
现在,对于邻接矩阵的概念已经有了,那么在输入的时候,(通常) 是x、y、z(起始点,终止点,权值),操作如下
cin>>n>>m;//n表示点的数量,m表示边的数量
for(int i = 1;i <= m; i++){//枚举输入边
cin>>x>>y>>z;//如上描述
//有向边:
dis[x][y] = z;
//无向边:
dis[x][y] = dis[y][x] = z;
}
分割线
分割线
链式前向星
名字很高大上,其实......就是链表。
博主很弱,如果看不大懂下面链式前向星和动态数组记录方法的,就不要看了,掌握好邻接矩阵吧
首先是变量定义:
int cnt;//用于添边时的编号计数
int w[10000];//记录边的权值
int next[10000];//记录每一条边的最开头的边的编号
int to[10000];//记录每一条边的终点
int first[10000] = {0};//记录每个点的最开头的边的编号
添边操作:
void addEdge(int u, int v, int weight)
{
cnt++; //边的编号
to[cnt] = v; //第cnt条边指向点v
w[cnt] = weight; //第cnt条边的权值
next[cnt] = first[u]; // 第cnt条边指向连接点u的第一条边
first[u] = cnt; //将连接点u的第一条边更新为第cnt条边
return;
}
然后......就没有然后了说了博主很弱,不用这个,顺便提一下而已
分割线
分割线
动态数组
和邻接矩阵没啥区别,也是二维数组,不过......省空间而已
如果有动态数组不会用的......百度吧
定义:
vector<int>nei[MAXN];
简单粗暴的模板
其他初始化读入啥的,见邻接矩阵吧......
好了,第一天就到这里,是不是收获很多呢狗屁?欢迎在下方留言!