給結(jié)點(diǎn)分別編號(hào)，輸入這個(gè)無(wú)向圖的的邊，它只有n - 1條邊，所以本質(zhì)上也是樹，但是我們還沒有確定樹的root的結(jié)點(diǎn)，下面我們來構(gòu)造一顆樹。

我們用鄰接矩陣來存下整個(gè)圖，這里用C++里的vector這中數(shù)據(jù)結(jié)構(gòu)，它是可以變長(zhǎng)的，所以存下之后，空間復(fù)雜度就不是n * n了，而是n。

給出一組數(shù)據(jù)：

一共8個(gè)結(jié)點(diǎn)，從0----7編號(hào)。我們假定以1為根結(jié)點(diǎn)構(gòu)建樹。

邊數(shù)據(jù)如下:

0 1
0 2
0 3
1 4
1 5
5 6

5 7

在鄰接矩陣中，他表示為：

0| 1 2 3

1| 0 4 5

2|0

3|0

4|1

5|6 7

6|5

7|5

下面給出代碼實(shí)現(xiàn)：為了驗(yàn)證正確性，我讓它以先序遍歷輸出了

#include <iostream.h> #include <vector.h> const int maxn = 1000; vector<int> G[maxn]; int p[maxn]; int n; void read_tree(){int u,v;scanf("%d",&n);for(int i = 1; i <= n - 1; i++){scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);} } void dfs(int u,int fa){int d = G[u].size();printf("%d ",u);for(int i = 0; i < d; i++){int v = G[u][i];if(v != fa){dfs(v,p[v] = u);}} } int main(){int root;while(scanf("%d",&root) != EOF){read_tree();p[root] = -1;dfs(root,-1);}return 0; }
輸出結(jié)果為：1 0 2 3 4 5 6 7

結(jié)果正確。

2013 04 22 By ACReaper

轉(zhuǎn)載于:https://www.cnblogs.com/sixcoder/archive/2013/04/22/3825990.html

總結(jié)

以上是生活随笔為你收集整理的无根树转为有根数(图论) By ACReaper的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。