特殊的邻接表——立方体邻接表:关于链接表的一些特殊情况的考虑

　　我们在学习图的时候，都知道常用的保存图的方法有邻接矩阵和邻接表。当图中的边的数量相对于顶点的数量较少是，邻接矩阵中会出现许多0值，即形成了稀疏矩阵。这个时候用邻接表来储存图就可以大大减少储存所需的空间，也即是对矩阵进行了“压缩”。

　　邻接表的本质是一种链式储存结构，它保存的是顶点间的邻接关系，也就是只考虑邻接矩阵中的非零元素。很自然会想到通过链表来构建一个邻接表，这是因为各个顶点通过的边的数量绝大多数不相同，用链表的动态分配内存显然更合理，但是还是存在一种特例：所有的顶点上的边的数量都相同。比如立方体，它有八个顶点，但是每个顶点都有且只有与其邻接的三个顶点，在这种各个顶点邻接顶点的数量相同的情况下，就没有必要用链表来储存，用长度固定的数组显然更方便，我称之为立方体邻接表（Cubic Adjacency List，CAL）。

　　CAL的定义和邻接表类似，只是各个顶点邻接的顶点数量相同，关于邻接表……大家可以复习以下数据结构课程中的定义。

　　下面直接以一个问题来阐述立方体邻接矩阵的结构定义和实际运用。

　　问题描述：

　　　　如图所示：

在正方体ABCD-A₁B₁C₁D₁  的A点处有一只青蛙（蚂蚁，虫子……什么都行）要跳到C₁  点，它每次只能条一步（也就是一条边），当跳满五次或者已经到达目标点时就停止跳动。

（1）求青蛙在5次以内跳到目的点的路线有多少条？

（2）求青蛙所有可能的跳跃方式？

 

先给出答案，根据排列组合的知识，第一问应该是3X2X1=6条，第二问应该是（3³ -6）X3X3+6=195种。下面给出这一题用CAL的源码：

1 /*Question: there is a frog standing in 2   A piont in cube ABCD-A1B1C1D1,it must 3   jump from one place to another within 4   5 jumps,how many ways does it have? 5 */ 6 #include 
     
       7  8 typedef enum {A,B,C,D,A1,B1,C1,D1} vertex; //定义顶点信息的枚举类型 9 10 const vertex cube[8][3]=                   /*cube[0]={B,A1,D}表示和A点邻接的是B，A1，D点以此类推，这样就构建了一个正方体*/11 {12     {B,A1,D},{A,C,B1},{B,C1,D},{A,C,D1},13     {A,D1,B1},{A1,C1,B},{D1,B1,C},{A1,D,C1}14 }; /* using an adjacency list to store graph*/ 15 16 long iCount=0;/* 记录所有可以到达C1点的路线的数量*/17 long iTotal=0;/*记录在5次以内到达的路线数（第一问答案）*/18 long iSum=0;/*记录所有的路线数（第二问答案）*/19 20 void Output(vertex path[],long count,int n);//函数原型，输出路径21 //output function22 23 int Traverse(int n, vertex p,vertex path[]);//函数原型，遍历邻接表24 //core func to traverse graph by recusion25 26 int main(void)27 {28     vertex path[5]={A}; //at most 529     vertex p=A;//起点在A点30     Traverse(0,p,path); //calling，遍历31     printf("All the number of existing paths : %ld \n",iCount);32     printf("number of thatc an complete the path within five steps :%ld\n",iSum);33     printf("All possible paths :%ld\n",iTotal);34     return 0;35 }36 37 void Output(vertex path[],long count,int n)//打印信息38 {39     int i;40     printf("Path %ld :",count);41     for (i=0;i<=n;++i)42     {43         switch (path[i])    44         {45             case A : printf("A-->"); break;        46             case B : printf("B-->");break;        47             case C : printf("C-->");break;        48             case D : printf("D-->");break;        49             case A1 : printf("A1-->");break;        50             case B1 : printf("B1-->");break;        51             case C1 : printf("C1\n");break;        52             case D1 : printf("D1-->");break;        53         }54     }55 }56 57 int Traverse(int n,vertex p,vertex path[])58 {59     int i;60     path[n]=p;61     if (n==5) //已经跳满五次62     {63         ++iTotal; //第三问数量加一64         if (p==C1)    //已经到C1点65         {66             Output(path,++iCount,n);    //iCount，可以到达的路线数量+1，67             return 1;68         }69         else70             return 0;71     }72     if (p==C1) //五步以内到达C1点73     {74         ++iTotal;75         Output(path,++iCount,n);    //输出76         if (n<5)77             ++iSum;78         return 1;    79     }80     for (i=0;i<3;++i) //没有到，从与某个顶点相邻接的三个点开始进行尝试81     {82         Traverse(n+1,cube[(int)p][i],path);//递归调用，遍历邻接表，其中（int）p指的是A～D1点（C语言中枚举类型是整形且默认从0开始）83     } 84     return 0;85 }
     

 编译并运行程序后可以发现与数学计算结果吻合（废话！）。由此，我们就成功的用邻接矩阵这种二维的形式保存了三维的立方体。

CAL的用途还有很多，尤其适合解决空间立体图形的问题。但是不管怎样变化，还是那几个常见的算法就可以实现的，简单就是美嘛！

---