c语言如何在邻接矩阵中找到两跳邻居

Question

#include<stdio.h>
#include<math.h>
#include<stdlib.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*/
    printf("List of two-hop neighbors:");
    /*for (i = 0; i < M; i++) {
        printf("\nVertex %d: ", i);
        for (j = 0; j < N; j++) {

            if (G[i][j] == 1) {                     
                    for (a = 0; a < 20; a++) {
                        if (G[a][j] == 1 && G[a][i] != 1 /*&& G[a][j] == 1 && G[i][a] != 1) {

                            printf("%d ", a);
                        }
                    }
                }
            }
        }
    printf("\n=================================================\n");*/

    for (i = 0; i < M; i++) {
        printf("\nVertex %d: ", i);
        for (j = 0; j < N; j++)/*; for(a=0;a<j;a++)*/ {
            for (a = 0; a < 20; a++) {
                if (G[i][j] == 1 && i != j) {
                    if (G[a][j] == 1 && G[a][i] != 1 && a != i && a != j && i != j) {
                        printf("%d ", a);
                    }

                }
                /*else {
                    printf("NONE");
                }*/
            }
        }

        }

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


    system("pause");
    return 0;
}

第 1 处的代码是生成一个 20x20 的随机邻接矩阵 矩阵是 G[i][j] 它是对称的，矩阵中只有 0 和 1 矩阵的主对角线都为0

然后我找到一跳邻居 一跳邻居部分我确信它是正确的

2-hop neighbors 部分的答案是错误的

我的想法是如果 G[i][j]=1，G[a][j]=1 和 G[a][i] !=1，那么 i 和 a 将是两跳邻居

但是如何循环a呢？ 如何使用for循环寻找二跳邻居？

我这里有图像输出 enter image description here

Answer 1

你的想法是正确的。为了避免嵌套太多的for循环，让我们写一个函数来测试两个节点是否是两跳邻居:

#include <stdbool.h>

bool distance_is_two (int i, int j)
{
    if ((i == j) || (G[i][j] == 1)) {
        return false;
    }

    for (int k = 0; k < N; k++) {
        if ((k == i) || (k == j)) {
            continue;
        }

        if ((G[i][k] == 1) && (G[k][j] == 1)) {
            return true;
        }
    }

    return false;
}