c - C 中顶点的三角形数量

Question

我在开发一个计算图每个顶点中三角形数量的函数时遇到了一些困难。该图是一个邻接表。我做到了如果 V1 和 V2 之间存在边缘，Is_Edge 函数将返回 1，这可能会有所帮助。有任何提示吗？结构如下:

struct AdjListNode
{
    int dest;
    int TrianglesNumber;
    int weight;
    struct AdjListNode* next;
};

struct AdjList
{
    struct AdjListNode *head; 
};

struct Graph
{
    int V;
    struct AdjList* array;
};

int Is_Edge(struct Graph *Graph,int V1,int V2){
    int find=0;
    if(V1 > Graph->V || V2 > Graph->V)
        return 0;
    else{
        struct AdjListNode *aux = Graph->array[V1].head;
        while((aux!=NULL)&&(!find)){
                if(aux->dest == V2)
                    find = 1;
                else
                    aux = aux->prox;
        }
        return(find);
    }
}

Answer 1

在知道希望代码实现什么逻辑或算法之前，不要编写代码。

如果您知道哪些顶点通过边连接，假设您有一个函数 Connected(i, j)，以及顶点总数 N，那么您可以使用(伪代码)计算共享顶点k的三角形数量

Function triangles_at_vertex(k):
    Count = 0
    For i = 1 to N:
        If i != k AND Connected(i, k):
            For j = 1 to N:
                If j != i AND j != k AND Connected(i, j):
                    Count = Count + 1
                End if
            End For
        End If
    End For
    Return Count
End Function

但是，上述函数根本不使用邻接表。

<小时/>

假设您确实有顶点 k 以及与 k 相邻的所有顶点的邻接列表。计算三角形的一种方法是计算也连接到顶点 k 的唯一连接顶点对的数量:

Function triangles_at_vertex(k):
    pairs = Empty
    kList = Adjacency_list(k)
    For i in kList:
       iList = Adjacency_list(i)
       For j in iList:
           If (j in kList):
               If ((Pair(i,j) NOT in pairs) AND
                  ((Pair(j,i) NOT in pairs):
                   Add Pair(i, j) to pairs
               End If
           End If
       End For
    End For
    Return Count(pairs)
End Function

上面的对可以是列表、有序集(对的数组)或无序集。请注意，它不能具有与顶点 k 的邻接列表一样多的成员，因为我们要查找的所有三角形中的所有顶点都必须位于 k 的邻接列表中。

<小时/>

如果我们假设所有邻接表都是完整的，那么我们可以避免pairs集合/列表——从某种意义上说，如果k列在i中 的邻接表，则 i 也列在 k 的邻接表中。通常，只存储一半的邻接关系，以减少内存使用。

然后，我们知道我们对每对恰好计数两次，因为我们同时计数 i,j 和 j,i:

Function triangles_at_vertex(k):
    Count = 0
    kList = Adjacency_list(k)
    For i in kList:
       iList = Adjacency_list(i)
       For j in iList:
           If (j in kList):
               Count = Count + 1
           End If
       End For
    End For
    Return Count / 2
End Function

<小时/>

首先选择您的算法，然后开始编码。