一，概述

彌諾陶洛斯（Minotaur）是希臘神話中半人半牛的怪物，它藏身于一個(gè)精心設(shè)計(jì)的迷宮之中。這個(gè)迷宮的結(jié)構(gòu)極其復(fù)雜，一般人一旦進(jìn)入其中，都休想走出來(lái)。不過(guò)，在公主阿里阿德涅（Ariadne）的幫助下，古希臘英雄特修斯（Theseus）還是想出了一個(gè)走出迷宮的方法。特修斯帶上一團(tuán)線去闖迷宮，在入口處，他將繩線的一頭綁在門(mén)上。然后，他不斷查找迷宮的各個(gè)角落，而繩線的另一頭則始終抓在他的手里，跟隨他穿梭于蜿蜒曲折的迷宮之中。借助如此簡(jiǎn)單的工具，特修斯不僅終于找到了怪物并將其殺死，而且還帶著公主輕松地走出了迷宮。

特修斯之所以能夠成功，關(guān)鍵在于他借助繩線來(lái)掌握迷宮內(nèi)各個(gè)通道之間的聯(lián)接關(guān)系，而在很多的問(wèn)題中，掌握類似的信息都是至關(guān)重要的。通常，這類信息所反映的都是一組對(duì)象之間的二元關(guān)系，比如城市交通圖中聯(lián)接于不同點(diǎn)之間的街道，或 Internet 中聯(lián)接于兩個(gè) IP 之間的路由等。

在某種程度上，我們前面所討論過(guò)的樹(shù)結(jié)構(gòu)也可以攜帶和表示這種二元關(guān)系，只不過(guò)樹(shù)結(jié)構(gòu)中的這類關(guān)系僅限于父、子節(jié)點(diǎn)之間。然而在一般情況下，我們所需要的二元關(guān)系往往是定義在任意一對(duì)對(duì)象之間。實(shí)際上，這樣的二元關(guān)系恰恰正是圖論（Graph theory ）

** 圖（Graph）可以表示為 G = (V, E)：**

• 其中集合 V 中的對(duì)象稱作頂點(diǎn)（Vertex）；

• 而集合 E 中的每一元素都對(duì)應(yīng)于 V 中某一對(duì)頂點(diǎn)??說(shuō)明這兩個(gè)頂點(diǎn)之間存在某種關(guān)系??稱作邊（Edge）。

這里還約定 V 和 E 都是有限集，通常記 n = |V|、m = |E|。

二，無(wú)向圖、混合圖及有向圖

圖中的邊可以是沒(méi)有方向的，也可以是有方向的。

如果邊 e = (u, v)所對(duì)應(yīng)的頂點(diǎn) u 和 v 不是對(duì)等的，或者存在某種次序，就稱 e 為有向邊（Directed edge）。

如果 u 和 v 的次序無(wú)所謂，e 就是一條無(wú)向邊（Undirected edge）。

注意：無(wú)向邊(u, v)也可以記作(v, u)，而有向邊(u, v)和(v, u)則是不同的兩條邊。

（a）無(wú)向圖（b）混合圖（c）有向圖

頂點(diǎn)v的關(guān)聯(lián)邊的總數(shù)，稱為v的度數(shù)（Degree），記作deg(v)。以 （a）為例，有deg(a) = deg(c) = 3。

v 出邊總數(shù)稱作v的出度（Out-degree），記作outdeg(v)；
v入邊總數(shù)稱作v的入度（In-degree），記作indeg(v)。
以（c）為例，有outdeg(a) = indeg(a) = outdeg(c) = indeg(c) =3。

圖中所含的邊并不見(jiàn)得能構(gòu)成一個(gè)集合（Set），準(zhǔn)確地說(shuō)它們構(gòu)成了一個(gè)復(fù)集（Multiset）??其中允許出現(xiàn)重復(fù)的元素。

比如，若在某對(duì)頂點(diǎn)之間有多條無(wú)向邊，或者兩條有向邊的起點(diǎn)和終點(diǎn)
完全一樣，就屬于這種情況。這類重復(fù)的邊也稱作平行邊（Parallel e dges）或多重邊（Multiple edges）。例如，要是用頂點(diǎn)表示城市，用邊表示城市之間的飛機(jī)航線，則有可能在某一對(duì)城市之間存在多條航線；如果用頂點(diǎn)表示演員，則某兩位演員合演過(guò)的影片很有可能不止一部。

無(wú)論是無(wú)向圖還是有向圖，還有另一種特殊情況：與某條邊關(guān)聯(lián)的是同一個(gè)頂點(diǎn)（如上圖中的頂點(diǎn)a）??這樣的邊稱作** 自環(huán)（Self-loop）**。

不含上述特殊邊的圖，稱作簡(jiǎn)單圖（Simple graph）。對(duì)簡(jiǎn)單圖而言，其中的邊必然構(gòu)成一個(gè)集合，而且每條邊只能聯(lián)接于不同的頂點(diǎn)之間。本文我們討論的圖都限于簡(jiǎn)單圖。

三，通路、環(huán)路及可達(dá)分量

通路——所謂圖中的一條通路或路徑（Path），就是由（不一定互異的）m+1 個(gè)頂點(diǎn)與 m 條邊交替構(gòu)成的一個(gè)序列ρ = {v 0 , e 1 , v 1 , e 2 , v 2 , …, e m , v m }，m ≥ 0，而且 e i = (v i-1 , v i )，1 ≤ i ≤ m。

環(huán)路—— 長(zhǎng)度 m ≥ 1 的路徑，若第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)相同，則稱之為環(huán)路（Cycle）。

可達(dá)分量——對(duì)于指定的頂點(diǎn) s，從 s 可達(dá)的所有頂點(diǎn)所組成的集合，稱作 s 在 G 中對(duì)應(yīng)的可達(dá)分量，記作 V r (G, s)。

四，樹(shù)、森林和連通圖

無(wú)向圖 G = (V, E)：

若 G 中不含任何環(huán)路，則稱之為森林（Forest）。

連通的森林稱作樹(shù)（Tree）。

不難看出，森林中的每一連通分量都是一棵樹(shù)，反之亦然。

設(shè) G 為由 n 個(gè)頂點(diǎn)與 m 條邊組成一幅無(wú)向圖：

• （1）若 G 是連通的，則 m ≥ n-1；

• （2）若 G 是一棵樹(shù)，則 m = n-1；

• （3）若 G 是森林，則 m ≤ n-1。

五，圖 ADT

（這里以有向圖為例介紹圖結(jié)構(gòu)及其算法）
作為一種抽象數(shù)據(jù)類型，有向圖必須支持以下操作：

六，圖的實(shí)現(xiàn)

** 基于鄰接矩陣（Adjacency matrix）的圖的實(shí)現(xiàn) **

圖 ADT 有多種實(shí)現(xiàn)方式，其中最直接的就是基于鄰接矩陣（Adjacency matrix）的實(shí)現(xiàn)。

若圖 G 中包含 n 個(gè)頂點(diǎn)，我們就使用一個(gè) n×n 的方陣 A，并使每一頂點(diǎn)都分別對(duì)應(yīng)于某一行（列）。

既然圖所描述的是這些頂點(diǎn)各自對(duì)應(yīng)的元素之間的二元關(guān)系，故可以很自然地將任意一對(duì)元素 u 和 v 之間可能存在二元關(guān)系與矩陣 A 中對(duì)應(yīng)的單元 A[u, v]對(duì)應(yīng)起來(lái)：
1 或 true 表示存在關(guān)系，0 或 false 表示不存在關(guān)系。

這一矩陣中的各個(gè)單元分別描述了一對(duì)元素之間可能存在的鄰接關(guān)系，故此得名。

以上基于鄰接矩陣的實(shí)現(xiàn)方法直觀易懂、思路簡(jiǎn)明，而且能夠高效地實(shí)現(xiàn)圖的大多數(shù) ADT 操作。

但是矩陣結(jié)構(gòu)是靜態(tài)的，通常都是事先估計(jì)一個(gè)較大的整數(shù) N，然后創(chuàng)建一個(gè) N×N 的矩陣。

然而，圖的規(guī)模往往都是動(dòng)態(tài)變化的，因此如果 N 不是足夠大，極有可能出現(xiàn)因空間“不足”而無(wú)法加入新頂點(diǎn)的情況??而實(shí)際上，此時(shí)系統(tǒng)并非沒(méi)有更多空間可以提供。為了降低這種情況發(fā)生的概率，必須選用足夠大的 N，而如此一來(lái)，單元閑置的程度也將加劇。

** 鄰接表 **

由上面的分析可知，鄰接矩陣的空間效率之所以低，是因?yàn)槠渲写罅康膯卧鶎?duì)應(yīng)的邊有可能并未在圖中出現(xiàn)，這也是靜態(tài)向量結(jié)構(gòu)普遍的不足。

既然如此，為什么不將向量改進(jìn)為列表呢？實(shí)際上，按照這一思路的確可以導(dǎo)出圖結(jié)構(gòu)的另一種表示與實(shí)現(xiàn)形式——鄰接表（Adjacency list）。

基于列表實(shí)現(xiàn)的頂點(diǎn)與邊的結(jié)構(gòu)：

** 具體由以下3個(gè)接口和對(duì)應(yīng)的3個(gè)類實(shí)現(xiàn)：**

（有向）圖的頂點(diǎn)結(jié)構(gòu)接口：

package dsa.Graph;

import dsa.Iterator.Iterator;
import other.Position;

public interface Vertex {

    /*
     * （有向）圖的頂點(diǎn)結(jié)構(gòu)接口
     */
    // 常量
    final static int UNDISCOVERED = 0;// 尚未被發(fā)現(xiàn)的頂點(diǎn)
    final static int DISCOVERED = 1;// 已被發(fā)現(xiàn)的頂點(diǎn)
    final static int VISITED = 2;// 已訪問(wèn)過(guò)的頂點(diǎn)
    // 返回當(dāng)前頂點(diǎn)的信息

    public Object getInfo();

    // 將當(dāng)前頂點(diǎn)的信息更新為x，并返回原先的信息
    public Object setInfo(Object x);

    // 返回當(dāng)前頂點(diǎn)的出、入度
    public int outDeg();

    public int inDeg();

    // 返回當(dāng)前頂點(diǎn)所有關(guān)聯(lián)邊、關(guān)聯(lián)邊位置的迭代器
    public Iterator inEdges();

    public Iterator inEdgePositions();

    public Iterator outEdges();

    public Iterator outEdgePositions();

    // 取當(dāng)前頂點(diǎn)在所屬的圖的頂點(diǎn)集V中的位置
    public Position getVPosInV();

    // 讀取、設(shè)置頂點(diǎn)的狀態(tài)（DFS + BFS）
    public int getStatus();

    public int setStatus(int s);

    // 讀取、設(shè)置頂點(diǎn)的時(shí)間標(biāo)簽（DFS）
    public int getDStamp();

    public int setDStamp(int s);

    public int getFStamp();

    public int setFStamp(int s);

    // 讀取、設(shè)置頂點(diǎn)至起點(diǎn)的最短距離（BFS或BestFS）
    public int getDistance();

    public int setDistance(int s);

    // 讀取、設(shè)置頂點(diǎn)在的DFS、BFS、BestFS或MST樹(shù)中的父親
    public Vertex getBFSParent();

    public Vertex setBFSParent(Vertex s);
}

（有向）圖的邊結(jié)構(gòu)接口

package dsa.Graph;

import other.Position;

public interface Edge {

    /*
     * （有向）圖的邊結(jié)構(gòu)接口
     */
    // 常量
    final static int UNKNOWN = 0;// 未知邊
    final static int TREE = 1;// 樹(shù)邊
    final static int CROSS = 2;// 橫跨邊
    final static int FORWARD = 3;// 前向跨邊
    final static int BACKWARD = 4;// 后向跨邊
    // 返回當(dāng)前邊的信息（對(duì)于帶權(quán)圖，也就是各邊的權(quán)重）

    public Object getInfo();

    // 將當(dāng)前邊的信息更新為x，并返回原先的信息
    public Object setInfo(Object x);

    // 取當(dāng)前邊在所屬的圖的邊集E中的位置
    public Position getEPosInE();

    // 取v[i]在頂點(diǎn)集V中的位置（i=0或1，分別對(duì)應(yīng)于起點(diǎn)、終點(diǎn)）
    public Position getVPosInV(int i);

    // 當(dāng)前邊在其兩個(gè)端點(diǎn)的關(guān)聯(lián)邊集I(v[i])中的位置
    public Position getEPosInI(int i);

    // 讀取、設(shè)置邊的類別（針對(duì)遍歷）
    public int getType();

    public int setType(int t);
}

（有向）圖結(jié)構(gòu)接口

package dsa.Graph;

import dsa.Iterator.Iterator;
import other.Position;

public interface Graph {

    /*
     * （有向）圖結(jié)構(gòu)接口 
     */

    // 取圖中頂點(diǎn)、邊的數(shù)目
    public int vNumber();

    public int eNumber();

    // 取圖中所有頂點(diǎn)、頂點(diǎn)位置的迭代器
    public Iterator vertices();

    public Iterator vPositions();

    // 返回圖中所有邊、邊位置的迭代器
    public Iterator edges();

    public Iterator ePositions();

    // 檢測(cè)是否有某條邊從頂點(diǎn)u指向v
    public boolean areAdjacent(Vertex u, Vertex v);

    // 取從頂點(diǎn)u指向v的邊，若不存在，則返回null
    public Edge edgeFromTo(Vertex u, Vertex v);

    // 將頂點(diǎn)v從頂點(diǎn)集中刪除，并返回之
    public Vertex remove(Vertex v);

    // 將邊e從邊集中刪除，并返回之
    public Edge remove(Edge e);

    // 在頂點(diǎn)集V中插入新頂點(diǎn)v，并返回其位置
    public Position insert(Vertex v);

    // 在邊集E中插入新邊e，并返回其位置
    public Position insert(Edge e);
}

基于鄰接邊表實(shí)現(xiàn)圖的頂點(diǎn)結(jié)構(gòu)

package dsa.Graph;

import dsa.Iterator.Iterator;
import dsa.List.List;
import dsa.List.List_DLNode;
import other.Position;

public class Vertex_List implements Vertex {

    /*
     * 基于鄰接邊表實(shí)現(xiàn)圖的頂點(diǎn)結(jié)構(gòu)
     */

    // 變量
    protected Object info;// 當(dāng)前頂點(diǎn)中存放的數(shù)據(jù)元素
    protected Position vPosInV;// 當(dāng)前頂點(diǎn)在所屬的圖的頂點(diǎn)表V中的位置
    protected List outEdges;// 關(guān)聯(lián)邊表：存放以當(dāng)前頂點(diǎn)為尾的所有邊（的位置）
    protected List inEdges;// 關(guān)聯(lián)邊表：存放以當(dāng)前頂點(diǎn)為頭的所有邊（的位置）
    protected int status;// （在遍歷圖等操作過(guò)程中）頂點(diǎn)的狀態(tài)
    protected int dStamp;// 時(shí)間標(biāo)簽：DFS過(guò)程中該頂點(diǎn)被發(fā)現(xiàn)時(shí)的時(shí)刻
    protected int fStamp;// 時(shí)間標(biāo)簽：DFS過(guò)程中該頂點(diǎn)被訪問(wèn)結(jié)束時(shí)的時(shí)刻
    protected int distance;// 到指定起點(diǎn)的距離：BFS、Dijkstra等算法所確定該頂點(diǎn)到起點(diǎn)的距離
    protected Vertex bfsParent;// 在最短距離樹(shù)（BFS或BestFS）中的父親
    // 構(gòu)造方法：在圖G中引入一個(gè)屬性為x的新頂點(diǎn)

    public Vertex_List(Graph G, Object x) {
        info = x;// 數(shù)據(jù)元素
        vPosInV = G.insert(this);// 當(dāng)前頂點(diǎn)在所屬的圖的頂點(diǎn)表V中的位置
        outEdges = new List_DLNode();// 出邊表
        inEdges = new List_DLNode();// 入邊表
        status = UNDISCOVERED;
        dStamp = fStamp = Integer.MAX_VALUE;
        distance = Integer.MAX_VALUE;
        bfsParent = null;
    }

    // 返回當(dāng)前頂點(diǎn)的信息
    public Object getInfo() {
        return info;
    }

    // 將當(dāng)前頂點(diǎn)的信息更新為x，并返回原先的信息
    public Object setInfo(Object x) {
        Object e = info;
        info = x;
        return e;
    }

    // 返回當(dāng)前頂點(diǎn)的出、入度
    public int outDeg() {
        return outEdges.getSize();
    }

    public int inDeg() {
        return inEdges.getSize();
    }

    // 返回當(dāng)前頂點(diǎn)所有關(guān)聯(lián)邊、關(guān)聯(lián)邊位置的迭代器
    public Iterator inEdges() {
        return inEdges.elements();
    }

    public Iterator inEdgePositions() {
        return inEdges.positions();
    }

    public Iterator outEdges() {
        return outEdges.elements();
    }

    public Iterator outEdgePositions() {
        return outEdges.positions();
    }

    // 取當(dāng)前頂點(diǎn)在所屬的圖的頂點(diǎn)集V中的位置
    public Position getVPosInV() {
        return vPosInV;
    }

    // 讀取、設(shè)置頂點(diǎn)的狀態(tài)（DFS + BFS）
    public int getStatus() {
        return status;
    }

    public int setStatus(int s) {
        int ss = status;
        status = s;
        return ss;
    }

    // 讀取、設(shè)置頂點(diǎn)的時(shí)間標(biāo)簽（DFS）
    public int getDStamp() {
        return dStamp;
    }

    public int setDStamp(int s) {
        int ss = dStamp;
        dStamp = s;
        return ss;
    }

    public int getFStamp() {
        return fStamp;
    }

    public int setFStamp(int s) {
        int ss = fStamp;
        fStamp = s;
        return ss;
    }

    // 讀取、設(shè)置頂點(diǎn)至起點(diǎn)的最短距離（BFS）
    public int getDistance() {
        return distance;
    }

    public int setDistance(int s) {
        int ss = distance;
        distance = s;
        return ss;
    }

    // 讀取、設(shè)置頂點(diǎn)在的DFS、BFS、BestFS或MST樹(shù)中的父親
    public Vertex getBFSParent() {
        return bfsParent;
    }

    public Vertex setBFSParent(Vertex s) {
        Vertex ss = bfsParent;
        bfsParent = s;
        return ss;
    }
}

基于鄰接邊表實(shí)現(xiàn)圖的邊結(jié)構(gòu)

package dsa.Graph;

import dsa.Deque.DLNode;
import other.Position;

public class Edge_List implements Edge {

    /*
     * 基于鄰接邊表實(shí)現(xiàn)圖的邊結(jié)構(gòu)
     */

    // 變量
    protected Object info;// 當(dāng)前邊中存放的數(shù)據(jù)元素
    protected Position ePosInE;// 當(dāng)前邊在所屬的圖的邊表中的位置
    protected Position vPosInV[];// 當(dāng)前邊兩個(gè)端點(diǎn)在頂點(diǎn)表中的位置
    protected Position ePosInI[];// 當(dāng)前邊在其兩個(gè)端點(diǎn)的關(guān)聯(lián)邊表中的位置
    // 約定：第0（1）個(gè)頂點(diǎn)分別為尾（頭）頂點(diǎn)
    // 禁止頭、尾頂點(diǎn)相同的邊
    protected int type;// （經(jīng)過(guò)遍歷之后）邊被歸入的類別
    // 構(gòu)造方法：在圖G中，生成一條從頂點(diǎn)u到v的新邊（假定該邊尚不存在）

    public Edge_List(Graph G, Vertex_List u, Vertex_List v, Object x) {
        info = x;// 數(shù)據(jù)元素
        ePosInE = G.insert(this);// 當(dāng)前邊在所屬的圖的邊表中的位置
        vPosInV = new DLNode[2];// 當(dāng)前邊兩個(gè)端點(diǎn)在頂點(diǎn)表中的位置
        vPosInV[0] = u.getVPosInV();
        vPosInV[1] = v.getVPosInV();
        ePosInI = new DLNode[2];// 當(dāng)前邊在其兩個(gè)端點(diǎn)的關(guān)聯(lián)邊表中的位置
        ePosInI[0] = u.outEdges.insertLast(this);// 當(dāng)前邊加入u的鄰接（出）邊表
        ePosInI[1] = v.inEdges.insertLast(this);// 當(dāng)前邊加入v的鄰接（入）邊表
        type = UNKNOWN;
    }

    // 返回當(dāng)前邊的信息
    public Object getInfo() {
        return info;
    }

    // 將當(dāng)前邊的信息更新為x，并返回原先的信息
    public Object setInfo(Object x) {
        Object e = info;
        info = x;
        return e;
    }

    // 取當(dāng)前邊在所屬的圖的邊集E中的位置
    public Position getEPosInE() {
        return ePosInE;
    }

    // 取v[i]在頂點(diǎn)集V中的位置（i=0或1，分別對(duì)應(yīng)于起點(diǎn)、終點(diǎn)）
    public Position getVPosInV(int i) {
        return vPosInV[i];
    }

    // 當(dāng)前邊在其兩個(gè)端點(diǎn)的關(guān)聯(lián)邊集I(v[i])中的位置
    public Position getEPosInI(int i) {
        return ePosInI[i];
    }

    // 讀取、設(shè)置邊的類別（針對(duì)遍歷）
    public int getType() {
        return type;
    }

    public int setType(int t) {
        int tt = type;
        type = t;
        return tt;
    }
}

基于鄰接邊表實(shí)現(xiàn)圖結(jié)構(gòu)

package dsa.Graph;

import dsa.Iterator.Iterator;
import dsa.List.List;
import dsa.List.List_DLNode;
import other.Position;

public class Graph_List implements Graph {
    /*
     * 基于鄰接邊表實(shí)現(xiàn)圖結(jié)構(gòu)
     */
    // 變量
    protected List E;// 容器：存放圖中所有邊
    protected List V;// 容器：存放圖中所有頂點(diǎn)
    // 構(gòu)造方法

    public Graph_List() {
        E = new List_DLNode();
        V = new List_DLNode();
    }

    // 取圖的邊表、頂點(diǎn)表
    protected List getE() {
        return E;
    }

    protected List getV() {
        return V;
    }

    // 取圖中頂點(diǎn)、邊的數(shù)目
    public int vNumber() {
        return V.getSize();
    }

    public int eNumber() {
        return E.getSize();
    }

    // 取圖中所有頂點(diǎn)、頂點(diǎn)位置的迭代器
    public Iterator vertices() {
        return V.elements();
    }

    public Iterator vPositions() {
        return V.positions();
    }

    // 返回圖中所有邊、邊位置的迭代器
    public Iterator edges() {
        return E.elements();
    }

    public Iterator ePositions() {
        return E.positions();
    }

    // 檢測(cè)是否有某條邊從頂點(diǎn)u指向v
    public boolean areAdjacent(Vertex u, Vertex v) {
        return (null != edgeFromTo(u, v));
    }

    // 取從頂點(diǎn)u指向v的邊，若不存在，則返回null
    public Edge edgeFromTo(Vertex u, Vertex v) {
        for (Iterator it = u.outEdges(); it.hasNext();) {// 逐一檢查
            Edge e = (Edge) it.getNext();// 以u(píng)為尾的每一條邊e
            if (v == e.getVPosInV(1).getElem())// 若e是(u, v)，則
                return e;// 返回該邊
        }
        return null;// 若不存在這樣的(u, v)，則返回null
    }

    // 將頂點(diǎn)v從頂點(diǎn)集中刪除，并返回之
    public Vertex remove(Vertex v) {
        while (0 < v.outDeg())// 將以v為尾的所有邊
            remove((Edge) (((Vertex_List) v).outEdges.first()).getElem());// 逐一刪除
        while (0 < v.inDeg())// 將以v為頭的所有邊
            remove((Edge) (((Vertex_List) v).inEdges.first()).getElem());// 逐一刪除
        return (Vertex) V.remove(v.getVPosInV());// 在頂點(diǎn)表中刪除v
    }

    // 將邊e從邊集中刪除，并返回之
    public Edge remove(Edge e) {
        ((Vertex_List) e.getVPosInV(0).getElem()).outEdges.remove(e.getEPosInI(0));// 從起點(diǎn)的出邊表中刪除e
        ((Vertex_List) e.getVPosInV(1).getElem()).inEdges.remove(e.getEPosInI(1));// 從終點(diǎn)的入邊表中刪除e
        return (Edge) E.remove(e.getEPosInE());// 從邊表中刪除e
    }

    // 在頂點(diǎn)集V中插入新頂點(diǎn)v，并返回其位置
    public Position insert(Vertex v) {
        return V.insertLast(v);
    }

    // 在邊集E中插入新邊e，并返回其位置
    public Position insert(Edge e) {
        return E.insertLast(e);
    }
}

這里主要涉及三個(gè)算法，具體分析如下：

• 判斷任意一對(duì)頂點(diǎn)是否相鄰

算法：areAdjacent(u, v)
輸入：一對(duì)頂點(diǎn)u和v
輸出：判斷是否有某條邊從頂點(diǎn)u指向v
{
取頂點(diǎn)u的出邊迭代器it;
通過(guò)it逐一檢查u的每一條出邊e;
一旦e的終點(diǎn)為v，則報(bào)告true;
若e的所有出邊都已檢查過(guò)，則返回false;
}

• 刪除邊

算法：RemoveEdge(e)
輸入：邊e = (u, v)
輸出：將邊e從邊集E中刪除
{
從起點(diǎn)u的出邊鄰接表中刪除e;
從終點(diǎn)v的入邊鄰接表中刪除e;
從邊表E中刪除e;
}

• 刪除頂點(diǎn)

算法：removeVertex(v)
輸入：頂點(diǎn)v
輸出：將頂點(diǎn)v從頂點(diǎn)集V中刪除
{
掃描v的出邊鄰接表，（調(diào)用removeEdge()算法）將所有邊逐一刪除;
掃描v的入邊鄰接表，（調(diào)用removeEdge()算法）將所有邊逐一刪除;
在頂點(diǎn)表V中刪除v;
}