第七章 圖(2).ppt

第七章圖 圖的定義圖的存儲(chǔ)方式圖的連通性最小生成樹有向無環(huán)圖的應(yīng)用 7 2圖的存儲(chǔ)方式 1 鄰接矩陣表示法 2 鄰接表表示法 鄰接表 AdjacencyList 表示法實(shí)際上是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 基本思想 為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表 第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊 有向圖中指以Vi為尾的弧 鄰接表的結(jié)點(diǎn)結(jié)構(gòu) 1 頂點(diǎn)表 由所有表頂點(diǎn)以順序結(jié)構(gòu) 向量 的形式存儲(chǔ) 以便可以隨機(jī)訪問任一頂點(diǎn)的單鏈表 頂點(diǎn)表結(jié)構(gòu)由兩部分構(gòu)成 數(shù)據(jù)域 vexdata 用于存儲(chǔ)頂點(diǎn)的名或其它有關(guān)信息 鏈域 firstarc 用于指向鏈表中第一個(gè)頂點(diǎn) 即與頂點(diǎn)vi鄰接的第一個(gè)鄰接點(diǎn) 2 邊表 由表示圖中頂點(diǎn)間鄰接關(guān)系的n個(gè)邊鏈表組成 它由三部分組成 鄰接點(diǎn)域 adjvex 用于存放與頂點(diǎn)vi相鄰接的頂點(diǎn)在圖中的位置 鏈域 nextarc 用于指向與頂點(diǎn)vi相關(guān)聯(lián)的下一條邊或弧的結(jié)點(diǎn) 數(shù)據(jù)域 info 用于存放與邊或弧相關(guān)的信息 如賦權(quán)圖中每條邊或弧的權(quán)值等 無向圖的鄰接表 同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中 每一個(gè)鏈結(jié)點(diǎn)代表一條邊 邊結(jié)點(diǎn) 如何求頂點(diǎn)i的度 頂點(diǎn)i的邊表中結(jié)點(diǎn)的個(gè)數(shù) 有向圖的鄰接表 可見 在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧 如何求頂點(diǎn)i的出度 頂點(diǎn)i的出邊表中結(jié)點(diǎn)的個(gè)數(shù) 如何求頂點(diǎn)i的入度 各頂點(diǎn)的出邊表中以頂點(diǎn)i為終點(diǎn)的結(jié)點(diǎn)個(gè)數(shù) 有向圖的逆鄰接表 在有向圖的鄰接表中 對(duì)每個(gè)頂點(diǎn) 鏈接的是指向該頂點(diǎn)的弧 網(wǎng)的鄰接表 鄰接表的結(jié)點(diǎn)結(jié)構(gòu) defineMaxVertexNum100typedefstructnode intadjvex 鄰接點(diǎn)域 存放與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置structnode next 鏈域 指示下一條邊或弧intinfo EdgeNode typedefstructtnode 表頭接點(diǎn) VertexTypevexdata 存放頂點(diǎn)信息EdgeNode firstarc 指示第一個(gè)鄰接點(diǎn) VertexNode typedefVertexNodeAdjList MaxVertexNum AdjList是鄰接表類型typedefstruct 對(duì)于簡單的應(yīng)用 無須定義此類型 可直接使用AdjList類型 AdjListadjlist 鄰接表intn e 圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) ALGraph voidCreatALGraph ALGraph G inti j k EdgeNode s printf 請(qǐng)輸入頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù) scanf d d 建立邊表for k 0 kn k printf 請(qǐng)輸入邊的兩個(gè)頂點(diǎn) scanf d d 將s插入頂點(diǎn)Vj的邊表頭部 鄰接表表示法特點(diǎn) 1 無向圖鄰接表邊結(jié)點(diǎn)數(shù)是邊數(shù)的兩倍 2 頂點(diǎn)vi的度 在無向圖中等于第i個(gè)鏈表中的結(jié)點(diǎn)數(shù) 在有向圖鄰接表中 第i行的結(jié)點(diǎn)數(shù)等于頂點(diǎn)i的出度 在有向圖逆鄰接表中 第i行的結(jié)點(diǎn)數(shù)等于頂點(diǎn)i的入度 3 在鄰接表上容易找到任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn) 4 設(shè)存儲(chǔ)頂點(diǎn)的一維數(shù)組大小為n 圖的頂點(diǎn)數(shù)n G占用存儲(chǔ)空間 n e G占用存儲(chǔ)空間與它的頂點(diǎn)數(shù)和邊數(shù)有關(guān) 適用于邊稀疏的圖 3 有向圖的十字鏈表表示法 十字鏈表 OrthogonalList 是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 我們也可以把它看成是將有向圖的鄰接表和逆鄰接表結(jié)合起來形成的一種鏈表 有向圖中的每一條弧對(duì)應(yīng)十字鏈表中的一個(gè)弧結(jié)點(diǎn) 同時(shí)有向圖中的每個(gè)頂點(diǎn)在十字鏈表中對(duì)應(yīng)有一個(gè)結(jié)點(diǎn) 叫做頂點(diǎn)結(jié)點(diǎn) 弧的結(jié)點(diǎn)結(jié)構(gòu) 弧尾頂點(diǎn)位置弧頭頂點(diǎn)位置弧的相關(guān)信息 指向弧頭相同的下一條弧 指向弧尾相同的下一條弧 typedefstructnode 弧的結(jié)構(gòu)表示inttailvex headvex InfoType info structnode hlink tlink EdgeNode tailvexheadvexhlinktlinkinfo 頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu) datafirstinfirstout 指向該頂點(diǎn)的第一條入弧 指向該頂點(diǎn)的第一條出弧 typedefstructvnode 頂點(diǎn)的結(jié)構(gòu)表示VertexTypedata EdgeNode firstin firstout VertexNode 0 1 2 3 十字鏈表的優(yōu)點(diǎn) 在十字鏈表中既能夠很容易地找到以vi為尾的弧 也能夠容易地找到以vi為頭的弧 因此對(duì)于有向圖 若采用十字鏈表作為存儲(chǔ)結(jié)構(gòu) 則很容易求出頂點(diǎn)vi的度 4 無向圖的鄰接多重表表示法 鄰