9.11图论DAY 1
#上午
上午讲了图的基本概念,图的存储结构和图的遍历
上午的一个难点就是图的存储结构中的邻接表。
邻接表结构如下:
按照这个图来理解还是比较简单的 下面是图的一道巨水的练习:
T10767 田地上的环
题目描述FJ 让他的N (1 <= N <= 250)只编号为从1到N的奶牛在田地里玩.这些奶牛决定用M条(1<=M<=N*(N+1)/2)牛绳将各自连接起来.当然,不会出现一对牛被两条及以上牛绳连接起来.输入告诉你每一条牛绳连接的两只奶牛C1和C2(1 <= c1 <= N; 1 <= c2 <= N; c1 <> c2)FJ要求奶牛们与1号奶牛相连.现在你要帮助FJ找出所有没有与1号奶牛相连的奶牛.这里的相连既可以是直接的,也可以是间接的(特别的,1号奶牛总是与自己相连).将没有与1号奶牛相连的奶牛的编号升序输出.如果你找不到这样的一只牛,那么就输出0.
这道题还是比较水的 用邻接矩阵做的话很方便 3分钟就能AC 唯一的细节就是如果找不到就输出0不能忘记 可能是我闲着蛋疼= =用邻接表来做了一边 然后就出现了很多细节错误 = = 一个问题就是数组开太小了 两个点RE 还有一个就是只找了与1直接相关的牛(直接连着的) 而没有找间接的。
邻接矩阵代码:
#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[260][260]={0};
bool check[10000];
inline void dfs(int x)
{
check[x]=1;
for(int i=1;i<=n;i++)
if((!check[i])&&(f[x][i])) dfs(i);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int xx,yy;
scanf("%d%d",&xx,&yy);
f[xx][yy]=1;
f[yy][xx]=1;
}
dfs(1);
bool flag=true;
for(int i=1;i<=n;i++)
if(!check[i]) printf("%d\n",i),flag=false;
if(flag) printf("0");
return 0;
}
邻接表代码:
#include<bits/stdc++.h>
using namespace std;
int n,t,m,link[300];
bool check[300];
struct niu
{
int num,next;
}ni[50000];
inline void insert(int start,int end)
{
ni[++t].next=link[start];
ni[t].num=end;
link[start]=t;
}
inline void init()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int xx,yy;
scanf("%d%d",&xx,&yy);
insert(xx,yy);
insert(yy,xx);
}
return;
}
inline void work()
{
for(int i=link[1];i;i=ni[i].next)
check[ni[i].num]=1;
return;
}
inline void print()
{
bool flag=true;
for(int i=2;i<=n;i++)
if(!check[i]) printf("%d\n",i),flag=false;
if(flag) printf("0");
}
inline void dfs(int x)
{
for(int i=link[x];i;i=ni[i].next)
if(!check[ni[i].num])
{
check[ni[i].num]=1;
dfs(ni[i].num);
}
}
int main()
{
init();
work();
memset(check,0,sizeof(check));
dfs(1);
print();
return 0;
}
这边忘记说的一点是:既然邻接表程序打起来比邻接矩阵麻烦 为什么要用邻接表呢? 我们不妨设想一下 加入这个图有n个点 如果用邻接矩阵 数组的大小为n^2 也就是说当n大于一定值的时候 很容易超越数组范围 但是如果用邻接表的话 数组的大小就是边的长度 这样空间占用就会少很多。
#下午
下午主要讲的是 图中两点间的最短距离的几种算法floyed、dijkstra、Bellman-ford
一开始讲floyed的时候好困 然后就有一段时间无服务了 、、幸亏后来有一段时间消化 还是比较好理解的,floyed的算法就是用传递闭包思想 把任意亮点的距离都求出来 存入一个二维数组 。显然这种方法与邻接矩阵的缺点一样 很容易超范围。第二种办法就有点高级了 dijkstra:这个的办法是针对这个点进行运算的 有贪心的思想在,步骤如图:
这个办法时间复杂度就很低了 占的空间也少 但是也有缺点 就是不能有负权 如果有负权推一下就会发现可能算出来的不是最优解 也可能陷入了负权回路。 第三种算法Bellman-ford就不怕负权 不断针对这两个点进行迭代做“松弛”
方法如下:
推一下还是能理解。