数据结构邻接表有向图

邻接表是一种常见的图的存储方式，它将每个顶点的所有邻居顶点存储在一个链表中。邻接表可以用于存储有向图和无向图。下面是一个有向图的邻接表的例子：

graph = {
    '1': ['2'],
    '2': ['4', '5'],
    '3': ['1', '2'],
    '4': ['5'],
    '5': ['3']
}

这个有向图共有5个顶点和6条边。每个顶点都对应一个键，其值是一个列表，包含了该顶点的所有邻居顶点。例如，顶点1的邻居是2，顶点2的邻居是4和5，顶点3的邻居是1和2，以此类推。

如果要插入新的顶点和边，可以直接在字典中添加新的键值对。例如，如果要在上面的有向图中插入一个新的顶点6和一条从顶点3到顶点6的边，可以这样做：

graph['6'] = []  # 添加新的顶点6
graph['3'].append('6')  # 在顶点3的邻居列表中添加顶点6

这样，邻接表就被更新了，新的有向图如下所示：

graph = {
    '1': ['2'],
    '2': ['4', '5'],
    '3': ['1', '2', '6'],
    '4': ['5'],
    '5': ['3'],
    '6': []
}

相关问题

数据结构有向图邻接表

有向图邻接表是一种数据结构，用于表示有向图中的顶点及其相邻顶点。它利用哈希表或数组来存储图中的每个顶点，并将每个顶点的邻居顶点列表存储为链表或动态数组。

在有向图邻接表中，每个顶点都有一个对应的链表或动态数组，其中存储了从该顶点出发的边的目标顶点。这种方式可以有效地表示稀疏图，因为它只存储存在边的顶点和它们的邻居。

例如，考虑以下有向图的邻接表表示：

顶点1 -> [2, 3]
顶点2 ->
顶点3 ->

这表示了一个有3个顶点和4条边的有向图。顶点1有两条边分别指向顶点2和顶点3，顶点2有一条边指向顶点3，顶点3有一条边指向顶点1。

使用邻接表表示有向图可以提供高效的遍历和查找操作，因为可以直接访问每个顶点的邻居列表。然而，在查找特定边的存在时可能会稍微慢一些，因为需要遍历链表或动态数组来检查目标顶点是否存在。

数据结构图邻接表代码

以下是邻接表的基本结构和代码实现：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

struct Edge{
    int to, nxt;
}edge[maxn];

int head[maxn], tot = 0;
int n, m;

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

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v); // 有向图只需要这一句
        add(v, u); // 无向图需要加上这一句
    }
    return 0;
}

其中，结构体 `Edge` 表示每条边的信息，包括了边的终点 `to` 和下一条邻接表中与该边起点相同的边的位置 `nxt`。数组 `head` 表示每个点的邻接表的起点位置，初始化为 `-1`。函数 `add` 用于向邻接表中添加一条边。在主函数中，先读入点数和边数，再循环读入每一条边并加入到邻接表中。对于有向图，只需要加入一次；对于无向图，需要加入两次，因为无向图中的边是双向的。