前向星与链式前向星

        前向星是一种用来存储图的数据结构。它的构造方式很简单，读入每条边的信息，然后存到数组中，然后将数组排序，排序方法是按照起点顺序排序，若起点相同则按终点顺序排序，如果终点相同则按权重排序（如果有权重）。另外，为了方便查询，会用一个数组head[]存储起点为v的第一条边的位置。

  具体实现方法如下：

const int maxn=100+10;
const int maxm=1000+10;
int head[maxn];
//存储起点为i的第一条边的位置
int n,m;
struct NODE
{
int from;
//起点
int to;
//终点
bool operator < (const NODE & a) const
{
return (from==a.from&&to<a.to)||from<a.from;
}
};
NODE edge[maxm];
void Init()
{
for(int i=0;i<m;++i)
//读入数据
cin>>edge[i].from>>edge[i].to;
sort(edge,edge+m);
//排序
memset(head,-1,sizeof(head));
head[edge[0].from]=0;
for(int i=1;i<m;++i)
if(edge[i].from!=edge[i-1].from) head[edge[i].from]=i;
}
void solve()
//遍历整个图
{
for(int i=1;i<=n;++i)
{
for(k=head[i];edge[k].from==i&&k<m;++k)
{
cout<<edge[k].from<<" "<<edge[k].to<<endl;
}
}
}

        前向星的优点是可以应对点非常多的情况，并且可以存储重边，缺点是效率相对来说不是非常高，因为它不能直接找到两点之间是否有边，而且还要排序，比较浪费时间。

        看完了前向星，我们可以再了解一下链式前向星，链式前向星的结构也很简单，需要存储的信息有终点和与此边拥有相同起点的前一条边所在的位置next。构造方法使用类似于链表一样的方法将所有起点相同边连起来，head数组中存储最开始的一条边的位置，这样就能通过它找到所有的边。

        具体请看Malash大牛的博客：http://malash.me/200910/linked-forward-star/

  实现代码：

const int maxn=100+10;
const int maxm=1000+10;
int head[maxn];
int n,m,nEdge;
//n为顶点数，m为边数，nEdge为存储的边的数量
//如果边是双向的，那么存储的边的数量就是2m
struct NODE
{
int to;
int next;
};
NODE edge[maxm<<1];
void addedges(int u,int v)
//将边(u,v)添加进去
{
nEdge++;
edge[nEdge].next=head[u];
edge[nEdge].to=v;
head[u]=nEdge;
}
void foreach()
//遍历边
{
int i,k;
for(i=1;i<=n;i++)
{
for(k=head[i];k!=-1;k=edge[k].next)
{
cout<<i<<" "<<edge[k].to<<endl;
}
}
}
void Init()
{
nEdge=-1;
memset(head,0xff,sizeof(head));
int u,v;
for(int i=0;i<m;++i)
{
cin>>u>>v;
addedges(u,v);
addedges(v,u);
}
}

          从上面的代码可以看出，链式前向星相对于普通的前向星而言最大的优势是它不用排序，这样就节约了很多时间。

         以上只是个人学习的时候的一点总结，如果有不对的地方欢迎指出，谢谢。

最后

以上就是壮观保温杯为你收集整理的前向星与链式前向星的全部内容，希望文章能够帮你解决前向星与链式前向星所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。