データ構造 - グラフ

グラフ(Graph)は、より汎用的な非線形データ構造であり、要素間の「多対多」の複雑な関係を表すために使用され、頂点と頂点を接続する辺から構成される。


グラフの基本概念

图类型

グラフの種類 — 無向グラフ、有向グラフ、重み付きグラフ

无向图

0
—
1
辺に方向はなく、接続は対等です
例:社交网络好友关系

有向图

0
→
1
边有方向,单向连接
例:关注关系、网页链接

带权图

0
5
1
边附带权重(距离/代价)
例:地图导航、网络延迟

グラフの格納方法

ストレージ方式の比較

隣接行列 vs 隣接リスト

邻接矩阵

空间复杂度O(V²)
判断两点相连O(1)
遍历邻接点O(V)
适合:稠密图 · int graph[V][V]

邻接表

空间复杂度O(V+E)
判断两点相连O(度数)
遍历邻接点O(度数)
适合:稀疏图 · 链表数组

グラフの走査

DFS vs BFS — 頂点0から走査

DFS 深さ優先

0→ 1→ 3→ 4→ 2→ 5
沿一条路径走到头再回溯
实现:递归 / 栈 | 适合路径搜索、拓扑排序

BFS 幅優先

0→ 1→ 2→ 3→ 4→ 5
按层扩展,同层先访问
实现:队列 | 天然适合无权图最短路径

实例

#include <stdio.h>
#include <stdbool.h>

#define V 6 /* 顶点数 */

/* 隣接行列で表されるグラフ */
int graph[V][V] = {
    {0,1,1,0,0,0},  /* 頂点 0 の隣接関係 */
    {1,0,0,1,1,0},  /* 顶点 1 */
    {1,0,0,0,1,0},  /* 顶点 2 */
    {0,1,0,0,0,1},  /* 顶点 3 */
    {0,1,1,0,0,1},  /* 顶点 4 */
    {0,0,0,1,1,0}   /* 顶点 5 */
};
bool visited[V];

/* DFS: 深度优先搜索,递归实现
特徴:1つの経路を最後まで辿ってからバックトラックする。経路探索と連結性の判定に適している */

void DFS(int v) {
    visited[v] = true;
    printf("%d ", v);         /* 访问当前顶点 */
    for (int i = 0; i < V; i++) {
        if (graph[v][i] && !visited[i]) {
            DFS(i);  /* 未訪問の隣接頂点を再帰のに訪問する */
        }
    }
}

/* BFS: 广度优先搜索,借助队列实现
特点:按层扩展,天然适合求解最短路径 */

void BFS(int start) {
    bool visited[V] = {false};
    int queue[V];
    int front = 0, rear = 0;

    visited[start] = true;
    queue[rear++] = start;  /* 起始顶点入队 */

    while (front < rear) {
        int v = queue[front++];  /* 出队 */
        printf("%d ", v);

        for (int i = 0; i < V; i++) {
            if (graph[v][i] && !visited[i]) {
                visited[i] = true;
                queue[rear++] = i;  /* 邻接顶点入队 */
            }
        }
    }
}

int main() {
    /* 初始化访问标记 */
    for (int i = 0; i < V; i++) visited[i] = false;

    printf("DFS (頂点 0 から開始): ");
    DFS(0);  /* 输出: 0 1 3 5 4 2 */
    printf("\n");

    printf("BFS (頂点 0 から開始): ");
    BFS(0);  /* 输出: 0 1 2 3 4 5 */
    printf("\n");
    return 0;
}

グラフの応用シーン

场景典型算法
最短路径Dijkstra、Bellman-Ford(地图导航)
最小生成树Prim、Kruskal(ネットワーク配線の最適化)
拓扑排序Kahn アルゴリズム(タスク依存関係分析)
社交网络分析PageRank、コミュニティ発見
其他扩展