树的直径以及邻接表，链式前向星的存图
今天的学习及刷题的过程中遇到了一些新的知识——树的直径，和前几天学到但没使用过的邻接表存图以及链式前向星存图。内容也不少，所以特意新开一篇文章进行介绍。
先来了解一下什么是树：
树（tree）是包含n（n>0）个结点的有穷集，其中：
- 每个元素称为结点（node）；
- 有一个特定的结点被称为根结点或树根（root）；
- 除根结点之外的其余数据元素被分为m（m≥0）个互不相交
的集合T1，T2，…Tm-1，其中每一个集合Tm-1（1≤i≤m）
本身也是一棵树，被称作原树的子树（subtree）。
树中距离最大的两个结点之间的距离称为树的直径。
树的直径的求法：
两次dfs或bfs。第一次任意选一个点进行dfs(bfs)找到离它最远的
点，此点就是最长路的一个端点，再以此点进行dfs（bfs），找到
离它最远的点，此点就是最长路的另一个端点，于是就找到了树
的直径。
证明：
假设此树的最长路径是从s到t,我们选择的点为u。
反证法：假设搜到的点是v。
1、v在这条最长路径上，那么dis[u,v]>dis[u,v]+dis[v,s],显然矛
盾。
2、v不在这条最长路径上，我们在最长路径上选择一个点为po，
则dis[u,v]>dis[u,po]+dis[po,t]，那么有dis[s,v]=dis[s,po]+dis[po,u]
+dis[u,v]>dis[s,po]+dis[po,t]=dis[s,t],即dis[s,v]>dis[s,t],矛盾。
也许你想说u本身就在最长路径，或则其它的一些情况，但其实
都能用类似于上面的反证法来证明的。
综上所述，你两次dfs(bfs)就可以求出最长路径的两个端点和路
径长度。 以上内容参考与学长的PDF
其实证明看不太懂得话问题不大，就是随便找一个位置先进行dfs或者bfs到达一个端点，再以这个端点为起点dfs或者bfs到达另一个端点即可。
有的题它让你处理的就是字符串组成的图，但是有的题就不会这么好心了，他会给出你节点，边，甚至有的还会给你出权值。此时我们就需要自己存图。
说到存图，一般都有三种方法。
二维数组
用二维数组进行存图，这个是最普通的办法，但是有一个致命的缺点就是当题目数据中的点比较多的时候有极高的空间复杂度，会爆内存。不过数据范围小的时候用二维数组来存图。还是很简单的。
举个栗子：
5个点 4条边
对每条边输入三个数，两个端点以及这条边的权值
1 2 2
2 3 4
4 5 1
1 4 2
1 5 3
char s[maxn][maxn];
for(int i=0;i<n;i++)
{
cin>>x>>y>>p;
s[x][y]=p;
s[y][x]=p;//如果是有向图的话，就不需要这一句了
}访问的时候直接s[i][j]就行了
邻接表法
邻接表法就是用vector来进行存储，这个也挺好理解，跟二维数组可以一样的理解。
举个栗子：
5个点 4条边
对每条边输入三个数，两个端点以及这条边的权值
1 2 2
2 3 4
4 5 1
1 4 2
1 5 3
//无权值
vector<int> v[maxn];
for(int i=0;i<n;i++)
{
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);//有向边的话不需要者一句
}//有权值
vector<pair<int,int> > v[maxn]；
fot(int i=0;i<n;i++)
{
cin>>x>>y>>z;
v[x].push_back(make_pair(y,z));
v[y].push_back(make_pair(x,z));//有向边的话不需要者一句
}访问每条边的时候需要这样写
for(int i=0;i<n;i++)
{
for(int j=0;j<v[i].size();j++)
{
cout<<v[i][j].first<<"->"<<v[i][j].second;
}
}链式前向星
链式前向星是一种很巧妙地方法。
首先建立一个结构体
struct Edge
{
int e;//表示第i条边的终点
int w;//权值
int next;//表示同起点的下一条边
};加边
cnt=0,head=-1;
void add ( int u, int v, int w)
{
edge [cnt ].w = w;
edge [cnt ]. to = v;
edge [cnt ]. next = head [u];
head [u] = cnt ++;
}边的遍历
for (int i= head [u];~i;i= edge [i]. next )
{
cout <<u<<" ->" <<edge [i].e<< endl ;
}链式前向星不会遍历到不存在的边。
内存利用率高，相比vector实现的邻接表而言，可以准确开辟最多边数的内存，不像vector实现的邻接表有爆内存的风险。
如果有兴趣深入理解存图的话可以参考一下这几篇博客：https://blog.csdn.net/acdreamers/article/details/16902023
三种存图方式的介绍就到这里了，我最喜欢用的是第二种，好理解又方便写，但是不得不承认链式前向星的优秀，还是应该会用的。
说完了存图，我还想说一下用邻接表存了图之后该如何进行搜索（这里以bfs为例）。
我们只需要对每个顶点进行搜索即可，即bfs传递的参数为邻接表中的第一个元素。
直接上代码吧
无权值得
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 1e5+10;
int dis[maxn],ans,vis[maxn],n,a,b;
vector<int> v[maxn];
int bfs(int x)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
queue<int> q;
q.push(x);
vis[x]=1,dis[x]=0;
int point;
while(!q.empty())
{
x=q.front();
q.pop();
if(dis[x]>ans)
{
ans=dis[x];
point=x;
}
for(int i=0;i<v[x].size();i++)
{
if(!vis[v[x][i]])
{
vis[v[x][i]]=1;
dis[v[x][i]]=dis[x]+1;
q.push(v[x][i]);
}
}
}
return point;
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
ans=0;
int point=bfs(1);
ans=0;
bfs(point);
cout<<ans<<endl;
}有权值的
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
int a,b,c,ans;
const int maxn = 1e5+10;
int vis[maxn],dis[maxn];
vector<pair<int,int> > v[maxn];
int bfs(int x)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
vis[x]=1;
int point=0;
queue<int> q;
q.push(x);
while(!q.empty())
{
x=q.front();
q.pop();
if(dis[x]>ans)
{
ans=dis[x];
point=x;
}
pair<int,int> mid;
for(int i=0;i<v[x].size();i++)
{
mid=v[x][i];
if(!vis[mid.first])
{
vis[mid.first]=1;
dis[mid.first]=dis[x]+mid.second;
q.push(mid.first);
}
}
}
return point;
}
int main()
{
while(cin>>a>>b>>c)
{
v[a].push_back(make_pair(b,c));
v[b].push_back(make_pair(a,c));
}
ans=0;
int point=bfs(1);
ans=0;
bfs(point);
cout<<ans<<endl;
return 0;
}这里只需要看一下对邻接表中vector下标的使用即可。
投递金山WPS等公司10个岗位 >
