C中頂點的三角形數量

Question

我在開發函數來計算圖形每個頂點的三角形數量方面遇到一些困難。此圖是一個鄰接列表。我做了 Is_Edge函數返回1，如果V1和V2之間有邊緣，這可能會有所幫助。任何提示？這些結構如下：

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組/列表中，如果我們假設所有的鄰居列表是完成 - 如果k在i列感小號的鄰接表，然後i在k上市「鄰接表也是如此。通常，只有一半的鄰接被存儲，用於較小的存儲器使用。

然後，我們知道，我們計算每對正好兩次，因爲我們都算和i,jj,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 

---

先挑你的算法，然後開始編碼。