图的基本概念

图的定义与基本术语

图是描述对象之间的关系的数据结构，由节点或顶点(Vertex）以及连接这些顶点的边（Edge）组成。顶点是实际对象的抽象，边是对象之间关系的抽象。可以将图形式化的表示成二元组：$G=(V,E)$。$V$ 是顶点集，$E$ 是边集。

注意：图的顶点集合不能为空，而边集合可以为空。

图的分类：图可以分为有向图和无向图以及混合图。

• 有向图：图中的边（无向边简称边）在连接顶点时需要区分方向。
• 无向图：图中的边（有向边或弧）在连接顶点时不需要区分方向。

完全图：

• 无向完全图：在无向图中，如果任意两个顶点之间都存在边，则该无向图称为无向完全图。$n$ 个顶点的无向完全图一共有 $\frac{n\ast (n-1)}{2}$ 条边。
• 有向完全图：在有向图中，若任意两个顶点 $x$ 、$y$ 即存在 $x$ 到 $y$ 的弧，也存在 $y$ 到 $x$ 的弧，则该有向图称为有向完全图。$n$ 个顶点的有向完全图一共有 $n\ast (n-1)$ 条弧。

稀疏图和稠密图

• 稠密图：边数接近完全图
• 稀疏图：边数远小于完全图

顶点的度：与顶点相关联的边的数目（无向图）或者是弧的数目（有向图）称为该顶点的度。

特别注意的是有向图中的度：出度和入度之和。

• 出度：以该顶点为起点向外连的边的数目
• 入度：指向该顶点的边的数目

权值：顶点或者边上带有权值

路径：在图中，由顶点 $u$ 到顶点 $v$ 的序列，称为路径。路径上边或者弧的数目称为路径长度。

简单路径：路径中包括重复顶点。

环（回路）：一条路径的起点和终点是一个点

自环：一条边的起点和终点都是一个点。

重边（平行边）：两个顶点之间存在多条边相连接。

图的连通性：在图论中，连通图基于连通的概念。在一个无向图 $G$ 中，若从顶点 $i$ 到顶点 $j$ 有路径相连（当然从 j 到 i 也一定有路径），则称 $i$ 和 $j$ 是连通的。如果 $G$ 是有向图，那么连接 $i$ 和 $j$ 的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。图的连通性是图的基本性质。

子图与连通分量：图 $G^{\prime }$ 中的边集合和顶点集合都是图 $G$ 的边集合和顶点集合的子集，则图 $G^{\prime }$ 是图 $G$ 的子图。无向图的极大连通子图，称为该图的连通分量。

图论中的握手定理：对于一个有向图，所有顶点的入度之和等于出度之和，并且边数也相等；对于一个有向图或者无向图，所有顶点的度数之和等于边数的两倍。

邻接矩阵存图

定义二维数组 $G$ 其中 $G[i][j]$ 表示顶点 $i$ 到顶点 $j$ 边（或弧）上的权值（带权图），使用 $0$ 或是 $\mathrm{\infty }$ 表示不存在边。注意：如果是无权图则可以使用 $1$ 表示有边。

无权图存储示例：

以无权图为例展示图的操作：

const int N = 1e3 + 10; // 最大顶点数
int g[N][N]; // 图
int st[N]; // 访问标记
int n, m; // n 图的顶点数目 m 图的边数

// 读入图
void read() {
    int a, b; // a -> b 的一条边
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        g[a][b] = g[b][a] = 1;
    }
}

// 输出图
void print() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j && g[i][j]) {
                cout << i << " -> " << j << endl;
            }
        }
    }
}

// 深度优先遍历
void dfs(int u) { // 从顶点 u 开始遍历该图
    cout << u << " ";
    st[u] = 1;
   
    for (int i = 1; i <= n; i++) {
        if (g[u][i] && !st[i]) {
            dfs(i);
        }
    }
}

// 广度优先遍历
void bfs(int u) { // 从节点 u 开始遍历该图
    queue<int> q;
    q.push(u);
    st[u] = 1;
   
    while (!q.empty()) {
        int h = q.front();
        q.pop();
        cout << h << " ";
        for (int i = 1; i <= n; i++) {
            if (g[h][i] && !st[i]) {
                q.push(i);
                st[i] = 1;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    read();
    print();
   
    dfs(1);
    memset(st, 0, sizeof st);
    cout << endl;
    bfs(1);

    return 0;
}

/*
一个示例图：
9 8
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
*/

邻接矩阵适用于存储稠密图，如果是稀疏图的话则会浪费空间。为了尽量节省空间，这时我们可以使用 vector。

以无权图为例展示 vector 存图：

const int N = 1e5 + 10;
vector<vector<int>> g(N);
int n, m; // 图的顶点数目和边数目
// 如果想存储边权可以这样做
// vector<vector<pair<int, int>> g(N);

// 读入图
void read() {
    int a, b;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        g[a].push_back(b); // 顶点 a 和顶点 g[a][j] 有一条边
        g[b].push_back(a);
    }
}

// 输出图
void print() {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < g[i].size(); j++) {
            cout << i << " -> " << g[i][j] << endl;
        }
    }
}

邻接表存图

如果我们把 vector 存储图的方式稍加改进，不仅能够极大的节省空间，而且使用起来也更加方便，更加符合人的直觉，这就是邻接表。

无权图的邻接表存储示例：

以无权图为例展示邻接表存储图的操作：

const int N = 1e5 + 10, M = 2 * N; // 最大顶点数 最大边数
// 使用数组模拟链表
int h[N], e[M], ne[M], idx;
int st[N];
int n, m;
int q[N]; // 广度优先遍历使用数组模拟队列

// 初始化链表
void init() {
    memset(h, -1, sizeof h);
    idx = 0;
}

// 头插法 插入一条 a -> b 的边
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

// 读入图
void read() {
    int a, b;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
}

// 输出图
void print() {
    for (int i = 1; i <= n; i++) {
        for (int j = h[i]; j != -1; j = ne[j]) {
            cout << i << " -> " << e[j] << endl;
        }
    }
}

// 深度优先遍历
void dfs(int u) { // 从顶点 u 开始遍历该图
    cout << u << " ";
    st[u] = 1;
   
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            dfs(j);
        }
    }
}

// 广度优先遍历
void bfs(int u) { // 从节点 u 开始遍历该图
    int hh = 0, tt = -1;
    q[++tt] = u;
    st[u] = 1;
   
    while (hh <= tt) {
        int t = q[hh++];
        cout << t << " ";
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                q[++tt] = j;
                st[j] = 1;
            }
        }
    }
}



int main() {
    init();
   
    cin >> n >> m;
    read();
    print();
   
    dfs(1);
    memset(st, 0, sizeof st);
    cout << endl;
    bfs(1);

    return 0;
}

/*
9 8
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
*/