有向图与无向图

有向图：a ——> b;
无向图：a —— b;
若为无向图，则建两条边：a -> b, b -> a;
(无向图是特殊的有向图)

树与图的存储

邻接矩阵 -> 二维数组
g[a][b] : 表示 a -> b 的一条边
邻接矩阵不能维护重边

邻接表：
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

树与图的深度优先遍历

int dfs(int u) {
    st[u] = true; // st[u] 表示点u已经被遍历过

    // 遍历该结点的所有出边
    for (int i = h[u]; i != -1; i = ne[i])
    {

        int j = e[i];
        // 如果点j没有被搜索过，则dfs( j )
        if (!st[j]) dfs( j );
    }
}

树与图的广度优先遍历

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size()) // 队列不空
{ 
    // 取出队头
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        // j未被搜索过
        if (!st[j]) // d[j] == -1 
        {
            st[j] = true; // 表示点j已经被遍历过
            d[x] = d[t] + 1; // 距离增加
            q.push(j);  // 存入队列

        }
    }
}