數(shù)據(jù)結構與算法

—圖主講教員:段凌宇2014年5月16日

北京大學信息科學與技術學院，轉載或翻印必究北京大學信息學院，轉載或翻印必究Page2路徑（path）在圖G=(V，E)中，若存在頂點序列Vp，Vi1，Vi2，…，Vin，Vq，使得（Vp，Vi1），(Vi1，Vi2)，…，(Vin，Vq)（有向圖，<Vp，Vi1>，<Vi1，Vi2>，…，<Vin，Vq>）都在E中，則稱從頂點Vp到頂點Vq存在一條路徑。簡單路徑（simplepath）路徑上的頂點，除了Vp

，Vq可以相同外，其他頂點都不相同(只可以發(fā)生在Vp

，Vq之間)。路徑長度（length）:路徑上的邊數(shù)北京大學信息學院，轉載或翻印必究Page3回路（cycle，也稱為環(huán)）路徑上某個頂點與其本身相連接簡單回路（simplecycle）無環(huán)圖（acyclicgraph）不帶回路的圖有向無環(huán)圖（directedacyclicgraph，簡寫為DAG）北京大學信息學院，轉載或翻印必究Page4有根的圖一個有向圖中，若存在一個頂點V0，從此頂點有路徑可以到達圖中其它所有頂點，則稱此有向圖為有根的圖，V0稱作圖的根。連通的圖（connected）對無向圖

G=（V，E）而言，如果從V1到V2有一條路徑（從V2到V1也一定有一條路徑），則稱V1和V2是連通的（connected）；若圖G中任意兩個頂點都是連通的，則稱無向圖G是連通的。強連通:針對有向圖北京大學信息學院，轉載或翻印必究Page5連通分支或者連通分量（connectedcomponent）無向圖的最大連通子圖。強連通分支（強連通分量）:針對有向圖。網絡帶權的連通圖。自由樹（freetree）不帶有簡單回路的無向圖；是連通的，并且具有|V|-1條邊。北京大學信息學院，轉載或翻印必究Page6大綱6.1圖的基本概念6.2圖的抽象數(shù)據(jù)類型6.3圖的存儲結構6.4圖的周游（深度、廣度、拓撲）6.5最短路徑問題6.6最小支撐樹北京大學信息學院，轉載或翻印必究Page76.2圖的抽象數(shù)據(jù)類型classEdge{public: intfrom,to,weight;

Edge(){from=-1;to=-1;weight=0;}Edge(intf,intt,intw){from=f;to=t;weight=w;}booloperator>(EdgeoneEdge){returnweight>oneEdge.weight;}booloperator<(EdgeoneEdge){returnweight<oneEdge.weight;}};北京大學信息學院，轉載或翻印必究Page8classGraph{public: intnumVertex;intnumEdge;int*Mark;//標志位用來標記某頂點是否被訪問過int*Indegree;//保存有向圖的頂點的入度的數(shù)組北京大學信息學院，轉載或翻印必究Page9Graph(intnumVert){numVertex=numVert;numEdge=0;Indegree=newint[numVertex];Mark=newint[numVertex];for(inti=0;i<numVertex;i++){Mark[i]=UNVISITED;Indegree[i]=0;}}~Graph(){delete[]Mark;delete[]Indegree;}北京大學信息學院，轉載或翻印必究Page10intVerticesNum(){//返回圖的頂點個數(shù)returnnumVertex;}

intEdgesNum(){//返回圖的邊數(shù)returnnumEdge;}

//oneEdge是邊，則返回TRUE，否則返回FALSEboolIsEdge(EdgeoneEdge){if(oneEdge.weight>0&&oneEdge.weight<INFINITY&&oneEdge.to>=0)

returntrue;elsereturnfalse;}

北京大學信息學院，轉載或翻印必究Page11//返回邊oneEdge的始點intFromVertex(EdgeoneEdge){returnoneEdge.from;

}//返回邊oneEdge的終點

intToVertex(EdgeoneEdge)

{returnoneEdge.to;

}//返回邊oneEdge的權

intWeight(EdgeoneEdge){

returnoneEdge.weight;

}北京大學信息學院，轉載或翻印必究Page12

//返回與頂點oneVertex相關聯(lián)的第一條邊

virtualEdgeFirstEdge(intoneVertex)=0;//返回與邊PreEdge有相同關聯(lián)頂點的下一條邊

virtualEdgeNextEdge(EdgepreEdge)=0;//添加一條邊virtualvoidsetEdge(intfromVertex,inttoVertex,intweight)=0;//刪一條邊

virtualvoiddelEdge(intfromVertex,intoVertex)=0;純虛函數(shù)是一種特殊的虛函數(shù)，它的一般格式如下:virtual<返回值類型>

<函數(shù)名>

(<參數(shù)表>)=0;在許多情況下，在基類中不能對虛函數(shù)給出有意義的實現(xiàn)，而把它說明為純虛函數(shù)，它的實現(xiàn)留給該基類的派生類去做。這就是純虛函數(shù)的作用。

北京大學信息學院，轉載或翻印必究Page13抽象類帶有純虛函數(shù)的類稱為抽象類；抽象類是一種特殊的類，它是為了抽象和設計建立的，處于繼承層次結構的較上層。抽象類將有關的組織置于一個繼承層次結構中，由它提供一個公共的根，相關的子類從這個根派生出來。繼承是面向對象設計中重要的機制，支持層次分類的觀點。繼承使得程序員可以在一個較一般的類的基礎上很快地建立一個新類，而不必從零開始設計每個類。在現(xiàn)實世界中，許多實體或概念不是孤立的，它們具有共同的特征，但也有細微的差別，人們使用層次分類的方法可以描述這些實體或概念之間的相似點和不同點。

北京大學信息學院，轉載或翻印必究Page14抽象類刻畫了一組操作接口的通用語義，這些語義可以傳給繼承的子類。一般而言，抽象類只描述一組子類共同的操作接口，而完整的實現(xiàn)留給子類完成。

virtualEdgeFirstEdge(intoneVertex)=0;virtualEdgeNextEdge(EdgepreEdge)=0;virtualvoidsetEdge(intfromVertex,inttoVertex,intweight)=0;virtualvoiddelEdge(intfromVertex,intoVertex)=0;北京大學信息學院，轉載或翻印必究Page15抽象類僅允許作為基類來使用；也就是說，其純虛函數(shù)的實現(xiàn)必須由派生類給出。如果派生類沒有重新定義純虛函數(shù)，即派生類只是繼承基類的純虛函數(shù)，則這個派生類仍然還是一個抽象類。如果派生類中給出了所有基類純虛函數(shù)的實現(xiàn)，則該派生類就不再是抽象類了，成為一個可以建立對象的具體類了。

北京大學信息學院，轉載或翻印必究Page16大綱6.1圖的基本概念6.2圖的抽象數(shù)據(jù)類型6.3圖的存儲結構6.4圖的周游（深度、廣度、拓撲）6.5最短路徑問題6.6最小支撐樹北京大學信息學院，轉載或翻印必究Page176.3圖的存儲結構6.3.1圖的相鄰矩陣表示法（adjacencymatrix）6.3.2圖的鄰接表表示法（adjacencylist）鄰接多重表表示法（adjacencymultilist）北京大學信息學院，轉載或翻印必究Page186.3.1圖的相鄰矩陣表示法相鄰矩陣:表示頂點間相鄰關系的矩陣。若G是一個具有n個頂點的圖，則G的相鄰矩陣如下定義：若（Vi，Vj）（或<Vi，Vj>）是圖G的邊，則A[i,j]=1若（Vi，Vj）（或<Vi，Vj>）不是圖G的邊，則A[i,j]=0，相鄰矩陣的空間代價為O(n2)北京大學信息學院，轉載或翻印必究Page19圖的相鄰矩陣表示法

示例A7=北京大學信息學院，轉載或翻印必究Page20圖的相鄰矩陣表示法

示例A4=北京大學信息學院，轉載或翻印必究Page21圖的相鄰矩陣表示法

程序實現(xiàn)classGraphm:publicGraph{private: int**matrix;public:Graphm(intnumVert):Graph(numVert){inti,j;matrix=(int**)newint*[numVert];for(i=0;i<numVertex;i++)matrix[i]=newint[numVertex];for(i=0;i<numVertex;i++)for(j=0;j<numVertex;j++)matrix[i][j]=0;}北京大學信息學院，轉載或翻印必究Page22圖的相鄰矩陣表示法

程序實現(xiàn)classGraphm:publicGraph{private: int**matrix;public:Graphm(intnumVert):Graph(numVert){inti,j;matrix=(int**)newint*[numVert];for(i=0;i<numVertex;i++)matrix[i]=newint[numVertex];for(i=0;i<numVertex;i++)for(j=0;j<numVertex;j++)matrix[i][j]=0;}表達式:publicGraph表示Graphm是從Graph類中派生出來的,它繼承了所有屬于Graph的數(shù)據(jù)成員和成員函數(shù)(關鍵字public使Graph的所有公有成員在Graphm中仍為公有).這個構造函數(shù)的成員初始化符表調用基類的構造函數(shù)Graph，傳給它的值要賦給該基類中定義的數(shù)據(jù)成員。在初始化完Graph后，Graphm接著初始化數(shù)據(jù)成員。北京大學信息學院，轉載或翻印必究Page23~Graphm(){for(inti=0;i<numVertex;i++)delete[]matrix[i];delete[]matrix;}EdgeFirstEdge(intoneVertex){EdgemyEdge;myEdge.from=oneVertex;myEdge.to=-1;for(inti=0;i<numVertex;i++){if(matrix[oneVertex][i]!=0){myEdge.to=i;myEdge.weight=matrix[oneVertex][i];break;}}returnmyEdge;}北京大學信息學院，轉載或翻印必究Page24EdgeNextEdge(EdgepreEdge){EdgemyEdge;myEdge.from=preEdge.from;myEdge.to=-1;for(inti=preEdge.to+1;i<numVertex;i++){if(matrix[preEdge.from][i]!=0){myEdge.to=i;myEdge.weight=matrix[preEdge.from][i];break;}}returnmyEdge;}北京大學信息學院，轉載或翻印必究Page25voidsetEdge(intfrom,intto,intweight){ifmatrix[from][to]<=0){numEdge++;Indegree[to]++;}matrix[from][to]=weight;}voiddelEdge(intfrom,intto){ifmatrix[from][to]>0){numEdge--;Indegree[to]--;}matrix[from][to]=0;}北京大學信息學院，轉載或翻印必究Page266.3.2圖的鄰接表表示法

示例北京大學信息學院，轉載或翻印必究Page27G7的出邊表G7的入邊表北京大學信息學院，轉載或翻印必究Page28圖的鄰接表存儲空間n個頂點m條邊的無向圖需用(n+2m)個存儲單元n個頂點m條邊的有向圖需用(n+m)個存儲單元北京大學信息學院，轉載或翻印必究Page29圖的鄰接多重表表示法

無向圖G6的鄰接多重表表示此邊的兩個頂點的序號第一個頂點相關聯(lián)的下一條邊指向與第二個頂點相關聯(lián)的下一條邊北京大學信息學院，轉載或翻印必究Page30圖的鄰接多重表表示法將鄰接表表示中代表同一條邊的兩個表目合為一個表目在以處理圖的邊為主，且要求每條邊處理一次的實際應用中特別有用。北京大學信息學院，轉載或翻印必究Page31鄰接多重表（有向圖）G7的鄰接多重表表示G7的出邊表G7的入邊表指向以此頂點為始點的第一條邊指向以此頂點為終點的第一條邊指向始點與本邊始點相同的下一條邊指向終點與本邊終點相同的下一條邊北京大學信息學院，轉載或翻印必究Page32有向圖鄰接多重表頂點表第一個指針指向以此頂點為始點的第一條邊第二個指針指向以此頂點為終點的第一條邊邊表第一個指針指向始點與本邊始點相同的下一條邊第二個指針指向終點與本邊終點相同的下一條邊僅用表中第一個鏈便得到有向圖的出邊表；

僅用表中第二個鏈便得到有向圖的入邊表。北京大學信息學院，轉載或翻印必究Page33大綱6.1圖的基本概念6.2圖的抽象數(shù)據(jù)類型6.3圖的存儲結構6.4圖的周游（深度、廣度、拓撲）6.5最短路徑問題6.6最小支撐樹北京大學信息學院，轉載或翻印必究Page346.4圖的周游

(Graphtraversal)給出一個圖G和其中任意一個頂點V0，從V0出發(fā)系統(tǒng)地訪問G中所有的頂點，每個頂點訪問一次，這叫做圖的周游。圖的周游的典型算法從一個頂點出發(fā)，試探性訪問其余頂點，同時考慮：從一頂點出發(fā)，可能不能到達所有其它的頂點，如非連通圖；也可能會陷入死循環(huán)，如存在回路的圖。解決辦法為圖的每個頂點保留一個標志位（markbit）；算法開始時，所有頂點的標志位置零；在周游的過程中，當某個頂點被訪問，其標志位標記為已訪問。北京大學信息學院