『普及』浅谈图的基础

· · 算法·理论

基础知识

图是一种网状数据结构，用于描述对象的集合以及对象之间的关系。其中，对象用顶点表示，也称为节点，简称点。对象之间的关系用连接顶点的边表示。若图中的每条边是单向的，则该图称为有向图；若图中的每条边是双向的，则该图称为无向图；若图中的每条边有权重，则该图称为加权图。研究图的数学分支被称为图论，这个我们以后会深入讲解。

图的表示

邻接矩阵

用一个二维数组标记两个节点是否相邻，G_{i, j} 表示节点 i 能否到达节点 j。若该图为加权图，则 G_{i, j} 标记节点 i 与节点 j 之间的边权，如果没有边的话通常设置其为无穷大或 -1。

实现方式

int G[3500][3500];//声明部分
int n, m;//点数与边数
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i)
    {
        int u, v, w;
        cin >> u >> v;//不加权
        //cin >> w;//加权
        G[u][v] = true;//有向图
        //G[v][u] = true;//无向图
        //G[u][v] = w;//有向加权图
        //G[v][u] = w;//无向加权图
    }
    return 0;
}

邻接表

用邻接表更节省空间。其中 G_i 存储节点 i 能直接到达的节点。

实现方式

不加权图

vector<int> G[3500];//声明部分
int n, m;//点数与边数
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i)
    {
        int u, v;
        cin >> u >> v;//不加权
        G[u].push_back(v)//有向图
        //G[v].push_back(u)//无向图
    }
    return 0;
}

加权图

struct Node{
    int v, w;
};
vector<Node> G[3500];//声明部分
int n, m;//点数与边数
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i)
    {
        int u, v, w;
        cin >> u >> v;
        cin >> w;//加权
        G[u].push_back({v, w})//有向图
        //G[v].push_back({u, w})//无向图
    }
    return 0;
}

其实还有一种叫链式前向星的表示方式，后面会讲到。

连通图的遍历

深度优先遍历

选择一个顶点为起点（通常为 1 号节点），并递归遍历其所有的邻接节点。为了防止一个节点被重复访问，我们需要一个 vis 数组来标记一个节点有没有被访问过。

实现方式

void dfs(int u)
{
    cout << u << " ";
    vis[u] = true;
    for (auto v : G[u])
    {
        if (vis[v] == true)
        {
            continue;
        }
        dfs(v);
    }
}

广度优先遍历

选择一个顶点为起点，再按照与起点的距离从小到大进行遍历，与广度优先搜索类似。

实现方式

void bfs(int s)
{
    queue<pair<int,int> > q;
    vis[s] = true;
    q.push({s, 0});
    while (!q.empty())
    {
        pair<int,int> t = q.front();
        q.pop();
        dis[t.first] = t.second;
        for(auto v:G[t.first])
        {
            if (vis[v] == true)
            {
                continue;
            }
            vis[v] = true;
            cout << v << " ";
        }
    }
}

习题

基础

P5318 【深基18.例3】查找文献

P3916 图的遍历

P1113 杂务

拓展

P1807 最长路

P1363 幻象迷宫