在沒有STL的情況下實現圖形的最佳方法？

我已經分配了一個項目，我必須在一堆節點中，以及在某些節點之間加權的邊。在沒有STL的情況下實現圖形的最佳方法？

我必須然後利用這些信息來找到一個最小生成樹爲圖中的每個連接元件（所以，如果有圖有兩個連接組件，我需要創建兩個生成樹）

美中不足的是我不能使用任何STL庫除外。

我知道我需要創建自己的數據結構，但我不知道我需要哪些數據結構。我想最小的堆將有助於找到要使用的最低重量邊緣，但是如何爲每個連接的組件創建最小堆？

而我在想我需要實現聯合查找才能組織連接組件集。

什麼其他數據結構，我需要實現呢？

來源

2013-07-15 user0123

對於union-find，您需要實現DISJOINT SET。

這裏是一個使用簡單數組實現簡單..看看

// Disjoint Set implementation 
// Shashank Jain 

#include<iostream> 
#define LL long long int 
#define LIM 100005 
using namespace std; 
int p[LIM],n; // p is for parent 
int rank[LIM]; 
void create_set() 
{ 
    for(int i=1;i<=n;i++) 
    { 
     p[i]=i; 
     rank[i]=0; 
    } 
} 
int find_set(int x) 
{ 
    if(x==p[x]) 
     return x; 
    else  
    { 
     p[x]=find_set(p[x]); 
     return p[x]; 
    }   
} 
void merge_sets(int x,int y) 
{ 
    int px,py; 
    px=find_set(x); 
    py=find_set(y); 
    if(rank[px]>rank[py]) 
     p[py]=px; 
    else 
    if(rank[py]>rank[px]) 
     p[px]=py; 
    else 
    if(rank[px]==rank[py]) 
    { 
     p[px]=py; 
     rank[py]++; 
    }    
} 
int main() 
{ 
    cin>>n; // no: of vertex , considering that vertex are numbered from 1 to n 
    create_set(); 
    int a,b,q,i; 
    cin>>q; // queries 
    while(q--) 
    { 
     cin>>a>>b; 
     merge_sets(a,b); 
    } 
    for(i=1;i<=n;i++) 
    { 
     cout<<find_set(i)<<endl; // vertex having same value of find_set i.e same representative of set are in same subset 
    } 
    return 0; 
}

來源

2013-07-16 16:07:45

我會假設你可以選擇你的MST算法和輸出是邊緣的列表。 Borůvka's algorithm實現起來很簡單，除了圖和一個不相交的集合結構外，不需要任何數據結構。相比之下，Prim算法需要一個優先級隊列和一些邏輯來處理不連通的圖，而Kruskal的算法需要一個不相交集結構和排序算法。我會設置這樣的數據結構。每個事件頂點邊緣對都有一個鄰接記錄。

struct Adjacency; 

struct Edge { 
    int weight; 
}; 

struct Vertex { 
    struct Adjacency *listhead; // singly-linked list of adjacencies 
    struct Vertex *parent; // union-find parent 
}; 

struct Adjacency { 
    struct Adjacency *listnext; 
    struct Edge *edge; 
    struct Vertex *endpoint; // the "other" endpoint 
};

來源

2013-07-17 00:26:19

在沒有STL的情況下實現圖形的最佳方法？

回答

相關問題