上一篇“BFS与DFS”写完，突然意识到这个可能偏离了“数据结构”的主题，所以回来介绍一下图的存储：邻接表和邻接矩阵。

       存图有两种方式，邻接矩阵严格说就是一个bool型的二维数组，map[i][j]表示i到j有没有单向边，邻接表则是对1~N中每个点都拉出一个链表来，链表E[i]中存的每个点j都表示i到j有一条单向边。 这两种方式各有利弊，在稀疏图中，邻接表更好，省时间而且省空间；在稠密图中，邻接矩阵更好，不浪费时间的同时省去了指针域的空间。

       而实际写代码时，对于邻接矩阵，我们可能会考虑用int型的邻接矩阵来同时表达边的权值，这取决于具体情况；对于邻接表，我们在对每个点拉出一个链表时，可以实际分配一个一维数组作为表头，以简化删除边时的代码，同时方便存每个点的信息，也可以像本文代码中直接用指针来作为表头，省些空间。

       本文仅仅给出相对基本的代码，边上的信息仅有一个权值，想必这已经够了。如果信息增多，大家在同样的位置添加信息即可。另外，临界表在很多情况下是可以用静态内存来代替动态内存的，这个方法本文代码就不赘述了，方法同“线性表”一文中所述。

      注意！对于邻接表和邻接矩阵，我并未试过用类来写，在此仅仅给出一个很丑的类版代码，不是为了供大家参考，而是抛砖引玉，希望有高手能给出更好的类版实现代码，不胜感激！

清爽版：

1 const int maxn = 10000; 2  3 // 邻接矩阵 4 struct edge 5 { 6     bool p; // p表示此边有无，也可以通过c取一个题目中不可能取到的值来代替p的作用 7     int c; 8     edge():p(false) {} 9 }map[maxn+1][maxn+1];10 void Clear()11 {12     for(int i=1;i<=maxn;++i)13         for(int j=1;j<=maxn;++j) map[i][j].p=false;14 }15 void AddEdge(int u,int v,int c)16 {17     map[u][v].p=true; map[u][v].c=c;18 }19 void DelEdge(int u,int v)20 {21     map[u][v].p=false;22 }23 24 // 邻接表25 struct edge26 {27     int v;28     int c;29     edge *next;30     edge(int _v=0,int _c=0): v(_v), c(_c) {}31 }*E[maxn+1]; // 全局定义，初始便都是0；若在局部定义，则应先清032 void Clear()33 {34     edge *p;35     for(int i=1;i<=maxn;++i)36         while(E[i])37         {38             p=E[i]; E[i]=p->next;39             delete p;40         }41 }42 void AddEdge(int u,int v,int c)43 {44     edge *p=new edge(v,c);45     p->next=E[u]; E[u]=p;46 }47 void DelEdge(int u,int v)48 {49     if(E[u]->v==v) { E[u]=E[u]->next; return; }50     for(edge *p=E[u],*q=p->next;q;p=q,q=p->next)51         if(q->v==v)52         {53             p->next=q->next;54             delete q;55             return; // 如果有重边，则此处不应返回，应待循环完再返回56         }57 }

 

 

 

类版：

1 // 邻接表 2 struct edge 3 { 4     int v; 5     int c; 6     edge *next; 7     edge(int _v=0,int _c=0): v(_v), c(_c) {} 8 }; 9 10 class Map11 {12     static const int maxn = 10000;13     edge *E[maxn+1];14 public:15     Map() { for(int i=1;i<=maxn;++i) E[i]=0; }16     void clear()17     {18         edge *p;19         for(int i=1;i<=maxn;++i)20             while(E[i])21             {22                 p=E[i]; E[i]=p->next;23                 delete p;24             }25     }26     void add(int u,int v,int c)27     {28         edge *p=new edge(v,c);29         p->next=E[u]; E[u]=p;30     }31     void del(int u,int v)32     {33         if(E[u]->v==v) { E[u]=E[u]->next; return; }34         for(edge *p=E[u],*q=p->next;q;p=q,q=p->next)35             if(q->v==v)36             {37                 p->next=q->next;38                 delete q;39                 return; // 如果有重边，则此处不应返回，应待循环完再返回40             }41     }42     edge* begin(int u) { return E[u]; }43     edge* next(edge *p) { return p->next; }44 }G;