有向图节点的相邻节点

Question

18

在有向图中，节点邻居的定义是什么？

更具体地说，在下面的图中，哪些节点被认为是节点0的邻居？

《破解程序员面试》似乎暗示0的邻居是1和2，但没有明确说明，我找不到一个合适的定义。在邻接矩阵表示中，需要遍历所有节点才能确定节点的邻居。这似乎意味着2被认为是0的邻居，否则你只需要遍历0的行来查找它的邻居。但它从未清楚地说明这一点。

- Nicola Pedretti

1

我同意你的观点，如果定义只要求2和0之间有一条边（不考虑方向），那么2被认为是0的邻居。但这是一个很好的问题：一个节点可以是不是它的邻居的节点的邻居吗？当然，邻接矩阵会将2连接到0，但也会将0标记为未连接到2。我在快速搜索中没有找到明确的答案，所以我也很好奇。 - Carser

我并不介意。通常这种东西在使用时总是有明确的定义，因此很清楚。当上下文不是直接清晰时，人们会更具体地谈论进入和离开的邻居，或者前驱和后继等。 - Zabuzard

你可以使用这个源代码： https://www.cs.cmu.edu/afs/cs/academic/class/15210-f14/www/lectures/graph-intro.pdf - Hamed Baziyad

2个回答

2

在有向图中，每个有向边都有一个尾部和一个头部，分别表示边离开的地方和到达的地方，从而形成节点N的入邻居和出邻居。所有边到达N的节点都是出邻居。所有离开N的边到达的节点都是入邻居。

节点N的出邻居是指在定义图的ALR（邻接表表示）的数组（或哈希映射）中属于该元素N的单链表中的所有节点。

在邻接矩阵中，必须决定将尾节点放在行中，将头节点放在列中，还是反之。矩阵的正文部分包含定义入邻居或出邻居的相关值（通常是非对称的）。

- user6025732

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jerry Coffin · Accepted Answer

在有向图中，“邻居”一词很少被使用，通常需要加上限定词（如果没有限定词，至少有些人会认为这可能是一个错误）。通常你会说出度邻居（或者叫做出边邻居）—— 有从一个顶点指向其他顶点的边，和入度邻居（或者叫做入边邻居）—— 有从其他顶点指向该顶点的边。

同样，在无向图中你可以谈论到一个邻域，而在有向图中你需要谈论出度邻域或入度邻域。