输出用邻接表(逆邻接表)存储表示的图
时间: 2023-11-05 14:25:37 浏览: 68
好的,我可以帮你解答这个问题。邻接表和逆邻接表是一种常用的图的存储结构,它们可以方便地表示图中节点之间的关系。
邻接表是一种链式存储结构,将每个节点的邻居节点存储在一个链表中。具体地说,对于每个节点,我们可以使用一个链表来存储与该节点相邻的节点。因此,邻接表由一个节点数组和一个链表数组组成。
逆邻接表是邻接表的反向表示,它存储了每个节点的入边信息。对于每个节点,我们可以使用一个链表来存储指向该节点的边。因此,逆邻接表也由一个节点数组和一个链表数组组成,但是链表中存储的是指向该节点的边。
下面是一个使用邻接表和逆邻接表存储的有向图的例子:
```
// 邻接表
int adjList[5][3] = {{1, 3, -1}, {2, -1, -1}, {4, -1, -1}, {1, 2, 4}, {0, 3, -1}};
// 逆邻接表
int reverseAdjList[5][3] = {{4, -1, -1}, {0, 3, -1}, {1, -1, -1}, {3, -1, -1}, {0, -1, -1}};
```
在这个例子中,有向图包含 5 个节点,编号分别为 0 到 4。邻接表中,第 i 个节点的邻居节点存储在 adjList[i] 这个链表中,链表中的每个元素表示一条从 i 到该元素所表示的节点的有向边。例如,adjList[0] = {1, 3, -1} 表示节点 0 有两条出边,一条指向节点 1,一条指向节点 3。
逆邻接表中,第 i 个节点的入边信息存储在 reverseAdjList[i] 这个链表中,链表中的每个元素表示一条从该元素所表示的节点到 i 的有向边。例如,reverseAdjList[0] = {4, -1, -1} 表示节点 0 有一条入边,来自节点 4。
希望这个例子能够帮助你理解邻接表和逆邻接表的概念。