圖圖主要內容圖的基本概念圖的存儲圖的連通性圖的生成樹圖遍歷實踐項目：圖遍歷演示程序主要內容圖的基本概念圖的應用公交網絡系統最短路徑查詢物流系統運輸系統圖的應用公交網絡系統基本概念圖：

圖是由頂點集合(vertex)及頂點間的關系集合組成的一種數據結構：

Graph＝(V,E)

其中

V={x|x

某個數據對象}

是頂點的有窮非空集合；

E={(x,y)|x,y

V}

或

E={<x,y>|x,y

V&&Path(x,y)}

是頂點之間關系的有窮集合，也叫做邊(edge)集合。Path(x,y)表示從x到y的一條單向通路,它是有方向的。基本概念圖：圖是由頂點集合(vertex)及頂點間的有向圖和無向圖00001111222265433無向圖：圖的每條邊都沒有方向，即邊的2個頂點沒有次序關系（1，0），（0，1）是同一條邊有向圖：圖的每條邊都是有方向的，即邊的2個頂點有次序關系。<0,1>，<1,0>是2條邊有向圖和無向圖00001111222265433無向圖：圖帶權圖（也稱網）權：圖的邊上的具有特定含義的數值稱為權。帶權圖：圖的每條邊都帶有一個權，這樣的圖稱為帶權圖，也稱網。BACD95234BAC523帶權圖（也稱網）權：圖的邊上的具有特定含義的數值稱為權。BA子圖鄰接頂點如果(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點。子圖設有兩個圖G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,則稱圖G’是圖G的子圖。0123子圖0130123023子圖鄰接頂點如果(u,v)是E(G)中的一條頂點的度和路徑、路徑長度0123與頂點關聯的邊數。頂點0的度為20－1的路徑和路徑長度：0-3-2-1，路徑長度為30-1，路徑長度為10-3-2-1-0-1，路徑長度為5BACD9523入度為2出度為1頂點的度和路徑、路徑長度0123與頂點關聯的邊數。頂點0的度連通圖與連通分量在無向圖中，如果任意2個頂點之間都有路徑，則稱該無向圖是連通圖。無向圖的極大連通子圖稱為連通分量。連通圖與連通分量在無向圖中，如果任意2個頂點之間都有路徑，強連通圖與強連通分量

在有向圖中，如果任意2個頂點之間都存在可到達的路徑，則稱該有向圖是強連通圖。有向圖的極大連通子圖稱為該有向圖的強連通分量。強連通圖與強連通分量在有向圖中，如果任意2個頂點之間都存生成樹一個n個頂點的連通圖的生成樹是一個極小連通子圖，它含有圖中所有的頂點，但具有足以構成一棵樹的n-1條邊。生成樹一個n個頂點的連通圖的生成樹是一個極小連通子圖，它含有圖的存儲鄰接矩陣鄰接表圖的存儲鄰接矩陣鄰接矩陣

(AdjacencyMatrix）在圖的鄰接矩陣表示中，有一個記錄各個頂點信息的頂點表，還有一個表示各個頂點之間關系的鄰接矩陣。設圖A=(V,E)是一個有n個頂點的圖,圖的鄰接矩陣是一個二維數組

A.edge[n][n]，定義：鄰接矩陣(AdjacencyMatrix）在圖的鄰接矩陣無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。0123012無向圖的鄰接矩陣是對稱的;0123012鄰接表(AdjacencyList)1.無向圖的鄰接表

同一個頂點發出的邊鏈接在同一個邊鏈表中，每一個鏈結點代表一條邊(邊結點),結點中有另一頂點的下標

adjvex和指針

nextarc。ABCDdata

firstarcABCD0123adjvexnextarc130210adjvexnextarc鄰接表(AdjacencyList)1.無向圖的鄰接表A2.有向圖的鄰接表和逆鄰接表ABCdatafirstarcABC012鄰接表(出邊表)ABC012逆鄰接表(入邊表)102011adjvexnextarcadjvexnextarcadjvexnextarcdatafirstarc2.有向圖的鄰接表和逆鄰接表ABCdatafirstarcBACD69528ABCD01231

53

62

83

21

9(出邊表)(頂點表)Adjvexinfonextarcdatafirstarc3.網絡(帶權圖)的鄰接表BACD69528A01536283圖的遍歷從已給的連通圖中某一頂點出發，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷(GraphTraversal)。圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經訪問過的頂點。圖的遍歷的分類:深度優先搜索遍歷

DFS(DepthFirstSearch)廣度優先搜索遍歷

BFS(BreadthFirstSearch)圖的遍歷從已給的連通圖中某一頂點出發，沿著一些邊訪遍圖中所深度優先搜索遍歷-

DFSACDEGBFIHACDEGBFIH123456789123456789前進回退深度優先搜索過程深度優先生成樹深度優先搜索遍歷-DFSACDEGBFIHACDEGBFDFS

在訪問圖中某一起始頂點v

后,由v出發,訪問它的任一鄰接頂點w1;再從w1

出發,訪問與w1鄰接但還沒有訪問過的頂點w2;然后再從w2

出發,進行類似的訪問,…如此進行下去,直至到達所有的鄰接頂點都被訪問過的頂點u為止。接著,退回一步,退到前一次剛訪問過的頂點,看是否還有其它沒有被訪問的鄰接頂點。如果有,則訪問此頂點,之后再從此頂點出發,進行與前述類似的訪問;如果沒有,就再退回一步進行搜索。重復上述過程,直到連通圖中所有頂點都被訪問過為止。深度優先搜索遍歷(

DFS)基本思想DFS在訪問圖中某一起始頂點v后,由v出廣度優先搜索遍歷(BFS)ACDEGBFIHACDEGBFH123456789123456789廣度優先搜索過程廣度優先生成樹I廣度優先搜索遍歷(BFS)ACDEGBFIHACDEGBFBFS在訪問了起始頂點v

之后,由

v出發,依次訪問

v的各個未被訪問過的鄰接頂點w1,w2,…,wt,然后再順序訪問

w1,w2,…,wt的所有還未被訪問過的鄰接頂點。再從這些訪問過的頂點出發，再訪問它們的所有還未被訪問過的鄰接頂點，…如此做下去，直到圖中所有頂點都被訪問到為止。廣度優先搜索是一種分層的搜索過程,每向前走一步可能訪問一批頂點,不像深度優先搜索那樣有往回退的情況。因此,廣度優先搜索不是一個遞歸的過程。廣度優先搜索遍歷(BFS)基本思想BFS在訪問了起始頂點v之后,由v出發,依次訪問實踐項目設計步驟定義圖形結點GraphNode.java定義操作GraphADT.java定義圖形結構Graph.java使用圖形結構GraphUser.java實踐項目設計步驟定義圖形結點GraphNode.java圖遍歷演示程序UML圖圖遍歷演示程序UML圖主程序運行界面主程序運行界面實戰演練（100頁）對例題5-1進行如下修改1）在Graph類中增加一個方法，輸出圖的鄰接矩陣。2）在Graph類中增加一個方法可以刪除某條邊。3）用非遞歸算法實現Graph類中的深度優先搜索遍歷方法。4）在GraphDemo類中測試上面的方法。實戰演練（100頁）對例題5-1進行如下修改圖圖主要內容圖的基本概念圖的存儲圖的連通性圖的生成樹圖遍歷實踐項目：圖遍歷演示程序主要內容圖的基本概念圖的應用公交網絡系統最短路徑查詢物流系統運輸系統圖的應用公交網絡系統基本概念圖：

圖是由頂點集合(vertex)及頂點間的關系集合組成的一種數據結構：

Graph＝(V,E)

其中

V={x|x

某個數據對象}

是頂點的有窮非空集合；

E={(x,y)|x,y

V}

或

E={<x,y>|x,y

V&&Path(x,y)}

是頂點之間關系的有窮集合，也叫做邊(edge)集合。Path(x,y)表示從x到y的一條單向通路,它是有方向的。基本概念圖：圖是由頂點集合(vertex)及頂點間的有向圖和無向圖00001111222265433無向圖：圖的每條邊都沒有方向，即邊的2個頂點沒有次序關系（1，0），（0，1）是同一條邊有向圖：圖的每條邊都是有方向的，即邊的2個頂點有次序關系。<0,1>，<1,0>是2條邊有向圖和無向圖00001111222265433無向圖：圖帶權圖（也稱網）權：圖的邊上的具有特定含義的數值稱為權。帶權圖：圖的每條邊都帶有一個權，這樣的圖稱為帶權圖，也稱網。BACD95234BAC523帶權圖（也稱網）權：圖的邊上的具有特定含義的數值稱為權。BA子圖鄰接頂點如果(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點。子圖設有兩個圖G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,則稱圖G’是圖G的子圖。0123子圖0130123023子圖鄰接頂點如果(u,v)是E(G)中的一條頂點的度和路徑、路徑長度0123與頂點關聯的邊數。頂點0的度為20－1的路徑和路徑長度：0-3-2-1，路徑長度為30-1，路徑長度為10-3-2-1-0-1，路徑長度為5BACD9523入度為2出度為1頂點的度和路徑、路徑長度0123與頂點關聯的邊數。頂點0的度連通圖與連通分量在無向圖中，如果任意2個頂點之間都有路徑，則稱該無向圖是連通圖。無向圖的極大連通子圖稱為連通分量。連通圖與連通分量在無向圖中，如果任意2個頂點之間都有路徑，強連通圖與強連通分量

在有向圖中，如果任意2個頂點之間都存在可到達的路徑，則稱該有向圖是強連通圖。有向圖的極大連通子圖稱為該有向圖的強連通分量。強連通圖與強連通分量在有向圖中，如果任意2個頂點之間都存生成樹一個n個頂點的連通圖的生成樹是一個極小連通子圖，它含有圖中所有的頂點，但具有足以構成一棵樹的n-1條邊。生成樹一個n個頂點的連通圖的生成樹是一個極小連通子圖，它含有圖的存儲鄰接矩陣鄰接表圖的存儲鄰接矩陣鄰接矩陣

(AdjacencyMatrix）在圖的鄰接矩陣表示中，有一個記錄各個頂點信息的頂點表，還有一個表示各個頂點之間關系的鄰接矩陣。設圖A=(V,E)是一個有n個頂點的圖,圖的鄰接矩陣是一個二維數組

A.edge[n][n]，定義：鄰接矩陣(AdjacencyMatrix）在圖的鄰接矩陣無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。0123012無向圖的鄰接矩陣是對稱的;0123012鄰接表(AdjacencyList)1.無向圖的鄰接表

同一個頂點發出的邊鏈接在同一個邊鏈表中，每一個鏈結點代表一條邊(邊結點),結點中有另一頂點的下標

adjvex和指針

nextarc。ABCDdata

firstarcABCD0123adjvexnextarc130210adjvexnextarc鄰接表(AdjacencyList)1.無向圖的鄰接表A2.有向圖的鄰接表和逆鄰接表ABCdatafirstarcABC012鄰接表(出邊表)ABC012逆鄰接表(入邊表)102011adjvexnextarcadjvexnextarcadjvexnextarcdatafirstarc2.有向圖的鄰接表和逆鄰接表ABCdatafirstarcBACD69528ABCD01231

53

62

83

21

9(出邊表)(頂點表)Adjvexinfonextarcdatafirstarc3.網絡(帶權圖)的鄰接表BACD69528A01536283圖的遍歷從已給的連通圖中某一頂點出發，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷(GraphTraversal)。圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經訪問過的頂點。圖的遍歷的分類:深度優先搜索遍歷

DFS(DepthFirstSearch)廣度優先搜索遍歷

BFS(BreadthFirstSearch)圖的遍歷從已給的連通圖中某一頂點出發，沿著一些邊訪遍圖中所深度優先搜索遍歷-

DFSACDEGBFIHACDEGBFIH123456789123456789前進回退深度優先搜索過程深度優先生成樹深度優先搜索遍歷-DFSACDEGBFIHACDEGBFDFS

在訪問圖中某一起始頂點v

后,由v出發,訪問它的任一鄰接頂點w1;再從w1

出發,訪問與w1鄰接但還沒有訪問過的頂點w2;然后再從w2

出發,進行類似的訪問,…如此進行下去,直至到達所有的鄰接頂點都被訪問過的頂點u為止。接著,退回一步,退到前一次剛訪問過的頂點,看是否還有其它沒有被訪問的鄰接頂點。如果有,則訪問此頂點,之后再從此頂點出發,進行與前述類似的訪問;如果沒有,就再退回一步進行搜索。重復上述過程,直到連通圖中所有頂點都被訪問過為止。深度優先搜索遍歷(

DFS)基本思想DFS在訪問圖中某一起始頂點v后,由v出廣度優先搜索遍歷(BFS)A