1樓：海天之源
一棵深度優先生成樹。
圖的深度優先遍歷類似於樹的先序遍歷。
特點是儘可能先往深方向進行搜尋。
所以，從這可以知道，遍歷的第一個點將是生成樹的根節點。
每個頂點至多呼叫一次dfs函式。而且一旦某個頂點被標誌成已被訪問，就不再從它出發進行搜尋。
遍歷圖的過程實質上是對每個頂點查詢其鄰接點的過程。
其耗費的時間則取決於所採用的儲存結果。
當用鄰接矩陣表示圖時，查詢每個頂點的鄰接點的時間複雜度為o(n平方)。n為頂點數
而當用鄰接表做圖的儲存結構時，找鄰接點的時間複雜度為o(e)。e為圖中邊數。
由此，當以鄰接表做儲存結構時，深度優先搜尋遍歷圖的時間複雜度為o(n+e)。
希望我的回答對您有幫助~
2樓：嘛小亂
深度優先搜尋不是產生一棵樹。。。。而是一個深度優先森林
已知一個有向圖如圖，請分別寫出從頂點a出發進行深度優先遍歷和廣度優先遍歷所得到的頂點序列及生成樹。
3樓：匿名使用者
深度：abdcefigh
廣度：abcdefghi
4樓：蘅域
dfs(depth-first-search)深度優先搜尋演算法，是為了要達到被搜尋結構的葉節點的搜尋演算法的一種，早期使用較多。
寬度優先搜尋演算法(又稱廣度優先搜尋)是最簡便的也是很多重要圖演算法原型搜尋演算法之一。
5樓：請叫我聲傑哥
你知道一個郵箱圖形。分別寫出頂點可以發出一個深度的優先遍歷條件。
鄰接表的儲存結構下圖的深度優先遍歷類似於二叉樹(樹)的( )。
6樓：淚的
先序遍歷。--------------------肯定正確
試分別畫出自頂點1出發進行遍歷所得的深度優先生成樹和廣度優先生成樹。
7樓：匿名使用者
從1開始，1連線7,7連線3，3連線4,4連線5,5連線6,6連線2（1已經連過了）（2連線了3,7，但是3和7都已經連過，所以回到上一級6,6的連線是1,2都已經連過，所以再回到上一級5）5連線10 。
（10連線1,6都已經連過了，所以回到上一級5，但是5的所有連線點都連過了，所以回到上一級4）4連線9,（9連線5,10都已經連過了，所以回到上一級4,4也已經練完了，所以再回到上一級3）3連線8，至此連完。
廣度遍歷：從1開始，連線7和9，下一個是7，連線3和10 ，下一個是9，連線5，下一個是3，連線4和8，下一個是10 連線6，下一個是5，沒有什麼連線的，下一個是4，沒有什麼連線的，下一個是8，沒有什麼連線的，下一個是6，連線2，至此連完。
資料結構 知道深度優先遍歷序列了怎麼畫對應的生成樹？
8樓：匿名使用者
沒看懂你的意思，這題目應該是先給你一張圖，然後根據圖來寫深度優先遍歷序列和生成樹。而不是給出前者畫後者。
如果只有前者，後者可以畫出很多種都是匹配前者的。
資料結構 圖g的廣度、深度優先生成樹分別怎麼畫呀？ 50
9樓：匿名使用者
1、首先第一步若節點右左子樹，則左鏈域lchild指示其左孩子（ltag=0）,否則，令左鏈域指示其前驅（ltag=1）。若結點有右子樹，則右鏈域rchild指示其右孩子（rtag=0）,否則，令右鏈域指示其後繼（rtag=1）。
3、最後幾是結點p的左指標域為空，則將其標誌位置為1，並使p->lchild指向中序前驅結點pre（即左線索化）；結點pre的右指標域為空，則將其標誌位置為1，並使pre->rchild指向中序後繼結點p（即右線索化）；將pre指向剛剛訪問過的結點p（即pre=p），線索化p的右子樹。
10樓：
深度優先生成樹 唯一嗎
如果給一圖，從一定點出發，那麼深度優先生成樹的畫法唯一嗎？也就是這個生成樹有左右之分嗎
這個不一定唯一，多數時候不唯一，如果某個頂點有多個未訪問的鄰接點，此時選擇不一樣的下一個點，結果都不一樣
但是對於深度優先的程式而言，因為已經限定了儲存結構和演算法步驟，此時結果才唯一
從網路拓撲中選取一個節點為根節點，產生一個生成樹是不是可以用深度優先搜尋？
11樓：煙波草廬
可以，但時間一般不夠（1s！！）
ps你指程式設計？
圖的深度優先搜尋類似於樹的什麼遍歷方法？？前序的話不是類似廣度的的麼？如果不是
12樓：匿名使用者
深度優先類似於樹的先根（或者先序）便利，廣度優先類似於樹的層次序遍歷