[練習] adjacency multilist

由於某天學到了這個圖形表示法

本魔就開始覺得這表示法怪怪的

問了RoBoard Lab後 我們找到了一篇N年前的論文

他主要是比較各種圖形表示法的優缺點

可以看得出來是用打字機打的...

他用的語言是Pascal

有興趣的人可以自己研究看看

然後我稍微介紹一下這種圖形表示法

他是用一個結構來做的

那結構有 mark,value1,value2,link1,link2

每個link代表本點接到的下一條線

舉例:  (網路搜尋到相關文章 都會找到一樣的範例)

mark是用來偵測是否把後面兩個link填完用的

填完後其實沒有什麼用處

畫掉的地方代表NULL 表示為沒有其他線了





然後我自己又想出了另一種方法來做adjacency multilist

我是用遞迴一層一層丟

遇到該新增的就新增

遇到該搜尋的就搜尋

然後將自己的address回傳

這樣就會自己填完這表格

也不需要特別去做mark的空間

以下為code:

#include <stdio.h>
#define graph_Max 4
struct Multilist{
 int val1;
 int val2;
 struct Multilist *link1;
 struct Multilist *link2;
};
Multilist **Matrix_to_Multilist(bool [][graph_Max]);
Multilist *Multilist_recursion(bool [][graph_Max],Multilist *[graph_Max],int,int);
int main(){
 //-------------graph-------------//
 /*
   　　┌─０─┐
   　　│　│　│
   　　１─┼─２
   　　│　│　│
   　　└─３─┘
 */
 //-------------------------------//
 bool graph[graph_Max][graph_Max] = {
           {0,1,1,1},
           {1,0,1,1},
           {1,1,0,1},
           {1,1,1,0}};
 Multilist **list;
 list = Matrix_to_Multilist(graph);
 getchar();
 return 0;
}
Multilist **Matrix_to_Multilist(bool graph[][graph_Max]){
 Multilist *start[graph_Max];
 for(int i = 0; i < graph_Max; i++){
  start[i] = Multilist_recursion(graph,start,i,0);
  //-------------output steps-------------//
  Multilist *t = start[i];
  bool out = false;
  printf("start[%d] --> %X\n",i,t);
  while(!out){
   printf("%X:\t%d,%d,%X,%X\n",t,t->val1,t->val2,t->link1,t->link2);
   t = t->val1 == i ? t->link1 : t->link2;
   if(t == NULL)
    out = true;
  }
  printf("\n");
  //-------------output steps-------------//
 }
 return start;
}
Multilist *Multilist_recursion(bool graph[][graph_Max],Multilist *start[graph_Max],int x,int y)
{
 if(y >= graph_Max)  //If search out of the graph, then return NULL, means it's end.
  return NULL;
 if(!graph[x][y])  //If two point are not linked, then skip this step.
  return Multilist_recursion(graph,start,x,y+1);
 Multilist *t;  //Use on add a Mutilist or get next Mutilist. 
 if(x < y){  //If x < y, means we need to add a Multilist.
  t = new Multilist();
  t->val1 = x;
  t->val2 = y;
  t->link1 = Multilist_recursion(graph,start,x,y+1);  //let the Multilist link to next list.
  return t;
 }else if(x > y){  //If x > y, means we had a Multilist before.
  t = start[y];
  while(t->val2 != x)  //Loop until we find the Multilist which we need.
   t = t->val1 == y ? t->link1 : t->link2;  //Find next list.
  t -> link2 = Multilist_recursion(graph,start,x,y+1);  //let the Multilist link to next list.
  return t;
 }
}