データ構造 - グラフ
グラフ(Graph)は、より汎用的な非線形データ構造であり、要素間の「多対多」の複雑な関係を表すために使用され、頂点と頂点を接続する辺から構成される。
グラフの基本概念
图类型グラフの種類 — 無向グラフ、有向グラフ、重み付きグラフ
无向图
0
—1
辺に方向はなく、接続は対等です
例:社交网络好友关系
例:社交网络好友关系
有向图
0
→1
边有方向,单向连接
例:关注关系、网页链接
例:关注关系、网页链接
带权图
0
51
边附带权重(距离/代价)
例:地图导航、网络延迟
例:地图导航、网络延迟
グラフの格納方法
ストレージ方式の比較隣接行列 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;
}
#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、コミュニティ発見 |