數據結構 圖的概念及怎么實現
時間：2018-01-25 來源：未知
本文主要想闡述有關圖的一些基本概念，及基本的實現方法。圖論算法是數據結構中比線性表和樹更為復雜的算法，但并不影響它在實踐中的重要作用，和實際生活中的應用，所以掌握這種算法還是蠻有用和有趣的。在這里，我會給大家介紹幾個生活中發生的問題，他們可以轉化成圖論問題。然后再給大家介紹一下圖的c語言基本實現。
一、圖的基本概念
概念1：圖。一個圖(graph)G=(V,E)由頂點(vertex)集和邊(edge)集組成。每一條變就是一個點對(v,w)，其中v,w∈V。有時也把邊稱作弧。如果點對是有序的，那么圖就叫做是有向的。有向的圖有時也叫有向圖。頂點v和w鄰接當且僅當(v,w)∈E。點對可以無向，我們稱作無向圖。有時候邊還具有第三種成分，稱作權或值。
圖(Graph)也可以形式化描述為： Graph = (V,E) 其中，V={Vi | Vi ∈datatype, i=0,1,……,n-1} 是圖中元素Vi(稱為頂點Vertex )的集合，n=0時，V為空集，記為φ。
概念2：強連通的。如果在一個無向圖中從每一個頂點到每個其他頂點都存在一條路徑，則稱該無向圖是連通的。具有這樣性質的有向圖稱為是強連通的。
概念3：頂點的度(Degree)。用圖形來說明。設E為無向圖G中邊的集合，V、V’為圖中的頂點。若(V,V’)∈E，則稱V和V’互為鄰接點，或稱V與V’相鄰接，邊(V,V’)與V、V’相關聯。某頂點V的度記為D(V)，代表與V相關聯的邊的條數。如：
D(V1)=3 ，D(V2)=2。
又設A為有向圖G中弧的集合，若
頂點V的度D(V)=ID(V)+OD(V)。如：
ID(V2)=2，OD(V2)=2，故D(V2)=4。
現實生活中能夠用圖進行模擬的實例：
比如航空系統。每個機場是一個頂點，在由兩個頂點表示的機場間如果存在一條直達航線，那么這兩個頂點就用一條邊連接。邊可以有一個權，表示時間、距離或飛行的費用。有理由假設，這樣的一個圖是有向圖，因為在不同的方向上飛機可能所用時間或所花的費用會不同(例如，依賴于地方稅)�？赡芪覀兏敢夂娇障到y是強連通的，這樣就總能夠從任一機場飛到領帶的任意一個機場，我們也可能愿意迅速確定任意兩個機場之間的佳航線。佳可以是指邊數少的路徑，也可以是根據一種或所有的全中量度所算出的佳者。
交通可以用一個圖來模型化。每一條接到交叉口表示一個頂點，而每一條街道就是一條邊。邊的值可能代表速度限度，伙食容量，等等。此時我們可能是需要找出一條短路，或用該信息找出可能產生交通瓶頸的位置。
一、圖的c語言實現
如下：
#define MAXN 64 ∥大頂點數∥
typedef char vtype; ∥設頂點為字符類型∥
typedef int adjtype; ∥設鄰接矩陣A中元素aij為整型∥
typedef struct
{
vtype V[MAXN]; ∥頂點存儲空間∥
adjtype A[MAXN][MAXN]; ∥鄰接矩陣∥
} mgraph;
void createmgraph(mgraph G) ∥建立無向圖的數組表示法∥
{
int i, j, n;
vtype ch, u, v;
adjtype w;
i = n = 0;
ch=getchar( ); ∥輸入頂點∥
while (ch!=‘#’) ∥#為結束符∥
{
n++; ∥頂點計數∥
if (n>MAXN-1)
ERROR(n); ∥溢出處理∥
G.V[i++]=ch; ch=getchar( ); ∥存入頂點, 并讀下一頂點∥
}
for (i=0; i<n; i++) ∥初始化鄰接矩陣∥
for (j=0; j<n; j++)
G.A[i][j]=max; ∥設max為機器表示的∞∥
scanf(“%c %c %d”, &u, &v, &w); ∥讀入一條邊<u, v>及權值 ∥
while (u != ‘#’) ∥u=‘#’時結束∥
{
i = locatevex(G,u); ∥求u的序號∥
j = locatevex(G,v); ∥求v的序號∥
G.A[i][j] = G.A[j][i] = w; ∥鄰接矩陣賦值（對稱）∥
scanf (“%c %c %d”,&u,&v,&w); ∥讀下一條邊∥
}
}
設圖中頂點數為n，邊的條數為e。第一個while循環執行次數為n;后兩個for循環的執行次數約為n2;后一個while循環執行次數為e;故算法的時間復雜度為T(n,e)=O(n2+e)。若n2>>e，則時間復雜度為O(n2)。
說明：mgraph G;則G為存儲圖的一個結構體變量，G.V[MAXN]為頂點的存儲空間，而G.A[MAXN][MAXN]為鄰接矩陣。
數組表示法存儲結構的建立算法比較簡單：讀入頂點和關系集(弧、邊)，建立頂點表和鄰接矩陣即可。
由于篇幅的限制，關于圖的存儲問題，關于廣度優先搜索、深度優先搜索、拓撲結構的處理，我會在后續的篇幅中，整理總結。
本文參照文獻：
[1]. 《數據結構體與算法分析--c語言描述》 Mark Allen Weiss 著 機械工業出版社出版。
[2].華清遠見 《數據結構》課件
华清图书馆
0元电子书，限时免费申领10本华清图书PDF版
扫码关注华清远见公众号
