一步步演算法：圖的建立與基本操作實作（鄰接表版）

編輯：關於C語言

承接上文圖表示法，本文聚焦鄰接表的工程級建立流程：從資料結構定義、節點/邊建立、圖初始化、查找操作到記憶體釋放，提供完整可編譯的 C 語言實作。

資料結構定義（含圖容器）


typedef struct ArcNode {
    int dest;
    int weight;
    struct ArcNode *next;
} ArcNode;

typedef struct VertexNode {
    int id;
    ArcNode *first_arc;
    struct VertexNode *next;  // 頂點鏈表，支援動態增刪頂點
} VertexNode;

typedef struct Graph {
    int vex_count;
    VertexNode *vertices;  // 頂點鏈表頭
} Graph;

核心建立函式

建立頂點節點


VertexNode* create_vertex(int id) {
    VertexNode *v = (VertexNode*)malloc(sizeof(VertexNode));
    if (!v) return NULL;
    v->id = id;
    v->first_arc = NULL;
    v->next = NULL;
    return v;
}

建立邊節點


ArcNode* create_arc(int dest, int weight) {
    ArcNode *a = (ArcNode*)malloc(sizeof(ArcNode));
    if (!a) return NULL;
    a->dest = dest;
    a->weight = weight;
    a->next = NULL;
    return a;
}

建立帶邊的頂點（便利函式）


VertexNode* create_vertex_with_arc(int id, int dest, int weight) {
    VertexNode *v = create_vertex(id);
    if (!v) return NULL;
    v->first_arc = create_arc(dest, weight);
    return v;
}

建立圖容器（含首個頂點與邊）


Graph* create_graph(int start_id, int dest_id, int weight) {
    Graph *g = (Graph*)malloc(sizeof(Graph));
    if (!g) return NULL;
    g->vex_count = 1;
    g->vertices = create_vertex_with_arc(start_id, dest_id, weight);
    return g;
}

查找操作（線性搜尋，工程上可改雜湊表）

在圖中查找頂點


VertexNode* find_vertex(Graph *g, int id) {
    VertexNode *cur = g->vertices;
    while (cur) {
        if (cur->id == id) return cur;
        cur = cur->next;
    }
    return NULL;
}

在頂點鄰接表中查找邊


ArcNode* find_arc(VertexNode *v, int dest_id) {
    ArcNode *cur = v->first_arc;
    while (cur) {
        if (cur->dest == dest_id) return cur;
        cur = cur->next;
    }
    return NULL;
}

動態插入操作

插入頂點


int insert_vertex(Graph *g, int id) {
    if (find_vertex(g, id)) return -1;  // 已存在
    VertexNode *v = create_vertex(id);
    if (!v) return -2;
    v->next = g->vertices;  // 頭插法
    g->vertices = v;
    g->vex_count++;
    return 0;
}

插入邊（無向圖雙向插入）


int insert_edge(Graph *g, int from, int to, int weight) {
    VertexNode *v_from = find_vertex(g, from);
    VertexNode *v_to = find_vertex(g, to);
    if (!v_from || !v_to) return -1;
    
    // from -> to
    ArcNode *a1 = create_arc(to, weight);
    if (!a1) return -2;
    a1->next = v_from->first_arc;
    v_from->first_arc = a1;
    
    // to -> from (無向圖)
    ArcNode *a2 = create_arc(from, weight);
    if (!a2) { /* 需回滾 a1，略 */ return -3; }
    a2->next = v_to->first_arc;
    v_to->first_arc = a2;
    
    return 0;
}

圖的銷毀與記憶體釋放


void destroy_graph(Graph *g) {
    VertexNode *v = g->vertices;
    while (v) {
        ArcNode *a = v->first_arc;
        while (a) {
            ArcNode *tmp = a;
            a = a->next;
            free(tmp);
        }
        VertexNode *tmp_v = v;
        v = v->next;
        free(tmp_v);
    }
    free(g);
}

完整測試主程式


int main() {
    Graph *g = create_graph(1, 2, 10);
    insert_vertex(g, 3);
    insert_edge(g, 2, 3, 5);
    insert_edge(g, 1, 3, 7);
    
    // 驗證
    VertexNode *v1 = find_vertex(g, 1);
    for (ArcNode *a = v1->first_arc; a; a = a->next)
        printf("1 -> %d (w=%d)\n", a->dest, a->weight);
    
    destroy_graph(g);
    return 0;
}