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>";
}
