IT培训机构|91免费精品视频|专注编程培训|91免费精品|软件开发培训_91免费国产视频_华清远见教育

本文主要想闡述有關(guān)圖的一些基本概念，及基本的實現(xiàn)方法。圖論算法是數(shù)據(jù)結(jié)構(gòu)中比線性表和樹更為復(fù)雜的算法，但并不影響它在實踐中的重要作用，和實際生活中的應(yīng)用，所以掌握這種算法還是蠻有用和有趣的。在這里，我會給大家介紹幾個生活中發(fā)生的問題，他們可以轉(zhuǎn)化成圖論問題。然后再給大家介紹一下圖的c語言基本實現(xiàn)。

一、圖的基本概念

概念1：圖。一個圖(graph)G=(V,E)由頂點(vertex)集和邊(edge)集組成。每一條變就是一個點對(v,w)，其中v,w∈V。有時也把邊稱作弧。如果點對是有序的，那么圖就叫做是有向的。有向的圖有時也叫有向圖。頂點v和w鄰接當(dāng)且僅當(dāng)(v,w)∈E。點對可以無向，我們稱作無向圖。有時候邊還具有第三種成分，稱作權(quán)或值。

圖(Graph)也可以形式化描述為： Graph = (V,E) 其中，V={Vi | Vi ∈datatype, i=0,1,……,n-1} 是圖中元素Vi(稱為頂點Vertex )的集合，n=0時，V為空集，記為φ。

概念2：強連通的。如果在一個無向圖中從每一個頂點到每個其他頂點都存在一條路徑，則稱該無向圖是連通的。具有這樣性質(zhì)的有向圖稱為是強連通的。

概念3：頂點的度(Degree)。用圖形來說明。設(shè)E為無向圖G中邊的集合，V、V’為圖中的頂點。若(V,V’)∈E，則稱V和V’互為鄰接點，或稱V與V’相鄰接，邊(V,V’)與V、V’相關(guān)聯(lián)。某頂點V的度記為D(V)，代表與V相關(guān)聯(lián)的邊的條數(shù)。如：

D(V1)=3 ，D(V2)=2。

又設(shè)A為有向圖G中弧的集合，若∈A，則稱V鄰接到V’，V’鄰接自V，與V、V’相關(guān)聯(lián)。頂點V的入度記為ID(V)，是圖中以V為弧頭的弧的條數(shù);而頂點V的出度記為OD(V)，是圖中以V為弧尾的弧的條數(shù)。

頂點V的度D(V)=ID(V)+OD(V)。如：

ID(V2)=2，OD(V2)=2，故D(V2)=4。

現(xiàn)實生活中能夠用圖進(jìn)行模擬的實例：

比如航空系統(tǒng)。每個機場是一個頂點，在由兩個頂點表示的機場間如果存在一條直達(dá)航線，那么這兩個頂點就用一條邊連接。邊可以有一個權(quán)，表示時間、距離或飛行的費用。有理由假設(shè)，這樣的一個圖是有向圖，因為在不同的方向上飛機可能所用時間或所花的費用會不同(例如，依賴于地方稅)。可能我們更愿意航空系統(tǒng)是強連通的，這樣就總能夠從任一機場飛到領(lǐng)帶的任意一個機場，我們也可能愿意迅速確定任意兩個機場之間的佳航線。佳可以是指邊數(shù)少的路徑，也可以是根據(jù)一種或所有的全中量度所算出的佳者。

交通可以用一個圖來模型化。每一條接到交叉口表示一個頂點，而每一條街道就是一條邊。邊的值可能代表速度限度，伙食容量，等等。此時我們可能是需要找出一條短路，或用該信息找出可能產(chǎn)生交通瓶頸的位置。

一、圖的c語言實現(xiàn)

如下：
#define MAXN 64           ∥大頂點數(shù)∥
typedef char vtype;            ∥設(shè)頂點為字符類型∥
typedef int adjtype;           ∥設(shè)鄰接矩陣A中元素aij為整型∥
typedef struct
{
vtype V[MAXN];             ∥頂點存儲空間∥
    adjtype A[MAXN][MAXN];     ∥鄰接矩陣∥
} mgraph;               
void createmgraph(mgraph G)    ∥建立無向圖的數(shù)組表示法∥
{  
int  i, j, n;
    vtype  ch, u, v;
    adjtype  w;
    i = n = 0;
    ch=getchar( );             ∥輸入頂點∥ 
    while (ch!=‘#’)          ∥#為結(jié)束符∥
{  
n++;                   ∥頂點計數(shù)∥
        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;       ∥設(shè)max為機器表示的∞∥
  scanf(“%c %c %d”, &u, &v, &w);   ∥讀入一條邊<u, v>及權(quán)值 ∥
    while (u != ‘#’)           ∥u=‘#’時結(jié)束∥
    {   
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);  ∥讀下一條邊∥
}                        
}  

設(shè)圖中頂點數(shù)為n，邊的條數(shù)為e。第一個while循環(huán)執(zhí)行次數(shù)為n;后兩個for循環(huán)的執(zhí)行次數(shù)約為n2;后一個while循環(huán)執(zhí)行次數(shù)為e;故算法的時間復(fù)雜度為T(n,e)=O(n2+e)。若n2>>e，則時間復(fù)雜度為O(n2)。

說明：mgraph G;則G為存儲圖的一個結(jié)構(gòu)體變量，G.V[MAXN]為頂點的存儲空間，而G.A[MAXN][MAXN]為鄰接矩陣。

數(shù)組表示法存儲結(jié)構(gòu)的建立算法比較簡單：讀入頂點和關(guān)系集(弧、邊)，建立頂點表和鄰接矩陣即可。

由于篇幅的限制，關(guān)于圖的存儲問題，關(guān)于廣度優(yōu)先搜索、深度優(yōu)先搜索、拓?fù)浣Y(jié)構(gòu)的處理，我會在后續(xù)的篇幅中，整理總結(jié)。

本文參照文獻(xiàn)：

[1]. 《數(shù)據(jù)結(jié)構(gòu)體與算法分析--c語言描述》 Mark Allen Weiss 著 機械工業(yè)出版社出版。

[2].華清遠(yuǎn)見 《數(shù)據(jù)結(jié)構(gòu)》課件