C编程两跳邻居

Question

我不确定如何正确获取我的两跳邻居。这几乎是正确的，但在我的输出中，我不想包含相同的顶点。对于我现在的输出，如果顶点 0 为 0，它会显示“顶点 0：0..... 我想跳过它当前正在查看的顶点。

请帮帮我，我的两跳代码是不是错了？

这是我的代码：

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#define M 20
#define N 20
int main()
 {
int i, j, x, a, b;
int G[20][20] = { { 0 } };
/*creaate random adjaceney matrix*/
printf("==================================================\n");
printf("Welcome to my Graph Processing tool!\n\n");

srand(time(NULL));
for (i = 0; i < M; i++) {
    for (j = 0; j < N; j++) {
        if (i == j) {
            G[i][j] = 0;
        }
        else {
            G[i][j] = rand() % 2;
            G[j][i] = G[i][j];
        }
    }
}
/*check whether the whole row equals to 0*/
for (j = 0; j < N; j++) {
    if (G[j] == 0) {
        x = rand() % 20 + 1;
        G[x][j] = G[j][x] = 1;
    }
    /*print the matrix G*/
    else
    {

        printf("The adjacency for graph G is\n");
        for (i = 0; i < M; i++) {
            for (j = 0; j < N; j++) {
                printf("%d ", G[i][j]);
            }
            printf("\n");
        }
    }
}

/*all one-hop neighbors*/
printf("\nList of one-hop neighbors:");
for (i = 0; i < M; i++) {
    printf("\nVertex %d: ", i);
    for (j = 0; j < N; j++) {
        if (G[i][j] == 1) {

            printf("%d ", j);
        }
    }
}
printf("\n===================================\n\n");


/*two-hop neighbors*/

    for (i = 0; i < M; i++) {
        printf("\nVertex %d: ", i);
        for (j = 0; j < N; j++) {
            if (G[i][j] == 0) {

                printf("%d ", j);
            }
        }
        }

}

printf("\n============================================\n");


system("pause");
return 0;
}

这是我的输出：

One hop Two hop

Answer 1

这里有两点需要注意。

在变量命名时更具描述性，这样会更容易阅读。

M-ROWS、N-COLS、G-Graph

当你循环遍历每一行时，你将 j 初始化为 0。这包括你想要忽略的顶点。

for (j = 1; j < N; j++)

Answer 2

@Jake 提供的答案仅适用于节点 0。如果只查看不同的节点，您需要做的

for (j = 0; j < N; j++) {
    if (i != j && G[i][j] == 0) {
        printf("%d ", j);
    }
}

此外，您假设所有没有边的节点都是两跳邻居。这是不正确的。计算实际两跳邻居的一种方法是 ((A + I)^2 > 0) - ((A + I) > 0)，其中 I 是单位矩阵。

此外，您可以通过三层循环对其进行编码：

int node, neighbor, neighbor2;
for (node = 0; node < N; node++) {
    printf("\nVertex %d: ", node);
    for (neighbor = 0; neighbor < N; neighbor++) {
        if (G[node][neighbor] == 1) {
            for (neighbor2 = 0; neighbor2 < N; neighbor2++) {
                if (node != neighbor2 && G[neighbor][neighbor2] == 1) {
                    printf("%d ", neighbor2);
                }
            }
        }
    }
}

请注意，根据定义 M=N，所以我只使用了 N。此外，这可能会打印一些 2 跳邻居两次。您可能想在打印前进行一些过滤。

C编程两跳邻居

C programming two-hop neighbors

c

neighbours

adjacency-matrix