模拟链表实现邻接表

优点:
1. 不用动态申请内存,常数小
2. 没了

下面的代码使用首部插入法。

代码实现:

#include <iostream>
#include <cstring>
using namespace std;
static const int nmax=1000000,mmax=1000000;
//nmax表示节点最大个数,mmax表示边的最大个数
struct graph
{
    int to[mmax+5],dis[mmax+5],nxt[mmax+5],head[nmax+5],size;
    //to[i]为边i到达的点,dis[i]为边i的权值,nxt[i]为边i的下一条边的编号
    //head[i]表示点i邻接表中第一条边的编号,size表示该图中边的个数(已插入的)
    inline graph(){memset(head,-1,sizeof(head)),size=0;}//初始化
    inline void push(int u,int v,int w)//向图中插入一条从u到v,权值为w的有向边
    {
        to[size]=v,dis[size]=w,nxt[size]=head[u],head[u]=size,size++;
    }
};
graph g;//定义一个图g
int main()
{
    g.push(1,2,100),g.push(1,3,200);//加入从1到2和3的两条边
    for(int i=g.head[1];i!=-1;i=g.nxt[i])//遍历节点1的邻接表
        cout<<g.to[i]<<' '<<g.dis[i]<<endl;
    return 0;
}

程序输出:

3 200
2 100

一些注意事项

  1. graph别定义在函数内,容易爆栈
  2. 对于无向图,记得mmax要开大一倍
  3. 记得初始化
  4. 以graph为参数的时候建议传指针
  5. 没了

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *