圖§8.1 圖的基本概念
圖： 圖是資料結構g＝(v，e)，其中v是結點的有窮非空集合，結點的偶對為邊，e是邊的集合。圖中的結點又稱為頂點。
無向圖與有向圖：如果圖中每條邊都是沒有方向的，則稱為無向圖；無向圖中的邊表示圖中頂點的無序對，即（u , v）和（v , u）表示同一條邊。如圖8.
1.1為乙個無向圖，它的頂點集和邊集分別為：
v（g1）＝
e（g1）＝
如果圖中每條邊都是有方向的，則稱其為有向圖；有向圖的邊表示圖中頂點的有序偶對；在有向圖中，箭頭表示邊的方向。如圖8.1.2為乙個有向圖，該圖的頂點集和邊集分別為：
v（g2）＝
e（g2）＝
度、入度、出度：在乙個有向圖中，把以結點v為終點的弧的數目稱為v的入度；把以結點v為始點的弧的數目稱為v的出度。 入度和出度之和為該的結點的度。
如圖8.1.2中，頂點v3的入度為2，出度為1，度為3。
路徑 、路徑長度： 圖中從vs到vp 的一條路徑是指一串由頂點所成的連續序列vs , vi1 ,vi2 ,……, vin , vp ，且其中 (vp , vi1) , (vi1 ,vi2) , ……, (vin , vp) 都是e上的邊。
路徑上所包含邊的數目稱為路徑長度。
簡單路徑、簡單迴路：如果一條路徑的頂點序列中，頂點不重複出現，則稱此路徑為簡單路徑。起點和終點相同的路徑稱為迴路或環。
除了第乙個頂點和最後乙個頂點之外，其餘頂點不重複出現的迴路稱為簡單迴路。
連通圖、強連通圖：在無向圖g1中，若從頂點vt到vs有路徑，則稱vt 和vs是連通的。如果對於圖中任意兩個頂點都是連通的，則稱g1為連通圖。
在有向圖g2中，如果每一對頂點vi , vj ， 從vi到vj和從vj到vi都存在路徑，則稱g2為強連通圖。
子圖、生成子圖：在圖g＝（v，e）和圖g'=（v' , e'）中，若v v'， e e'，則稱圖g'是圖g的子圖。若v＝v'，e e'，則子圖g'=（v' , e'）是圖g的乙個生成子圖。
如圖8.1.3所示。
連通分量、強連通分量：所謂連通分量是指乙個無向圖中的極大連通子圖。有向圖中的極大強連通分量稱作強連通分量。
這裡「極大」的含義是：對該子圖中再加入其它結點，它便不再是連通的。
生成樹、生成森林：乙個連通圖的生成樹是含有圖中所有頂點的乙個極小連通生成子圖，首先它是原連通圖的生成子圖，其次它是連通的並且有最少的邊數。一棵含n個頂點的生成樹有且僅有n－1條邊，因為乙個有n個頂點的圖，如果少於n－1條邊則為非連通圖，如果多於n－1條邊則一定有環。
但有n－1條邊的圖不一定是生成樹。
乙個有向圖的生成森林是這樣乙個生成子圖，它由若干棵互不相交的有根有向樹組成。有根有向樹是這樣乙個有向圖，它恰有乙個結點的入度為零，其餘結點的入度為1，並且如果略去此圖中邊的方向，處理成無向圖後，圖是連通的。
網路：若圖的每條邊都帶有乙個權，則稱這種帶權圖為網路。通常權是具有某種實際意義的數，比如，它們可以表示兩個頂點之間的距離、耗費等。
§8.2 圖的儲存結構
§8.2.1 鄰接矩陣
鄰接矩陣是表示結點間相鄰關係的矩陣。若g是乙個具有n個結點的圖，則g的鄰接矩陣是如下定義的n×n矩陣：
a [ i , j ] =
例如，圖8.2.1的g1的鄰接矩陣為a1：
無向圖的鄰接矩陣為對稱矩陣！
帶權的圖，其鄰接矩陣中值為1的元素可以用邊上的權來代替。有時還可根據需要，將網的鄰接矩陣中的所有的0用∞代替。如圖8.2.2。
在實際程式設計中，∞ 如何表示？
§8.2.2 鄰接表
鄰接表是圖的一種鏈式儲存結構。
為圖中每乙個頂點建立乙個單鏈表，該頂點為表頭，後面連線與表頭結點有邊相連的結點。如圖8.2.3，g1、g2的鄰接表分別為：
§8.3 圖的遍歷
圖的遍歷就是從圖中某一頂點出發訪遍圖中其餘頂點，且使每乙個頂點僅被訪問一次。圖的遍歷使實現圖的其它演算法的基礎。和樹的遍歷類似，對圖也有深度和寬度兩種遍歷，也可分別稱為深度優先搜尋和廣度優先搜尋。
§8.3.1 深度優先搜尋
深度優先搜尋可以看出是樹的先根序遍歷的推廣。
假定初始狀態時，圖g中所有結點都未被訪問過，那麼從某個結點v0出發的深度優先搜尋圖g的遞迴過程可以描述為：
訪問結點v0 （對v打上已訪問標記）
依次從v0的未訪問的鄰接點出發，深度優先搜尋圖g
直至圖中與v0有路徑相通的頂點都被訪問到；
若此時圖中尚有頂點未被訪問，則另選圖中乙個未曾被訪問的頂點作起點，重複上述過程，直至圖中所有頂點都被訪問過為止。
請思考上述過程與連通圖、非連通圖的關係。
從vi出發，深度優先搜尋的遞迴過程如下：
procedure dfs( v0 : integer );
var i:integer;
begin
visit( v0);
visited[v0]:=true;
for i:=1 to n do
if (w[v0,i]>0) and (visited[i]=false) then dfs(i);
end;
如果是乙個連通圖，以上過程就已經遍歷全圖，但我們還應考慮非連通圖的情況，對整個圖進行深度遍歷的演算法如下：
procedure tr**er;
var i : integer;
begin
for i:=1 to n do visited[ i ]:=false;
for i:=1 to n do
if visited[ i ]:=false then dfs( i );
end;
§8.3.2 廣度優先搜尋
廣度優先搜尋類似於樹的按層次遍歷的過程。
假定初始時圖中所有結點都未被訪問過，那麼從某個結點v0出發的廣度優先搜尋過程可以描述為：
1．訪問了v0之後，依次訪問v0的各個未曾被訪問的鄰接點
然後分別從這些鄰接點出發，廣度搜尋圖g
若此時圖中尚有頂點未被訪問，則另選圖中乙個未曾被訪問的頂點作起點，重複上述過程，直至圖中所有頂點都被訪問為止。
對於圖8.3.1，從頂點v1 出發進行廣度搜尋，得到的頂點訪問序列是：
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12
廣度搜尋的過程是以v0為起始點，由近至遠，依次訪問和v0有路徑相通且路徑長度為1，2，…… 的頂點。為了順次訪問路徑長度為2、3、…… 的頂點，需設佇列 / 棧 ？）儲存1、2、…… 的頂點。
從vi出發，進行廣度搜尋的過程如下：
procedure bfs( v0 : integer);
var q:array [1..n] of integer;
front , rear , i , v : integer;
begin
visit( v0);
visited[v0]:=true;
q[1]:=v0;
front:=1; rear:=1;
while front<=rear do begin
v:=q[front];
front:=front+1;
for i:=1 to n do
if (w[v,i]>0) and (visited[i]=false) then begin
visited[i]:=true;
rear:=rear+1;
q[rear]:=i;
end;
end;
end;
對整個圖進行廣度遍歷的演算法如下：
procedure tr**er;
var i : integer;
begin
for i:=1 to n do visited[ i ]:=false;
for i:=1 to n do
if visited[ i ]:=false then bfs( i );
end;
【練習8-1】
從檔案讀入n個城市的汽車交通圖，用c [ i , j ] 表示從城市i到城市j是否有直達汽車，
1 城市i到城市j有單向直達汽車
0 城市i到城市j無單向直達汽車
請編制程式，輸出從各城市出發乘汽車（包括轉車）可以到達的所有城市。
[輸入格式] 輸入檔名：
第1行為整數n，代表n個城市
第2行到n＋1行為n×n的矩陣c
[輸出格式] 輸出檔名：
第1行為城市數n
第2到n+1行：第1個整數i，後面的整數代表從第i個城市出發可直達的城市；
[輸入輸出舉例]
2023年廣東省汕頭市中考語文試卷
廣東省汕頭市2010年中考語文試題 一 基礎 1.根據課文默寫古詩文。1 子曰 其恕乎論語 2 阿爺無大兒，木蘭無長兄木蘭詩 3 凝望著故鄉的方向，凝望著漸漸墜入大海的夕陽，老人哽咽著吟誦起崔顥 黃鶴樓 中的詩句聞者無不潸然淚下。4 四面邊聲連角起，千嶂裡范仲淹 漁家傲秋思 5 把杜甫 春望 默寫完...
廣東省汕頭市金山中學學年高一下學期期末考試數學試題
汕頭市金山中學2012 2013學年高一下學期期末考試 數學試題 一 選擇題 本大題共10小題，每小題5分，共50分把答案填在答題卡相應位置上 1 等差數列中，則 abcd 2 某林場有樹苗30000棵，其中松樹苗4000棵 為調查樹苗的生長情況，採用分層抽樣的方法抽取乙個容量為150的樣本，則樣本...
廣東省汕頭市澄海中學高考語文默寫練習 一 版含答案
高考默寫練習 一 1 孔子曰 不知命，無以為君子也不知言，無以知人也。2 樊遲未達。子曰能使枉者直。3 子曰知者動，仁者靜。知者樂，仁者壽。4 子曰 志士仁人 5 不違農時，谷不可勝食也斧斤以時入山林，材木不可勝用也。6 百畝之田，勿奪其時，數口之家可以無飢矣 七十者衣帛食肉，黎民不飢不寒，然而不王...