[Note] 存图与遍历

[L4] 存图与遍历

1. 决策矩阵

方式	空间	遍历效率	查边效率 $u \to v$	适用场景
邻接矩阵	$O(N^2)$	$O(N)$	$O(1)$	点数少 ($N \le 500$)，边稠密，需频繁判断连通。
邻接表	$O(M)$	$O(deg(u))$	$O(deg(u))$	大部分情况通用，代码最简洁，常数略大。
链式前向星	$O(M)$	$O(deg(u))$	$O(deg(u))$	常数极小，方便维护反向边、边编号。

2. 实战部署

3.1 方案 A：邻接矩阵

适合小规模密集图，支持 $O(1)$ 查边。

▶

邻接矩阵

const int maxn = 510;
int g[maxn][maxn];
bool vis[maxn];
int n, m;

void solve( )
{
    // 1. 读图与初始化
    memset( g, 0x3f, sizeof( g ) );
    for( int i = 1; i <= n; ++ i ) g[i][i] = 0;
    
    for( int i = 1; i <= m; ++ i )
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = min( g[u][v], w ); // 处理重边
    }
}

// 2. DFS 遍历
void dfs( int u )
{
    vis[u] = true;
    for (int v = 1; v <= n; ++ v )
    {
        if( g[u][v] > 1e9 || vis[v] ) continue;
        dfs( v );
    }
}

// 3. BFS 遍历
void bfs( int s )
{
    queue< int > q;
    q.push( s );
    vis[s] = true;
    while( !q.empty( ) )
    {
        int u = q.front( ); q.pop();
        for( int v = 1; v <= n; ++ v )
        {
            if (g[u][v] > 1e9 || vis[v]) continue;
            vis[v] = true;
            q.push(v);
        }
    }
}

3.2 方案 B：vector 邻接表

适合大多数场景，动态内存管理，代码极其直观。

▶

邻接表

const int maxn = 100010;
struct Edge { int to, w; };
vector< Edge > adj[maxn];
bool vis[maxn];
int n, m;

void solve( )
{
    // 1. 读图
    for (int i = 1; i <= m; ++ i )
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({ v, w });
    }
}

// 2. DFS
void dfs( int u )
{
    vis[u] = true;
    for( auto& [v, w] : adj[u] )
    {
        if( vis[v] ) continue;
        dfs( v );
    }
}

// 3. BFS
void bfs( int s )
{
    queue< int > q;
    q.push( s );
    vis[s] = true;
    while( !q.empty( ) )
    {
        int u = q.front( );
        q.pop( );
        for( auto& [v, w] : adj[u] )
        {
            if( vis[v] ) continue;
            vis[v] = true;
            q.push(v);
        }
    }
}

3.3 方案 C：链式前向星

性能之选，方便反向边索引，常数极小。

▶

链式前向星

const int maxn = 100010;
const int maxm = 200010;

int head[maxn], ver[maxm], edge[maxm], nxt[maxm], tot;
bool vis[maxn];
int n, m;

void add( int u, int v, int w )
{
    ver[++tot] = v;
    edge[tot] = w;
    nxt[tot] = head[u];
    head[u] = tot;
}

void solve( )
{
    // 1. 初始化与读图
    tot = 1; // 关键：从 1 开始，方便 i^1 找反向边
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        // add(v, u, w); // 无向图
    }
}

// 2. DFS
void dfs( int u )
{
    vis[u] = true;
    for( int i = head[u]; i; i = nxt[i] )
    {
        int v = ver[i];
        if( vis[v] ) continue;
        dfs( v );
    }
}

// 3. BFS
void bfs( int s )
{
    queue< int > q;
    q.push( s );
    vis[s] = true;
    while( !q.empty( ) )
    {
        int u = q.front( );
        q.pop( );
        for( int i = head[u]; i; i = nxt[i] )
        {
            int v = ver[i];
            if( vis[v] ) continue;
            vis[v] = true;
            q.push( v );
        }
    }
}

3. 小 Trick

1. 反向边索引: 初始化 tot = 1。第 1 对边编号为 2, 3，2 ^ 1 = 3, 3 ^ 1 = 2。

2. 重边处理: 邻接矩阵需取 min；邻接表/前向星通常直接存储，由具体算法（如 Dijkstra）处理。

3. 多组数据清空: 只需 memset(head, 0, (n + 1) * sizeof(int)); tot = 1;。

4. 知识关联

• 关联笔记:

  • [[Note] 最短路体系]：遍历 + 松弛操作。

  • [[Note] 网络流核心]：必须使用链式前向星的反向边特性。