408答疑

---

---

五、圖的代碼實操

圖的存儲

鄰接矩陣

結構定義

typedef struct GraphMtx {int numV; // 頂點個數int numE; // 邊的條數ElemType vList[MAX_VERTEX_SIZE]; // 頂點空間int edge[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE]; // 邊的矩陣
} GraphMtx;

初始化

• 初始化圖的頂點數和邊數為 0，并將鄰接矩陣的所有元素設置為 0。

void initGraph(GraphMtx *g) {g->numV = 0;g->numE = 0;for (int i = 0; i < MAX_VERTEX_SIZE; ++i) {for (int j = 0; j < MAX_VERTEX_SIZE; ++j)g->edge[i][j] = 0;}
}

插入頂點

• 在圖中插入一個新頂點，如果頂點數超過最大值則不插入。

void insertVertex(GraphMtx *g, ElemType vertex) {if (g->numV >= MAX_VERTEX_SIZE)return;g->vList[g->numV] = vertex;g->numV++;
}

獲取頂點位置

• 返回頂點在頂點列表中的位置，如果不存在則返回 -1。

int getPosVertex(GraphMtx *g, ElemType vertex) {for (int i = 0; i < g->numV; ++i) {if (g->vList[i] == vertex)return i;}return -1; // 沒有要查找的頂點
}

在頂點 v1 和 v2 之間插入邊

• 在圖中插入一條從頂點 vertex1 到頂點 vertex2 的邊。

void insertEdge(GraphMtx *g, ElemType vertex1, ElemType vertex2) {int v1 = getPosVertex(g, vertex1);int v2 = getPosVertex(g, vertex2);// 插入v1->v2邊g->edge[v1][v2] = 1;// 若是無向圖，則插入v2->v1邊//g->edge[v2][v1] = 1;g->numE++;
}

獲取第一個鄰接頂點

• 獲取給定頂點的第一個鄰接頂點。

int getFirstNeighbor(GraphMtx *g, ElemType vertex) {int v = getPosVertex(g, vertex);if (v == -1)return -1; // 沒有鄰接頂點for (int j = 0; j < g->numV; ++j) {if (g->edge[v][j] == 1)return j; // 返回鄰接頂點}return -1; // 沒有鄰接頂點
}

獲取下一個鄰接頂點

• 獲取給定頂點的下一個鄰接頂點。

int getNextNeighbor(GraphMtx *g, ElemType vertex1, ElemType vertex2) {int v1 = getPosVertex(g, vertex1);int v2 = getPosVertex(g, vertex2);if (v1 == -1 || v2 == -1)return -1;for (int j = v2 + 1; j < g->numV; ++j) {if (g->edge[v1][j] == 1)return j;}return -1;
}

顯示圖

• 顯示圖的鄰接矩陣。

void showGraph(GraphMtx *g) {printf(" ");for (int i = 0; i < g->numV; ++i)printf(" %c", g->vList[i]);printf("\n");for (int i = 0; i < g->numV; ++i) {printf("%c ", g->vList[i]);for (int j = 0; j < g->numV; ++j) {printf("%d ", g->edge[i][j]);}printf("\n");}
}

鄰接表

結構定義

typedef struct Edge {int dest; // 目標頂點的下標struct Edge *next; // 結點指針
} Edge;typedef struct Vertex {ElemType data;   // 頂點數據Edge *first; // 指向邊的起始指針
} Vertex;typedef struct GraphLnk {int numV; // 頂點數int numE; // 邊的條數Vertex nodeTable[MAX_VERTEX_SIZE];
} GraphLnk;

初始化圖

• 初始化圖的頂點數和邊數為 0，并將鄰接表的所有元素設置為 NULL。

void initGraph(GraphLnk *g) {g->numV = 0;g->numE = 0;for (int i = 0; i < MAX_VERTEX_SIZE; ++i)g->nodeTable[i].first = NULL;
}

插入頂點

• 在圖中插入一個新頂點，如果頂點數超過最大值則不插入。

void insertVertex(GraphLnk *g, ElemType vertex) {if (g->numV >= MAX_VERTEX_SIZE)return;g->nodeTable[g->numV].data = vertex;g->numV++;
}

獲取頂點位置

• 返回頂點在頂點列表中的位置，如果不存在則返回 -1。

int getPosVertex(GraphLnk *g, ElemType vertex) {for (int i = 0; i < g->numV; ++i) {if (g->nodeTable[i].data == vertex)return i;}return -1; // 沒有要查找的頂點
}

在頂點 v1 和 v2 之間插入邊

• 在圖中插入一條從頂點 vertex1 到頂點 vertex2 的邊。

void insertEdge(GraphLnk *g, ElemType vertex1, ElemType vertex2) {int v1 = getPosVertex(g, vertex1);int v2 = getPosVertex(g, vertex2);// v1->v2Edge *e = (Edge*)malloc(sizeof(Edge));e->dest = v2;e->next = g->nodeTable[v1].first;g->nodeTable[v1].first = e;// 	若是無向圖，則插入v2->v1邊//e = (Edge*)malloc(sizeof(Edge));//e->dest = v1;//e->next = g->nodeTable[v2].first;//g->nodeTable[v2].first = e;g->numE++;
}

獲取第一個鄰接頂點

• 獲取給定頂點的第一個鄰接頂點。

int getFirstNeighbor(GraphLnk *g, ElemType vertex) {int v = getPosVertex(g, vertex);if (v == -1)return -1; // 沒有鄰接頂點if (g->nodeTable[v].first != NULL)return g->nodeTable[v].first->dest;return -1; // 沒有鄰接頂點
}

獲取下一個鄰接頂點

• 獲取給定頂點的下一個鄰接頂點。

int getNextNeighbor(GraphLnk *g, ElemType vertex1, ElemType vertex2) {int v1 = getPosVertex(g, vertex1);int v2 = getPosVertex(g, vertex2);if (v1 == -1 || v2 == -1)return -1;Edge *p = g->nodeTable[v1].first;while (p->dest != v2)p = p->next;p = p->next;if (p != NULL)return p->dest;return -1;
}

顯示圖

• 顯示圖的鄰接表。

void showGraph(GraphLnk *g) {for (int i = 0; i < g->numV; ++i) {printf("%d %c : ", i, g->nodeTable[i].data);Edge *p = g->nodeTable[i].first;while (p != NULL) {printf("%d->", p->dest);p = p->next;}printf("Nil.\n");}
}

圖的遍歷

深度優先遍歷

算法思想

深度優先遍歷（DFS）是一種用于遍歷或搜索圖或樹的算法。該算法使用棧（顯式或遞歸）來實現非遞歸約的遍歷過程。算法從圖中的某一頂點開始，沿著路徑深入訪問盡可能遠的頂點，直到不能再深入為止，然后回溯并訪問其他路徑。

算法步驟

1. 訪問起始頂點：選擇圖中的某一頂點作為起始點，并標記為已訪問。
2. 訪問鄰接頂點：訪問該頂點的所有未被訪問的鄰接頂點，對每個鄰接頂點遞歸地調用DFS。
3. 回溯：當當前路徑無法繼續深入時，回溯到最近的已訪問頂點，檢查是否有其他未訪問的鄰接頂點。
4. 重復過程：重復上述過程，直到圖中所有頂點都被訪問。

算法特點

• DFS 相當于二叉樹中的前序遍歷。
• 使用臨時空間來標記結點是否被訪問過。
• 適用于圖的連通性檢測、拓撲排序等場景。

鄰接矩陣

void DFS(GraphMtx *g, ElemType vertex) {printf("%c->", vertex);int v = getPosVertex(g, vertex);visit[v] = 1; // 標記頂點int w = getFirstNeighbor(g, vertex);while (w != -1) {if (!visit[w]) {DFS(g, g->vList[w]);}w = getNextNeighbor(g, g->vList[v], g->vList[w]); //(g, v1, v2)}
}

鄰接表

void DFS(GraphLnk *g, ElemType vertex) {printf("%c->", vertex);int v = getPosVertex(g, vertex);visit[v] = 1; // 標記頂點int w = getFirstNeighbor(g, vertex);while (w != -1) {if (!visit[w]) {DFS(g, g->nodeTable[w].data);}w = getNextNeighbor(g, g->nodeTable[v].data, g->nodeTable[w].data); //(g, v1, v2)}
}

廣度優先遍歷

算法思想

1. 初始化：

   • 標記起始頂點為已訪問。
   • 將起始頂點入隊。

2. 遍歷隊列：當隊列不為空時，執行以下操作。

   • 從隊列中取出一個頂點。
   • 訪問該頂點的所有未訪問過的鄰接頂點。
   • 將這些鄰接頂點標記為已訪問，并加入隊列。

3. 重復步驟2，直到隊列為空，即所有可達頂點都被訪問。

鄰接矩陣

void BFS(GraphMtx *g, ElemType vertex) {printf("%c->", vertex);int v = getPosVertex(g, vertex);visit[v] = 1;int Q[MAX_VERTEX_SIZE];int front = 0, rear = 0;// 入隊Q[rear++] = v;while (front != rear) { // 隊列不空v = Q[front++]; // 出隊并保存頂點int w = getFirstNeighbor(g, g->vList[v]);while (w != -1) {if (!visit[w]) {printf("%c->", g->vList[w]);visit[w] = 1;Q[rear++] = w;}w = getNextNeighbor(g, g->vList[v], g->vList[w]);}}
}

鄰接表

void BFS(GraphLnk *g, ElemType vertex) {printf("%c->", vertex);int v = getPosVertex(g, vertex);visit[v] = 1;int Q[MAX_VERTEX_SIZE];int front = 0, rear = 0;// 入隊Q[rear++] = v;while (front != rear) { // 隊列不空v = Q[front++]; // 出隊并保存頂點int w = getFirstNeighbor(g, g->nodeTable[v].data);while (w != -1) {if (!visit[w]) {printf("%c->", g->nodeTable[w].data);visit[w] = 1;Q[rear++] = w;}w = getNextNeighbor(g, g->nodeTable[v].data, g->nodeTable[w].data);}}
}

圖的應用

BFS算法求解單源最短路徑問題

1. 初始化：

   • 設置所有頂點的最短路徑長度為無窮大，起始頂點的距離為0。
   • 標記起始頂點為已訪問。
   • 將起始頂點加入隊列。

2. BFS遍歷：當隊列非空時，執行以下操作。

   • 從隊列中取出一個頂點。
   • 遍歷該頂點的所有未訪問鄰接頂點。
   • 更新鄰接頂點的最短路徑長度。
   • 標記鄰接頂點為已訪問。
   • 將鄰接頂點加入隊列。

3. 完成遍歷：

   • 重復步驟2，直到隊列為空。
   • 此時，數組d中存儲的即為從起始頂點到所有可達頂點的最短路徑長度。

void BFS_MIN_Distance(GraphMtx G, int u) {// d[i]表示從u到i結點的最短路徑長度int d[MAX_VERTEX_SIZE]; int visited[MAX_VERTEX_SIZE]; // 訪問標記數組Queue Q; // 定義隊列Qfor (int i = 0; i < G.numV; ++i) {d[i] = ∞; // 初始化路徑長度為無窮大visited[i] = FALSE; // 初始化所有頂點為未訪問}d[u] = 0; // 起始頂點到自身的距離為0visited[u] = TRUE; // 標記起始頂點為已訪問EnQueue(Q, u); // 將起始頂點入隊while (!IsEmpty(Q)) { // BFS算法主過程int v;DeQueue(Q, v); // 隊頭元素v出隊for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {if (!visited[w]) { // w為v的尚未訪問的鄰接頂點visited[w] = TRUE; // 標記為已訪問d[w] = d[v] + G.edge[v][w]; // 路徑長度加v到w的邊的權重EnQueue(Q, w); // 頂點w入隊}}}
}

拓撲排序

• 使用棧實現圖的拓撲排序，輸出頂點的拓撲序列。

void topSort(GraphMtx *g) {// 統計每一個頂點的入度for (int j = 0; j < g->numV; ++j) {for (int i = 0; i < g->numV; ++i) {if (g->edge[i][j] == 1)inDegree[j]++;}}// 定義一個棧ElemType stack[MAX_VERTEX_SIZE] = { 0 };int top = 0;// 把入度為0的頂點入棧for (int i = 0; i < g->numV; ++i) {if (inDegree[i] == 0) // 入度為0stack[top++] = i;}for (int i = 0; i < g->numV; ++i) { // 排序輸出每一個頂點if (top == 0) {printf("圖有回路.\n");return;}int v = stack[--top];printf("%c->", g->vList[v]);int w = getFirstNeighbor(g, g->vList[v]);while (w != -1) {if (--inDegree[w] == 0)stack[top++] = w;w = getNextNeighbor(g, g->vList[v], g->vList[w]);}}
}

六、參考資料

鮑魚科技課件

b站免費王道課后題講解:

網課全程班:

26王道考研書