欧美另类亚洲中文字幕,欧美一区二区三区啪啪

圖可以分為有向圖和無向圖。在有向圖中，邊是有方向的，表示從一個頂點(diǎn)指向另一個頂點(diǎn)；而在無向圖中，邊則沒有方向。

圖的術(shù)語與分類

圖的分類包括簡單圖、多重圖、完全圖和子圖等。簡單圖是指沒有重邊和自環(huán)的圖，多重圖則允許重邊。完全圖是指任意兩個不同頂點(diǎn)之間都有邊相連的圖。而子圖是原圖的一個部分，包括一些頂點(diǎn)和邊。

圖的分類

有向圖與無向圖

有向圖：邊是有序?qū)?，記?(v, w)，表示從頂點(diǎn) v 到頂點(diǎn) w 的連接。
無向圖：邊是無序?qū)?，記?(v, w)，表示頂點(diǎn) v 和頂點(diǎn) w 之間的雙向連接。

頂點(diǎn)的度、入度和出度

在圖中，每個頂點(diǎn)的度是與其相連的邊的數(shù)目。對于有向圖，度分為入度和出度，分別表示以該頂點(diǎn)為終點(diǎn)和起點(diǎn)的有向邊的數(shù)目。

圖的存儲結(jié)構(gòu)

圖的存儲結(jié)構(gòu)有多種選擇，常見的有鄰接矩陣、鄰接表、十字鏈表、鄰接多重表和邊集數(shù)組。

鄰接矩陣

鄰接矩陣是一種簡單易理解的圖存儲方式。它使用一個二維數(shù)組來表示頂點(diǎn)之間的連接關(guān)系。對于一個有 n 個頂點(diǎn)的圖，鄰接矩陣是一個 n × n 的二維數(shù)組。若頂點(diǎn) vi 和 vj 之間有邊，則 A[i][j] = 1，否則為 0。

鄰接矩陣示例

這種方法適合稠密圖，但對于稀疏圖則會浪費(fèi)大量空間。

鄰接表

鄰接表是一種更為高效的存儲方式，尤其適用于稀疏圖。它為每個頂點(diǎn)維護(hù)一個鏈表，用于存儲其所有相鄰頂點(diǎn)。

鄰接表示例

這種方式存儲空間小，但查找兩個頂點(diǎn)之間是否有邊連接的時(shí)間復(fù)雜度較高。

十字鏈表

十字鏈表是有向圖的一種存儲方式，將鄰接表和逆鄰接表結(jié)合起來，使得在查找入度和出度時(shí)都很方便。

十字鏈表示例

鄰接多重表

鄰接多重表是無向圖的存儲方式，適用于需要頻繁修改邊的圖。它在鄰接表的基礎(chǔ)上，每條邊只存一次，從而簡化了對邊的操作。

鄰接多重表示例

邊集數(shù)組

邊集數(shù)組關(guān)注邊的集合，適用于需要頻繁遍歷邊的操作。它由兩個數(shù)組構(gòu)成，一個存儲頂點(diǎn)信息，另一個存儲邊的信息。

邊集數(shù)組示例

圖的遍歷

圖的遍歷是訪問圖中所有頂點(diǎn)的過程，主要有深度優(yōu)先遍歷（DFS）和廣度優(yōu)先遍歷（BFS）。

深度優(yōu)先遍歷（DFS）

DFS 類似于樹的先序遍歷，通過遞歸的方式盡可能深入到圖的每個分支。其實(shí)現(xiàn)需要輔助遞歸棧。

void DFS(Graph G, int v) {
    visit(v);
    visited[v] = TRUE;
    for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
        if (!visited[w]) {
            DFS(G, w);
        }
    }
}

DFS示例

廣度優(yōu)先遍歷（BFS）

BFS 類似于樹的層序遍歷，通過隊(duì)列實(shí)現(xiàn)，逐層訪問頂點(diǎn)。

void BFSTraverse(MGraph G) {
    Queue Q;
    InitQueue(&Q);
    for (i = 0; i = 0; j = NextNeighbor(G, i, j)) {
                    if (!visited[j]) {
                        visited[j] = TRUE;
                        EnQueue(&Q, j);
                    }
                }
            }
        }
    }
}

BFS示例