殘差圖的最快數據結構

Question

我想實現一個有數千個節點和邊的流算法，因此我需要高效的數據結構。目前，我做到以下幾點：

結構節點：

Double Linked Array (Parents) //Edges that enter the node (basicaly a tuple that contains a pointer to the parent node and the weight, current flow of the edge 
Double Linked Array (Sons) //Edges that leave the node 

的問題是，當我執行BFS，給定一個節點U我需要看看邊緣的residual graph（基本上向後的邊緣因爲我可以有平行邊緣，所以我需要始終知道哪個後向邊緣來自哪個前向邊緣。

目前我正在通過首先處理Sons（v）中的所有邊來解決問題，然後我定義了一個映射，該映射爲我提供了所有邊的目標節點w中的Parents（w）的索引。因此，我獲得了存儲的後向邊緣並可以執行我的算法。然而，這些地圖具有日誌（E）訪問時間，這會降低我的算法的速度。我應該如何解決這個問題（雙鏈表被實現爲std :: vector）？

Answer 1

我使用的表示是一樣的東西邊緣名單，但與

typedef long long dintype; 
struct edge{ 
    edge(int t_ = 0,int n_ = 0, dintype c_ = 0){ 
    to = t_; 
    next = n_; 
    cap = c_; 
    } 
    int to,next; 
    dintype cap; 
}; 
const int max_edges = 131010; 
const int max_nodes = 16010; 
edge e[max_edges]; 
int first[max_nodes]; // initialize this array with -1 
int edges_num; 
inline void add_edge(int from,int to, dintype cap){ 
    if(edges_num == 0){ 
    memset(first,-1,sizeof(first)); 
    } 
    e[edges_num].to = to;e[edges_num].cap = cap; 
    e[edges_num].next = first[from];first[from] = edges_num++; 

    e[edges_num].to = from;e[edges_num].cap = 0; 
    e[edges_num].next = first[to];first[to] = edges_num++; 
} 

我用全局數組能夠更好地解釋這個想法的更多信息。我用這個爲我的dinitz algorithm。

現在有點解釋。在數組「e」中，我保留所有邊。在數組first [v]中，我保存陣列e中v的第一個邊的索引。如果數組e中的索引idx存在邊，則反向邊存儲在索引爲idx^1的元素中。 因此，這種表示使我們能夠有一個鄰居列表（從第一個[v]開始跟蹤下一個索引，直到它變爲-1），並且能夠在常量時間訪問反向邊沿。

Answer 2

int src,snk,nnode,nedge; 
int fin[100000],dist[100000];//nodes 
int cap[100000],next[100000],to[100000]; 
void init(int s,int sn,int n) 
{ 
    src=s,snk=sn,nnode=n,nedge=0; 
    memset(fin,-1,sizeof(fin)); 
} 
void add(int u,int v,int c) 
{ 
    to[nedge]=v,cap[nedge]=c,next[nedge]=fin[u],fin[u]=nedge++; 
    to[nedge]=u,cap[nedge]=0,next[nedge]=fin[v],fin[v]=nedge++; 
} 
bool bfs() 
{ 
    int e,u,v; 
    memset(dist,-1,sizeof(dist)); 
    dist[src]=0; 
    queue<int> q; 
    q.push(src); 
    while(!q.empty()) 
    { 
     u=q.front(); 
     q.pop(); 
     for(e=fin[u];e>=0;e=next[e]) 
     { 
      v=to[e]; 
      if(cap[e]>0&&dist[v]==-1) 
      { 
       dist[v]=dist[u]+1; 
       q.push(v); 
      } 
     } 
    } 
    if(dist[snk]==-1) 
     return false; 
    else 
     return true; 
} 
int dfs(int u,int flow) 
{ 
    if(u==snk) 
     return flow; 
    int e,v,df; 
    for(e=fin[u];e>=0;e=next[e]) 
    { 
     v=to[e]; 
     if(cap[e]>0&&dist[v]==dist[u]+1) 
     { 
      df=dfs(v,min(cap[e],flow)); 
      if(df>0) 
      { 
       cap[e]-=df; 
       cap[e^1]+=df; 
       return df; 
      } 
     } 
    } 
    return 0; 
} 
int dinitz() 
{ 
    int ans=0; 
    int df,i; 
    while(bfs()) 
    { 
     while(1) 
     { 
      df=dfs(src,INT_MAX); 
      if(df>0) 
       ans+=df; 
      else 
       break; 
     } 
    } 
    return ans; 
} 

這是我迪尼茨算法代碼 這裏初始化函數初始化鄰接表 添加添加列表中的一個新的邊緣，散熱片給人在鄰接表 的最後一個節點，這樣你們就可以訪問所有元素名單通過下面的循環

for(e=fin[u];e>=0;e=next[e]) 
{ 
    v=to[e]; 
} 

其中u爲u想找到 v將相鄰的元素賦予到u 也同時尋找最大流量u需要前向邊緣和後向邊緣，其相鄰元素的節點所以假設前沿是e ，那麼後向邊將是e^1，反之亦然，但是爲此，邊的起始索引應該爲零