JSON 文件在線打開指南
圖可以分為有向圖和無向圖。在有向圖中，邊是有方向的，表示從一個頂點指向另一個頂點；而在無向圖中，邊則沒有方向。
圖的分類包括簡單圖、多重圖、完全圖和子圖等。簡單圖是指沒有重邊和自環的圖，多重圖則允許重邊。完全圖是指任意兩個不同頂點之間都有邊相連的圖。而子圖是原圖的一個部分，包括一些頂點和邊。
在圖中，每個頂點的度是與其相連的邊的數目。對于有向圖，度分為入度和出度，分別表示以該頂點為終點和起點的有向邊的數目。
圖的存儲結構有多種選擇，常見的有鄰接矩陣、鄰接表、十字鏈表、鄰接多重表和邊集數組。
鄰接矩陣是一種簡單易理解的圖存儲方式。它使用一個二維數組來表示頂點之間的連接關系。對于一個有 n 個頂點的圖，鄰接矩陣是一個 n × n 的二維數組。若頂點 vi 和 vj 之間有邊，則 A[i][j] = 1，否則為 0。
這種方法適合稠密圖，但對于稀疏圖則會浪費大量空間。
鄰接表是一種更為高效的存儲方式，尤其適用于稀疏圖。它為每個頂點維護一個鏈表，用于存儲其所有相鄰頂點。
這種方式存儲空間小，但查找兩個頂點之間是否有邊連接的時間復雜度較高。
十字鏈表是有向圖的一種存儲方式，將鄰接表和逆鄰接表結合起來，使得在查找入度和出度時都很方便。
鄰接多重表是無向圖的存儲方式，適用于需要頻繁修改邊的圖。它在鄰接表的基礎上，每條邊只存一次，從而簡化了對邊的操作。
邊集數組關注邊的集合，適用于需要頻繁遍歷邊的操作。它由兩個數組構成，一個存儲頂點信息，另一個存儲邊的信息。
圖的遍歷是訪問圖中所有頂點的過程，主要有深度優先遍歷（DFS）和廣度優先遍歷（BFS）。
DFS 類似于樹的先序遍歷，通過遞歸的方式盡可能深入到圖的每個分支。其實現需要輔助遞歸棧。
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);
}
}
}
BFS 類似于樹的層序遍歷，通過隊列實現，逐層訪問頂點。
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);
}
}
}
}
}
}
圖的連通性是指圖中任意兩個頂點是否可達。對于無向圖，若從任一頂點出發能到達所有其他頂點，則為連通圖；對于有向圖，若任意兩個頂點之間都有路徑，則為強連通圖。
選擇圖的存儲結構取決于圖的密度和操作需求。稠密圖適合鄰接矩陣，稀疏圖適合鄰接表。十字鏈表適用于需要頻繁查詢入度和出度的有向圖。
在鄰接矩陣中，直接檢查對應位置的值。在鄰接表中，需要遍歷頂點對應的邊表。
DFS 是沿著一個分支盡可能深地走，適用于路徑查找；BFS 是逐層遍歷，適用于查找最短路徑。
生成樹是一個包含圖中所有頂點的最小連通子圖，對于無回路的連通圖，生成樹的邊數為 n-1（n為頂點數）。
