資源描述：
《數(shù)據(jù)結(jié)構(gòu)第7章》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第七章圖圖的基本概念圖的存儲結(jié)構(gòu)圖的遍歷最小生成樹2002-11-121mmmm7.1圖的基本概念圖定義圖是由頂點集合(vertex)及頂點間的關(guān)系邊（或者弧)集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Graph＝(V,E)其中V={x
2、x?某個數(shù)據(jù)對象}是頂點的有窮非空集合；E={或(v,w)
3、v,w?V}是頂點之間關(guān)系的有窮集合，謂詞P(v,w)定義了弧的意義或信息,謂詞是用來刻劃個體詞的性質(zhì)或事物之間關(guān)系的詞.2002-11-122mmmm有向圖與無向圖若圖G中的每條邊都是有方向的，則稱G為有向圖。有向邊
4、也稱為弧。若圖G中的每條邊都是沒有方向(x,y)的，則稱G為無向圖.(x,y)稱為邊。V1V3V4V5V2V4V3V2V1無向圖G1有向圖G2G2=(V2,E2)V2={v1,v2,v3,v4}E2={,,,}G1=(V,E)集合V＝{v1,v2,v3,v4,v5}集合E＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}。2002-11-123mmmm權(quán)某些圖的邊具有與它相關(guān)的數(shù),稱之為權(quán)。在實際應(yīng)用中，權(quán)值可以有某種
5、含義。比如，在一個反映城市交通線路的圖中，邊上的權(quán)值可以表示該條線路的長度或者等級；對于一個電子線路圖，邊上的權(quán)值可以表示兩個端點之間的電阻、電流或電壓值；對于反映工程進(jìn)度的圖而言，邊上的權(quán)值可以表示從前一個工程到后一個工程所需要的時間等等。帶權(quán)圖叫做網(wǎng)。有向網(wǎng)、無向網(wǎng)。2002-11-124mmmm12356874ABDCE10796671231516603045358040752002-11-125mmmm完全圖對有n個頂點的圖，若為有向圖且邊數(shù)為n(n-1)，則稱其為有向完全圖。若為無向圖且邊數(shù)為n(n-1)/2，則
6、稱其為無向完全圖；邊或弧數(shù),稱vi鄰接到vj，弧關(guān)聯(lián)于頂點vi和vj.2002-11-126mmmm頂點的度一個頂點v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。頂點v的入度是以v為終點的有向邊的條數(shù),記作ID(v);頂點v的出度是以v為始點的有向邊的條數(shù),記作OD(
7、v)。子圖設(shè)有兩個圖G＝(V,E)和G‘＝(V’,E‘)。若V’?V且E‘?E,則稱圖G’是圖G的子圖。52002-11-127mmmm路徑在圖G＝(V,E)中,若存在一個頂點序列vp1,vp2,…,vpm，使得(vi,vp1)、(vp1,vp2)、...、(vpm,vj)均屬于E，則稱頂點vi到vj存在一條路徑。若一條路徑上除了vi和vj可以相同外，其余頂點均不相同，則稱此路徑為一條簡單路徑。起點和終點相同的路徑稱為回路或環(huán),其余頂點均不相同，稱為簡單回路62002-11-128mmmm圖的連通在無向圖G中，若兩個頂點v
8、i和vj之間有路徑存在，則稱vi和vj是連通的。若G中任意兩個頂點都是連通的，則稱G為連通圖。非連通圖的極大連通子圖叫做連通分量。BEADCFBAFEDC2002-11-129mmmm強(qiáng)連通圖與強(qiáng)連通分量在有向圖中,若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。V2V4V3V1V4V3V2V12002-11-1210mmmm生成樹一個連通圖的生成樹是它的極小連通子圖，含圖中n個頂點，有n-1條邊。V1V3V4V5V2V1V3V4V5V2
9、含圖中n個頂點，有n-1條邊的圖一定生成樹嗎？2002-11-1211mmmm生成森林在非連通圖中，由每個連通分量都可得到一個極小連通子圖，即一棵生成樹。這些連通分量的生成樹就組成了一個非連通圖的生成森林。BEADCFBAFEDC2002-11-1212mmmm基本操作P：結(jié)構(gòu)的建立和銷毀:CreateGraph(&G,V,VR);//按V和VR的定義構(gòu)造圖G。DestroyGraph(&G);//銷毀圖G。對頂點的訪問操作:LocateVex(G,u);//若G中存在頂點u，則返回該頂點在圖中位置；否則返回其它信息。Ge
10、tVex(G,v);//返回v的值。PutVex(&G,v,value);//對v賦值value。2002-11-1213mmmm對鄰接點的操作:FirstAdjVex(G,v);//返回v的第一個鄰接點。若該頂點//在G中沒有鄰接點，則返回“空”。NextAdjVex(G,v,w);//返回v的（相對
