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

10-1-4有向圖形

有向圖形(Digrph)是一種每一個邊都可使用有序對<V1,V2>來表示，並且<V1,V2>與<V2,V1>是表示方向不同的邊，而所謂<V1,V2>，是指V1為尾端指向為頭部的V2。如下圖所示：

V={A,B,C,D,E}
E={<A,B>、<B,C>、<C,D>、<C,E>、<E,D>、<D,B>}

接下來則是有向圖形的相關定義介紹：

*完整圖形(Complete Graph)：具有n個頂點且恰有n*(n-1)個邊的有向圖形，如下圖所示：

*路徑(Path)：有向圖形中從頂點Vp到頂點Vq的路徑是指一串由頂點所組成的連續有像序列。

*強連接(Strongly Connected)：有向圖形中，如果每個相異的成對頂點Vi,Vj有直接路徑，同時，有另一條路徑從Vj到Vi，則稱此圖為強連接。如下圖：

*強連接單元(Strong Connected Component)：有向圖形中構成強連接的最大子圖，在下圖(A)中是強連接，但(B)就不是。

而圖(B)中的強連接單元如下：

*出分支度(Out-degree)：是指有向圖形中，以頂點V為劍尾的邊數目。

*入分支度(In-degree)：是指有向圖形中，以頂點V為箭頭的邊數目，下圖中V4的入分支度為1，出分支度為0，V2的入分支度為4，出分支度為1。

10-2不能不學的圖形表示法

知道圖形的各種定義與觀念後，有關圖形的資料表示法就易顯重要了。常用來表達圖形資料結構的方法很多，本節中將介紹四種表示法。

10-2-1相鄰矩陣法

圖形A有n個頂點，以n*n的二為矩陣陣列表示。此矩陣的定義如下：

相關特性說明如下：

接著就實際來看一個範例，請以相鄰矩陣表示右邊的無向圖：由於下圖共有5個頂點，故使用5*5的二維陣列存放圖形。下圖中，先找和1相鄰的頂點有哪些，把和1相鄰的頂點座標填入1。

跟頂點1相鄰的有頂點2及頂點5，所以完成下表：

其他頂點依此類推可以得到相鄰矩陣：

無向/有向圖形的6*6相鄰矩陣演算法如下：

for (i=0; i<10; i++) {
    for (j=0; j<2; j++) {
        for (k=0; k<6; k++) {
            tmpi=data[i][0];
            tmpj=data[i][1];
            arr[tmpi][tmpj]=1;
        }
    }
}
process.stdout.write('無向圖形矩陣：\n');
for (i=1; i<6; i++) {
    for (j=1; j<6; j++) 
        process.stdout.write('['+arr[i][j]+'] ');
    process.stdout.write('/n');
}

無向圖形

JS                 undirected.js

arr=[[0,0,0,0,0,0],
	 [0,0,0,0,0,0],
	 [0,0,0,0,0,0],
	 [0,0,0,0,0,0],
	 [0,0,0,0,0,0],
	 [0,0,0,0,0,0]];

data=[[1,2],[2,1],[1,5],[5,1],
	  [2,3],[3,2],[2,4],[4,2],
	  [3,4],[4,3]];

for (i=0; i<10; i++) {
	for (j=0; j<2; j++) {
		for (k=0; k<6; k++) {
			tmpi=data[i][0];
			tmpj=data[i][1];
			arr[tmpi][tmpj]=1;
		}
	}
}
process.stdout.write('無向圖形矩陣：\n');
for (i=1; i<6; i++) {
	for (j=1; j<6; j++) 
		process.stdout.write('['+arr[i][j]+'] ');
	process.stdout.write('\n');
}

PHP                    undirected.php

$arr = array(
    array(0,0,0,0,0,0),
	array(0,0,0,0,0,0),
	array(0,0,0,0,0,0),
	array(0,0,0,0,0,0),
	array(0,0,0,0,0,0),
	array(0,0,0,0,0,0)
);

//圖形各邊的起點值及終點值
$data = array(
	array(1,2),array(2,1),array(1,5),
	array(5,1),array(2,3),array(3,2),
	array(2,4),array(4,2),array(3,4),
	array(4,3)
);

for ($i=0; $i<10; $i++) {
	for ($j=0; $j<2; $j++) {
		for ($k=0; $k<6; $k++) {
			$tmpi=$data[$i][0];
			$tmpj=$data[$i][1];
			$arr[$tmpi][$tmpj]=1;
		}
	}
}

for ($i=1; $i<6; $i++) {
	for ($j=1; $j<6; $j++) {
		echo "[".$arr[$i][$j]."]";
	}
	echo "<br>";
}

有向圖形

JS                directed.js

arr=[[0,0,0,0,0,0],
	 [0,0,0,0,0,0],
	 [0,0,0,0,0,0],
	 [0,0,0,0,0,0],
	 [0,0,0,0,0,0],
	 [0,0,0,0,0,0]];

data=[[1,2],[2,1],[2,3],[2,4],
	  [4,3],[4,1],[2,4]];

for (i=0; i<6; i++) {
	for (j=0; j<6; j++) {
			tmpi=data[i][0];
			tmpj=data[i][1];
			arr[tmpi][tmpj]=1;
	}
}
process.stdout.write('有向圖形矩陣：\n');
for (i=1; i<6; i++) {
	for (j=1; j<6; j++) 
		process.stdout.write('['+arr[i][j]+'] ');
	process.stdout.write('\n');
}

PHP                directed.php

$arr = array(
    array(0,0,0,0,0,0),
	array(0,0,0,0,0,0),
	array(0,0,0,0,0,0),
	array(0,0,0,0,0,0),
	array(0,0,0,0,0,0),
	array(0,0,0,0,0,0)
);

//圖形各邊的起點值及終點值
$data = array(
	array(1,2),array(2,1),array(2,3),
	array(2,4),array(4,3),array(4,1)
	);

$count=count($data);
//echo $count."<br>";

for ($i=0; $i<$count; $i++) {      //讀取圖形資料
	for ($j=0; $j<$count; $j++) {       //填入arr矩陣
			$tmpi=$data[$i][0];    //tmpi為起始頂點
			$tmpj=$data[$i][1];    //tmpj為終止頂點
			$arr[$tmpi][$tmpj]=1;  //有邊的點填入1
	}
}

for ($i=1; $i<6; $i++) {
	for ($j=1; $j<6; $j++) {
		echo "[".$arr[$i][$j]."]"; //列印矩陣內容
	}
	echo "<br>";
}