(13)第六章 圖及其存儲結構

1、1第六 章 圖定義、概念、存儲結構、輸入2圖圖(Graph)的的ADT定義：定義：圖圖是是n( n0 0 )個個結點的有限集結點的有限集合。在任意一個圖中合。在任意一個圖中任意兩個結點之間都可能相關任意兩個結點之間都可能相關。圖。圖的的ADT定義如下：定義如下：一、基本概念一、基本概念數(shù)據(jù)對象數(shù)據(jù)對象V： V是具有相同特性的數(shù)據(jù)元素的集合，并稱為頂點集是具有相同特性的數(shù)據(jù)元素的集合，并稱為頂點集合。合。數(shù)據(jù)關系數(shù)據(jù)關系R： R=E E=|v,wV , （或（或（v, w)表示從表示從v到到w的弧的弧 (或邊）或邊）,且有函數(shù)且有函數(shù) P(v,w)定義了弧定義了弧上的信息或權值上的信息或權值基本

2、操作基本操作P： 詳見詳見 P127圖的二元組表示：圖的二元組表示：G=(V，E)E即為圖中邊或弧的集合。即為圖中邊或弧的集合。3圖的有關術語：圖的有關術語：一、基本概念一、基本概念 圖中的數(shù)據(jù)元素稱為圖中的數(shù)據(jù)元素稱為頂點；頂點； 有向圖；有向圖； ?。换?； 弧頭；弧頭； 弧尾；弧尾； 無向圖；無向圖； 邊；邊； *定理定理：若用：若用e表示有向圖或無向圖中弧或邊的條數(shù)，表示有向圖或無向圖中弧或邊的條數(shù)，即即e=|E|,則有：則有： 在有向圖中：在有向圖中： 0en(n-1) 在無向圖中：在無向圖中： 0en(n-1)/2 具有具有n(n-1)/2條邊的無向圖稱為條邊的無向圖稱為無向無向完全

3、圖：完全圖： 具有具有n(n-1)條邊的有向圖稱為條邊的有向圖稱為有向完全圖：有向完全圖：abcd01234圖的有關術語：圖的有關術語：一、基本概念一、基本概念頂點的度；頂點的度； 有向圖中頂點的度有向圖中頂點的度是該頂點的是該頂點的入度入度與與出度出度之和之和。 無向圖中頂點的度無向圖中頂點的度是與該是與該頂點頂點相關聯(lián)的邊的條數(shù)相關聯(lián)的邊的條數(shù)。 子圖：子圖：對于對于G1=(V1,E1),G2=(V2,E2),若若V2 V1，E2 E1，則稱，則稱G2是是G1的子圖。的子圖。 回路（環(huán)）：回路（環(huán)）：若一條路徑上的頂點均不相同則該路徑稱為若一條路徑上的頂點均不相同則該路徑稱為簡單路徑簡單路

4、徑；除了除了第一頂點第一頂點和和終點終點相同外，路徑上的其他頂點均不相同的路徑相同外，路徑上的其他頂點均不相同的路徑稱為稱為簡單回路簡單回路或或簡單環(huán)簡單環(huán)。第一頂點第一頂點和和最后頂點最后頂點相同的路徑叫相同的路徑叫回路回路或環(huán)或環(huán)。abcd01235圖的有關術語：圖的有關術語：一、基本概念一、基本概念 無向圖中任意兩個頂點都是連通的，則該圖為無向圖中任意兩個頂點都是連通的，則該圖為連通圖連通圖。有向圖中任何有序頂點對之間都有有向路徑，則稱該圖是有向圖中任何有序頂點對之間都有有向路徑，則稱該圖是強連通的強連通的。無向圖中最大的連通子圖稱為該圖的。無向圖中最大的連通子圖稱為該圖的連通分量連通分

5、量；有向圖中相應地稱為有向圖中相應地稱為強連通分量強連通分量。abcd01236圖的有關術語：圖的有關術語：一、基本概念一、基本概念 一個連通無向圖的一個連通無向圖的生成樹生成樹是該圖的一個極小連通子圖，是該圖的一個極小連通子圖，它包含有該圖的所有它包含有該圖的所有n個頂點以及連接這個頂點以及連接這n個頂點的（個頂點的（n-1）條邊。條邊。 邊或弧上帶權值的圖稱為邊或弧上帶權值的圖稱為網(wǎng)網(wǎng)（分為（分為無向網(wǎng)無向網(wǎng)和和有向網(wǎng)有向網(wǎng)）。）。 一個無向圖的所有生成樹中，邊上的權值之和最小的一個無向圖的所有生成樹中，邊上的權值之和最小的生成樹稱為該圖的生成樹稱為該圖的最小生成樹最小生成樹或或最小代價生

6、成樹最小代價生成樹。abcdef65512564637圖的有關術語：圖的有關術語：一、基本概念一、基本概念圖中頂點的圖中頂點的“序號序號”及其鄰接點的及其鄰接點的“序號序號”： 由于圖中頂點之間不存在全序關系，所以無法將圖中由于圖中頂點之間不存在全序關系，所以無法將圖中頂點進行線性排序。但為了實現(xiàn)圖的存儲結構，我們必須頂點進行線性排序。但為了實現(xiàn)圖的存儲結構，我們必須給每個頂點附加一個人為規(guī)定的給每個頂點附加一個人為規(guī)定的“序號序號”。這個序號即稱。這個序號即稱為該為該頂點在圖中的位置頂點在圖中的位置。 對于任意一個頂點而言，若它有兩個以上的鄰接點，對于任意一個頂點而言，若它有兩個以上的鄰接點

7、，則它的鄰接點也有所謂則它的鄰接點也有所謂“第一個鄰接點第一個鄰接點”， “第二個鄰第二個鄰接點接點”，.，這個順序也稱為，這個順序也稱為鄰接順序鄰接順序。8一、基本概念一、基本概念圖的遍歷圖的遍歷：從圖中某一頂點出發(fā)按一定規(guī)律沿著圖中的邊：從圖中某一頂點出發(fā)按一定規(guī)律沿著圖中的邊或弧訪問每一頂點一次且僅一次的操作稱為對圖的遍歷。或弧訪問每一頂點一次且僅一次的操作稱為對圖的遍歷。 *圖的遍歷有兩種方法：圖的遍歷有兩種方法：深度優(yōu)先遍歷深度優(yōu)先遍歷和和廣度優(yōu)先遍歷廣度優(yōu)先遍歷 *若圖是連通的或是強連通的，則遍歷過程所經(jīng)過的邊若圖是連通的或是強連通的，則遍歷過程所經(jīng)過的邊（或?。┘八闅v的頂點就得

8、到圖中的一棵（或?。┘八闅v的頂點就得到圖中的一棵生成樹生成樹。 *對于非連通圖而言，從某一連通分量中的某一頂點出對于非連通圖而言，從某一連通分量中的某一頂點出發(fā)執(zhí)行一次發(fā)執(zhí)行一次“遍歷遍歷”算法可得該連通分量的生成樹，該生算法可得該連通分量的生成樹，該生成樹是非連通圖的一顆成樹是非連通圖的一顆生成子樹生成子樹；分別對各連通分量執(zhí)行；分別對各連通分量執(zhí)行一次一次“遍歷遍歷”算法可得到非連通圖的算法可得到非連通圖的生成森林生成森林。 9二、存儲結構二、存儲結構*思想思想： 用兩個數(shù)組分別存儲數(shù)據(jù)元素(頂點)的信息和數(shù)據(jù)元素之間的關系： 一個一維數(shù)組vexs: 存放各頂點的有關信息； 一個二維數(shù)組

9、arcs: 存放各條邊或弧的有關信息Arcs : 一般情況下存放邊或弧上的權值； 對于邊或弧上無權值的圖而言，邊或弧上的權值 為1時表示該條弧或邊的存在，若兩頂點之間沒有邊或弧，則設置該條邊或弧上的權值為0。10二、存儲結構二、存儲結構#define INFINITY 10000 / INFINITY用以表示用以表示#define MAX_VERTEX_NUM 20 /最大頂點數(shù)最大頂點數(shù)enum GraphKind DG,DN,UDG,UDN ; /枚舉：有向圖枚舉：有向圖,有向網(wǎng)有向網(wǎng),無向圖無向圖,無向網(wǎng)無向網(wǎng)typedef struct ArcCell VRType adj; / VR

10、Type的類型視具體情況而定。對于帶權圖，的類型視具體情況而定。對于帶權圖，adj用以存用以存 /放邊或弧上的權值放邊或弧上的權值;對于無權圖，對于無權圖，adj用以存放用以存放0或或1(int類型類型) /InfoType * info; /一般情況下可以不使用該項一般情況下可以不使用該項 ArcCell , AdjMatrix MAX_VERTEX_NUM , MAX_VERTEX_NUM ; /AdiMatrix是一個類型為是一個類型為ArcCell的二維數(shù)組的二維數(shù)組,用以存放弧或邊的鄰接關系或權值用以存放弧或邊的鄰接關系或權值typedef struct VertexType vex

11、s MAX_VERTEX_NUM ; / VertexType是頂點值的類型是頂點值的類型 /一維數(shù)組一維數(shù)組vexs用以存放各頂點的值用以存放各頂點的值 AdjMatrix arcs; /二維數(shù)組二維數(shù)組arcs存放邊或弧上的信息（如權值）存放邊或弧上的信息（如權值） int vexnum , arcnum; /這兩項分別存放圖的頂點數(shù)目和弧的條數(shù)這兩項分別存放圖的頂點數(shù)目和弧的條數(shù) GraphKind kind; / kind用以存放圖的種類標志用以存放圖的種類標志 MGraph11二、存儲結構二、存儲結構例1：例如：例如：MGraph G1; 0 1 1 0 0 0 0 0 0 0 0

12、1 1 0 0 0G1.vexs0=a，. .， G1.vexs3=d ；G1.vexnum=4； G1.arcnum=4 ； G1.kind=DGG1.arcs =abcd012312二、存儲結構二、存儲結構例2：abde0134c2MGraph G2; 3 9 3 6 8 6 2 4 9 2 8 4 G2.vexs0=a，. .， G2.vexs4=e ；G2.vexnum=5； G2.arcnum=6 ； G2.kind=UDNG2.arcs =38692413二、存儲結構二、存儲結構*當輸入一個圖時，要求用戶先輸入圖的類型：Status CreateGraph(MGraph &

13、G) cinG.kind; switch(G.kind) case DG: return CreateDG(G); /0 case DN: return CreateDN(G); /1 case UDG: return CreateUDG(G); /2 case UDN: return CreateUDN(G); /3 default : return ERROR;/CreateGraph14二、存儲結構二、存儲結構*以無向網(wǎng)為例,即當用戶輸入圖的類型標志為UDN時,有：Status CreateUDN(MGraph &G) cinG.vexnum G.arcnum; /輸入頂點個數(shù)和

14、邊的條數(shù) for (i=0;iG.vexsi; /一維數(shù)組存放頂點值 for (i=0;iG.vexnum;+ +i ) /二維數(shù)組賦初值 for (j=0;jG.vexnum;+ +j ) G.arcsij= INFINITY ; /即將做為初值存入矩陣的各行各列 for (k=0;kv1 v2 w; i=locatevex(G,v1); j=locatevex(G,v2); /求頂點v1,v2在圖中的位置 G.arcsij.adj=w; G.arcsji.adj=w; /無向網(wǎng)的鄰接矩陣是對稱的 return OK;/CreateUDN此處的locatevex(G,vi)是一個對一維數(shù)組G

15、.vexsG.vexnum進行搜索查找vi在圖G中的位置的函數(shù)子程序；請同學們自己編寫之。參考：int locatevex(MGraph G, VRType v) int k,i; k=-1; for (i=0;iG.kind; /輸入圖的種類 switch(G.kind) case 0: return CreateAL0(G); /DG case 1: return CreateAL1(G); /DN case 2: return CreateAL2(G); /UDG case 3: return CreateAL3(G); /UDN default : return ERROR;/Crea

16、teGraph19二、存儲結構二、存儲結構*以無向圖為例,即當用戶輸入圖的類型標志為2時,有：Status CreateAL2(ALGraph &G) cinG.vexnum G.arcnum; /輸入頂點數(shù)和弧的條數(shù) n= G.vexnum; e= G.arcnum; G.kind=2; for (i=0;iG.verticesi.data; G.verticesi.firstarc=NULL; /輸入n個頂點的值 for (k=1;kvt vh; /輸入一條邊的兩個頂點的值 i=locatevex(G,vt); j=locatevex(G,vh); p=new Arcnode; /申請一個弧結點存放序號申請一個弧結點存放序號j,并并 p-adjvex=j; /頭插法將其插入到序號為i的頂點的單鏈表（即第i個單鏈表）的表首 p-nextarc=G.verticei.firstarc; G.verticei.firstarc=p; p= new Arcnode; /由于邊可視為對稱的兩條弧，故 /再申請一個弧結點存放序號i, 并將其插入到序號為j的頂點的單鏈表的表首 p-adjvex=i; p-ne