圖說演算法使用JavaScript(三十三)

10-2-2相鄰串列法

前面所介紹相鄰矩陣法，優點是藉著矩陣的運算，可以求取許多特別的應用，如要在圖形中加入新邊時，這個表示法的插入與刪除相當簡易。不過可慮到稀疏矩陣空間浪費的問題，如要計算所有頂點的分支度時，其時間複雜度為O(n^2)。

因此可以考慮更有效率的方法，就是相鄰串列法(adjaceny list)。這種表示法就是將一個n列相鄰矩陣，表示成n個鏈結串列，這種做法和相鄰矩陣相比較節省空間，如計算所有頂點的分支度時，其時間複雜度為O(n+e)，缺點是圖形新邊的加入或刪除會更動到相關的串列鏈結，較為麻煩費時。

首先將圖形的n個頂點形成n個串列首，每個串列中的節點表示它們和首節點之間有邊相連。節點宣告如下：

class  list_node  {
           constructor ()  {
           this.val=0;
           this.next=null;
          }
}

在無向圖形中，因為對稱的關係，若有n個頂點、m個邊，則形成n個串列首，2m個節點。若為有向圖形中，則有n個串列首，以及m個頂點，因此相鄰串列中，求所有頂點分枝度所需的時間複雜度為O(n+m)。現在分別來討論下圖中兩個範例，該如何使用相鄰串列表示：

首先來看(A)圖，因為5個頂點使用5個串列首，V1串列代表頂點1，與頂點1相鄰的頂點有2及5，依此類推。

接著來看(B)圖，因為4個頂點使用4個串列首，V1串列代表頂點1，與頂點1相鄰的頂點有2，依此類推。

JS                    adjaceeency_matrix.js

class list_node {
	construnctor() {
		this.val=0;
		this.next=null;
	}
}

head=[];
for (i=0; i<6; i++) {
	head[i]=new list_node();
}

var newnode=new list_node();

//圖形宣告
data=[[1,2],[2,1],[2,5],[5,2],
		[2,3],[3,2],[2,4],[4,2],
		[3,4],[4,3],[3,5],[5,3],
		[4,5],[5,4]];

process.stdout.write('圖形的鄰接串列內容：\n');
process.stdout.write('-------------------------------------------\n');
for (i=1; i<6; i++)  {
	head[i].val=i;
	head[i].next=null;
	process.stdout.write('頂點 '+i+'=>');
	ptr=head[i];
	for (j=0; j<14; j++)  {
		if (data[j][0]==i) {
			newnode.val=data[j][1];
			newnode.next=null;
			while (ptr!=null) ptr=ptr.next;
			ptr=newnode;
			process.stdout.write('['+newnode.val+'] ');
		}
	}
	process.stdout.write('\n');
}