由於某天學到了這個圖形表示法
本魔就開始覺得這表示法怪怪的
問了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;
}
}
