C中顶点中的三角形数

Question

我在开发一个函数来计算图形的每个顶点中的三角形数量时遇到了一些困难。这个图是一个邻接表。我做了 Is_Edge 函数 returns 1 如果 V1 和 V2 之间有一条边，这可能 help.Any 提示？结构如下：

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

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

我们可以避免 pairs set/list，如果我们假设所有邻接表都是完整的——从某种意义上说，如果 k 列在 i' s 的邻接表，那么 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

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

C中顶点中的三角形数

Number of Triangles in a Vertex in C

c

graph

adjacency-list