鄰接矩陣有向圖 C語言完整實現：創建、遍歷與核心操作

鄰接矩陣表示法

有向圖 G=(V,E)，頂點集 V，邊集 E。鄰接矩陣 A[|V|][|V|]：

• A[i][j] = 1 表示存在邊 vi → vj
• A[i][j] = 0 表示無邊
• 空間複雜度 O(|V|²)，適合稠密圖；查邊 O(1)。

圖結構定義

#define MAX 100

typedef struct Graph {
    char vexs[MAX];           // 頂點標籤
    int vexnum;               // 頂點數
    int edgnum;               // 邊數
    int matrix[MAX][MAX];     // 鄰接矩陣
} Graph, *PGraph;

輔助函數：頂點下標查找

int get_position(Graph g, char ch) {
    for (int i = 0; i < g.vexnum; i++)
        if (g.vexs[i] == ch) return i;
    return -1;
}

創建圖：已知數據版

Graph* create_example_graph(void) {
    char vexs[] = {'A','B','C','D','E','F','G'};
    char edges[][2] = {
        {'A','B'}, {'B','C'}, {'B','E'}, {'B','F'},
        {'C','E'}, {'D','C'}, {'E','B'}, {'E','D'}, {'F','G'}
    };
    int vlen = sizeof(vexs)/sizeof(vexs[0]);
    int elen = sizeof(edges)/sizeof(edges[0]);

    Graph *g = calloc(1, sizeof(Graph));
    g->vexnum = vlen; g->edgnum = elen;
    memcpy(g->vexs, vexs, vlen);

    for (int i = 0; i < elen; i++) {
        int u = get_position(*g, edges[i][0]);
        int v = get_position(*g, edges[i][1]);
        g->matrix[u][v] = 1;
    }
    return g;
}

創建圖：交互輸出版

Graph* create_graph_interactive(void) {
    int v, e;
    printf("頂點數: "); scanf("%d", &v);
    printf("邊數: ");   scanf("%d", &e);
    if (v < 1 || e < 1 || e > v*(v-1)) return NULL;

    Graph *g = calloc(1, sizeof(Graph));
    g->vexnum = v; g->edgnum = e;

    for (int i = 0; i < v; i++) {
        printf("頂點 %d: ", i);
        g->vexs[i] = getchar(); // 需處理換行
    }

    for (int i = 0; i < e; i++) {
        char c1, c2;
        printf("邊 %d (起點 終點): ", i);
        scanf(" %c %c", &c1, &c2);
        int u = get_position(*g, c1);
        int v = get_position(*g, c2);
        if (u==-1 || v==-1) { free(g); return NULL; }
        g->matrix[u][v] = 1;
    }
    return g;
}

深度優先搜索 (DFS)

void dfs(Graph *g, int v, int visited[]) {
    visited[v] = 1;
    printf("%c ", g->vexs[v]);
    for (int i = 0; i < g->vexnum; i++)
        if (g->matrix[v][i] && !visited[i])
            dfs(g, i, visited);
}

void dfs_traverse(Graph *g) {
    int visited[MAX] = {0};
    for (int i = 0; i < g->vexnum; i++)
        if (!visited[i]) dfs(g, i, visited);
    putchar('\n');
}

廣度優先搜索 (BFS)

void bfs_traverse(Graph *g) {
    int visited[MAX] = {0};
    int queue[MAX], front = 0, rear = 0;

    for (int i = 0; i < g->vexnum; i++) {
        if (visited[i]) continue;
        visited[i] = 1;
        queue[rear++] = i;
        while (front < rear) {
            int v = queue[front++];
            printf("%c ", g->vexs[v]);
            for (int j = 0; j < g->vexnum; j++)
                if (g->matrix[v][j] && !visited[j]) {
                    visited[j] = 1;
                    queue[rear++] = j;
                }
        }
    }
    putchar('\n');
}

打印鄰接矩陣

void print_matrix(Graph *g) {
    printf("  ");
    for (int i = 0; i < g->vexnum; i++) printf("%c ", g->vexs[i]);
    putchar('\n');
    for (int i = 0; i < g->vexnum; i++) {
        printf("%c ", g->vexs[i]);
        for (int j = 0; j < g->vexnum; j++)
            printf("%d ", g->matrix[i][j]);
        putchar('\n');
    }
}

主程序測試

int main(void) {
    Graph *g = create_example_graph();
    print_matrix(g);
    printf("DFS: "); dfs_traverse(g);
    printf("BFS: "); bfs_traverse(g);
    free(g);
    return 0;
}

輸出示例

  A B C D E F G
A 0 1 0 0 0 0 0
B 0 0 1 0 1 1 0
C 0 0 0 0 1 0 0
D 0 0 1 0 0 0 0
E 0 1 0 1 0 0 0
F 0 0 0 0 0 0 1
G 0 0 0 0 0 0 0
DFS: A B C E D F G
BFS: A B C E F D G