有向圖轉樹演算法

A. 有向圖的最小生成樹該怎麼求

蛋疼的軟體，蛋疼的線性表、棧、隊列、數組、樹、圖…

B. 數據結構，一個有向圖及其生成森林

將形成迴路的邊去掉，然後樹轉森林，樹和圖的區別，就是沒有迴路。比如你這個圖中，把fb和ea，cb，de去掉，直接就變成森林了，很簡單。

C. 對給定的有向圖G及頂點v0，設計演算法以判斷G是否是一棵以v0為根的有向樹。若是有向樹返回TRUE否則返回FALS

直接從v0開始BFS，如果搜到環或者沒有搜完整個圖就是FALSE啊

D. 數據結構圖的有向樹的問題

那個有向樹說的是左邊有向圖在右邊的生成森林的各棵樹

E. 生成樹的標准有哪些各有什麼異同

一 區別

最小生成樹能夠保證整個拓撲圖的所有路徑之和最小，但不能保證任意兩點之間是最短路徑。

最短路徑是從一點出發，到達目的地的路徑最小。

二 實現方法

1. 最小生成樹

2. 最小生成樹有兩種演算法來得到：Prims演算法和Kruskal演算法。

3. Kruskal演算法：根據邊的加權值以遞增的方式，一次找出加權值最低的邊來構建最小生成樹，而且規定：每次添加的邊不能造成生成樹有迴路，知道找到N-1個邊為止。

4. Prims演算法：以每次加入一個的臨界邊來建立最小生成樹，直到找到N-1個邊為止。其規則為：以開始時生成樹的集合（集合U）為起始的定點，然後找出與生成樹集合鄰接的邊（集合V）中，加權值最小的邊來建立生成樹，為了確定新加入的邊不會造成迴路，所以每一個新加入的邊，只允許有一個頂點在生成樹集合中，重復執行此步驟，直到找到N-1個邊為止。

5. 2 最短路徑

演算法描述

(這里描述的是從節點1開始到各點的dijkstra演算法，其中Wa->b表示a->b的邊的權值，d(i)即為最短路徑值)

1． 置集合S={2,3,n}, 數組d(1)=0, d(i)=W1->i(1,i之間存在邊) or +無窮大(1.i之間不存在邊)

2． 在S中，令d(j)=min{d(i),i屬於S}，令S=S-{j}，若S為空集則演算法結束，否則轉3

3． 對全部i屬於S,如果存在邊j->i，那麼置d(i)=min{d(i), d(j)+Wj->i}，轉2

Dijkstra演算法思想為：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以後每求得一條最短路徑 , 就將 加入到集合S中，直到全部頂點都加入到S中，演算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大於從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。

演算法具體步驟

（1）初始時，S只包含源點，即S=，v的距離為0。U包含除v外的其他頂點，U中頂點u距離為邊上的權（若v與u有邊）或 ∞(若u不是v的出邊鄰接點）。

（2）從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。

（3）以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u（u U）的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改後的距離值為頂點k的距離加上邊上的權。

（4）重復步驟（2）和（3）直到所有頂點都包含在S中。

復雜度分析

Dijkstra 演算法的時間復雜度為O(n^2)空間復雜度取決於存儲方式，鄰接矩陣為O(n^2)

F. 樹和有向圖是什麼關系呢

閱讀關於Prim演算法和Kruskal演算法的說明,這兩個演算法就是用來構造最小生成樹的,對於有向圖和無向圖均可,並不是說有向圖要像無向圖那樣有環才可以有生成樹

G. 數據結構圖的有向樹的問題

第一句話：比如這個有向圖可以是這樣的
A--->B---->C---->D
在這個有向圖中，A的入度為0 其餘各點B、C、D均為1
第二句話：他都是樹了，他的入度一定是1啊。
所謂樹：它具有以下的特點：
1、每個節點有零個或多個子節點；
2、沒有父節點的節點稱為根節點；
3、每一個非根節點有且只有一個父節點；
4、除了根節點外，每個子節點可以分為多個不相交的子樹；(以上特點摘自網路)
你看第3點，只有一個父節點的意思，就是說非根節點的入度只可能為1，如果他入度不是1
他就不是一棵樹。
你體會一下。

H. 已知一個有向圖如圖，請分別寫出從頂點a出發進行深度優先遍歷和廣度優先遍歷所得到的頂點序列及生成樹。

一、深度生成樹：abdcefigh，如下圖所示：

相關特點：

（1）生成樹協議提供一種控制環路的方法。採用這種方法，在連接發生問題的時候，你控制的乙太網能夠繞過出現故障的連接。

（2）生成樹中的根橋是一個邏輯的中心，並且監視整個網路的通信。最好不要依靠設備的自動選擇去挑選哪一個網橋會成為根橋。

（3）生成樹協議重新計算是繁冗的。恰當地設置主機連接埠(這樣就不會引起重新計算)，推薦使用快速生成樹協議。

（4）生成樹協議可以有效的抑制廣播風暴。開啟生成樹協議後抑制廣播風暴，網路將會更加穩定，可靠性、安全性會大大增強。

I. 圖的所有生成樹的演算法

邊構成,並包含G的所有頂點的樹稱為G的生成樹(G連通).
加權無向圖G的生成樹的代價是該生成樹的所有邊的代碼(權)的和.
最小代價生成樹是其所有生成樹中代價最小的生成樹.

參考代碼:
(僅為主程序,更多代碼在

解壓密碼: )
#include "Sets.h"
#include "themap.h"
#include "windows.h"
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

/*
功能:
演示Kruskal演算法和Prim演算法
集合的並,元素查找的操作及應用
說明:
代碼均在vc++6.0環境下編譯均通過
在非VC++6.0環境下編譯請去掉頭文件 windows.h 和函數 end()
如果NULL未定義請自定義
#define NULL 0 或
#define NULL ((void*)0)
作者:
hacker
時間:
2007.2.3
*/

const VSIZE = 7;//7個頂點
const INFINITY = 10000;//10000作為無窮大來處理

void LoadData(int cost[][VSIZE+1], Edge edge[]);
void end();

/*
函數名:
Kruskal 和 Prim
參數:
邊,代價,邊數,頂點數,最小代價生成樹的頂點
返回值:
返回值為-1,不存在最小代價生成樹
返回值大於0時為最小代價生成樹的代價
最小代價生成樹的邊在vector<Edge>& t
*/
int Kruskal(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t);
int Prim (Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t);

int main()
{
int cost[VSIZE+1][VSIZE+1];//0不用
Edge edge[9];//9條邊
vector<Edge> t;//用來存儲最小代價生成樹的頂點
int mincost;//最小代價

LoadData(cost, edge);

if ( (mincost = Kruskal(edge, cost, 9, VSIZE, t))!=-1)
{
cout<<"最小代價是:"<<mincost<<endl<<"邊是:";
for (int i = 0;i<t.size();i++)
cout<<t[i];
cout<<endl;
}

t.clear();
if ( (mincost = Prim(edge, cost, 9, VSIZE, t))!=-1)
{
cout<<"最小代價是:"<<mincost<<endl<<"邊是:";
for (int i = 0;i<t.size();i++)
cout<<t[i];
cout<<endl;
}

end();
return 1;
}

void LoadData(int cost[][VSIZE+1], Edge edge[])
{
edge[0].u = 1; edge[0].v = 2; edge[0].weight = 28;
edge[1].u = 1; edge[1].v = 6; edge[1].weight = 10;
edge[2].u = 2; edge[2].v = 3; edge[2].weight = 16;
edge[3].u = 2; edge[3].v = 7; edge[3].weight = 14;
edge[4].u = 3; edge[4].v = 4; edge[4].weight = 12;
edge[5].u = 4; edge[5].v = 5; edge[5].weight = 22;
edge[6].u = 4; edge[6].v = 7; edge[6].weight = 18;
edge[7].u = 5; edge[7].v = 6; edge[7].weight = 25;
edge[8].u = 5; edge[8].v = 7; edge[8].weight = 24;

for (int i=1;i<=7;i++)
for (int j=1;j<=i;j++)
cost[i][j] = cost[j][i] = INFINITY;
for (i=0;i<9;i++)
cost[edge[i].u][edge[i].v] =
cost[edge[i].v][edge[i].u] = edge[i].weight;
}

int Kruskal(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t)
{
Sets s(esize);
priority_queue<Edge, vector<Edge>, EdgeGreater> pq;
int mincost = 0;

for (int i = 0;i<esize;i++)
//把所有的邊放入優先隊列
pq.push(edge[i]);

i = 0;
while (i<vsize-1 && !pq.empty())
{
Edge temp = pq.top();//取出當前權最小的邊
pq.pop();

int j = s.SimpleFind(temp.u);
int k = s.SimpleFind(temp.v);

if (j!=k)//如果不構成環
{
i++;
t.push_back(temp);
mincost +=cost[temp.u][temp.v];
s.SimpleUnion(j, k);
}
}

if (i!=vsize-1)
{
t.clear();
return -1;
}
else
{
return mincost;
}
}

int Prim(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t)
{
priority_queue<Edge, vector<Edge>, EdgeGreater> pq;
vector<Edge> sortededge;
int i;

for (i =0;i<esize;i++)
pq.push(edge[i]);

for (i =0;i<esize;i++)
{//對邊進行從小到大排列,放到sortededge中
sortededge.push_back(pq.top());
pq.pop();
}

int distance[VSIZE+1];
int j;
int mincost = sortededge[0].weight;
Edge temp = sortededge[0];

t.push_back(temp);
for (i=1;i<=vsize;i++)
distance[i] = 1;//每個點都不在已生成樹里

distance[temp.u] = distance[temp.v] = 0;//最短的邊的兩個點放到生成樹里

for (i=2;i<=vsize-1;i++)
{//尋找另外的邊
int exist = 0;//設置是否找到符合條件的邊的狀態標志為未找到
for (j=1;j<esize;j++)
if (distance[sortededge[j].u] ^ distance[sortededge[j].v] == 1)
{//由於邊是排序好了的,所以從小邊向大邊找,找到的第一個符合條件的邊可以
//加到生成樹里
int k = (distance[sortededge[j].u] == 0) ? sortededge[j].v :\
sortededge[j].u;
distance[k] = 0;
mincost += sortededge[j].weight;
t.push_back(sortededge[j]);
exist = 1;
break;
}
if (!exist)
{
t.clear();
return -1;
}
}

return mincost;
}

void end()
{
if (MessageBox(NULL,\
"歡迎到學習交流(源代碼在論壇下載)\n\t\t(確定後自動訪問論壇)",\
"supcoder", IDOK) == IDOK)
{
char cmdLine[] = "iexplore ";
char path[256];
char buf[256];
STARTUPINFO si;
ZeroMemory(&si, sizeof(si));
PROCESS_INFORMATION ProcessInformation;
GetSystemDirectory(buf, 256);
sprintf(path, "%c:\\Program Files\\Internet Explorer\\IEXPLORE.EXE", buf[0]);
CreateProcess(path,cmdLine, NULL, NULL, 1, 0, NULL, NULL, &si, &ProcessInformation);
}

cout<<"==============================================================================="<<endl;
cout<<"\t\t\t\t 謝謝使用!"<<endl;
cout<<"\t\t\t "<<endl;
Sleep(1000);
}