网站可以随便创建么,做外贸在哪个平台比较好,网站开发专业的领军人物,网站有权重但是没访问今天#xff0c;我们讲解一下图论的概念#xff0c;首先我们知道图是一个什么东西。
图你可以理解成一个网络系统#xff0c;两个节点之间可能会有边#xff0c;边链接两个节点#xff0c;可能是有向#xff08;就比如说a只能往b,或者b只能往c)#xff0c;可能是无向我们讲解一下图论的概念首先我们知道图是一个什么东西。
图你可以理解成一个网络系统两个节点之间可能会有边边链接两个节点可能是有向就比如说a只能往b,或者b只能往c)可能是无向就是相当于没有方向如果a和b有一条无向边的话a可以往bb可以往a)一条边可能有长度我写一些图论题目常见的用词 1.有向边上面说了他是有方向的比如说a到b的有向边不能由b到a
2.无向边上面说了就是只要连上了两个都能到达
3.边权代表边的长度有些图可能不需要考虑边长比如说判断两点是否可达这种问题是没有边权的。
4.反向边只对有向边有效比如说a-b,他的反向边就是b-a
5.重边:出现了两条一模一样的边可能会影响后面的算法所以说要注意不过一般来讲基础题是保证了没有重边不过仍然需要注意
6.自环自己向自己连一条边这种情况和重边一样的也会影响算法甚至可能让一些算法卡住。
7.链对于任意一个节点他们当中没有分叉比如说这种1-2,2-3这种就有点像一条直线。这种数据可能需要小心因为有些算法会在链上退化比如说像BST(二叉搜索树)不过有时候骗分的时候也可以特判链的情况。
8 .环相当于把链的首尾相接有时候环也会卡住。
9.树这种数据比较友好一些图的算法不会在上面退化反倒还容易骗分一些定义是由n个节点和n-1条组成的无向无环图。
10.菊花图就是所有点都连到了一个点形成了一朵菊花有些算法会在上面退化比如说spfa算法的O(km)会在菊花图的情况下变成O(nm)这里一定要注意这种情况以前NOI曾经有人写了spfa被菊花图卡了
11.蒲公英图菊花图和链组成起来也会让一些算法退化。
12.负权/负权边意思说一条边的权值为负数这回让一些算法出问题例如dijkstra最短路)这种时候必须要spfa算法了当然不止这些还有一些其他的算法也会在负权边上出问题。
13.负权回路/负环相当于一个环里所有数为负数为让最短路算法卡进去包括spfa)遇到负环可能需要用spfa判断负环.
14.正权回路/正环根负环一样的只不过是正数这也会让求最长路时出问题
15.连通图图是联通的对于任意两点他们都有一条路径。
16.点权有一些题目他不是边有长度而是经过一个点有点权比如说我经过一个点需要支付多少钱啊这种的一般来讲树形dp一般是没有边权而是点权。
