algorithm - 在邻接矩阵中，如何找到给定顶点的邻居的邻居？

Question

假设我们有一个像这样的 4x4 邻接矩阵:

和给定的顶点，比如说int v=1

如何找到顶点 1 的邻居的邻居，并将它们添加到列表中？例如，如果我想从顶点 1 到顶点 4，我必须先到顶点 2，然后从顶点 2 到顶点 4，因为从 1 到 4 没有直接路径。我想添加顶点 4 和类似于列表。

现在这是我得到的:

int v=1;
for(int i=0;i<adjmat.length;i++){
            if (i==v){
                for(int j=0;j<adjmat[i].length;j++){
                    if (j!=i){ // self loops do not count
                        // if adjmat[i][j] has a neighbor, add the neighbor to a list 
                    }
                }
            }
        }

Answer 1

你所拥有的似乎是正确的。

简单说明一下: 当循环从 0 开始时，图形的索引从 1 开始。您可能不担心这一点，但无论如何，我们假设顶点的命名从 1 开始，并且数组从 0 开始。

那么唯一真正关心的是你的最外层循环。如果您只需要找到一个顶点 v 的邻居的邻居(您的示例，v = 1)

int v_i = v-1;
for(int j=0;j<adjmat[v_i].length;j++){
    if (v_i!=j){ // self loops do not count
        // if adjmat[i][j] has a neighbor, add the neighbor to a list 
        //*NOTE maybe only if that neighbor is also not a self loop, one of v's first neighbors, or v 
    }
}