1、已知有向圖g=(v,e),其中v=,e=
寫出g的拓撲排序的結果。
g拓撲排序的結果是:v1、v2、v4、v3、v5、v6、v7
2、 連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊,最小生成樹是邊上權值之和最小的生成樹。故可按權值從大到小對邊進行排序,然後從大到小將邊刪除。每刪除一條當前權值最大的邊後,就去測試圖是否仍連通,若不再連通,則將該邊恢復。
若仍連通,繼續向下刪;直到剩n-1條邊為止。
void spntree (adjlist g)
//用「破圈法」求解帶權連通無向圖的一棵最小代價生成樹。
node; //設頂點資訊就是頂點編號,權是整型數
node edge;
scanf( "%d%d",&e,&n) ; //輸入邊數和頂點數。
for (i=1;i<=e;i輸入e條邊:頂點,權值。
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i<=e;i++) //按邊上的權值大小,對邊進行逆序排序。
//for
k=1; eg=e;
while (eg>=n破圈,直到邊數e=n-1.
if (connect(k)) //刪除第k條邊若仍連通。
edge[k].w=0; eg--; }//測試下一條邊edge[k],權值置0表示該邊被刪除
k++; //下條邊
while
}//演算法結束。
connect()是測試圖是否連通的函式,可用圖的遍歷實現,
3、兩棵空二叉樹或僅有根結點的二叉樹相似;對非空二叉樹,可判左右子樹是否相似,採用遞迴演算法。
int similar(bitree p,q) //判斷二叉樹p和q是否相似
//結束similar
4、4、 void linklist_reverse(linklist &l)
//鍊錶的就地逆置;為簡化演算法,假設表長大於2
q->next=p;s->next=q;l->next=s;
}//linklist_reverse
2023年河北省資料總結加強
1 證明由二叉樹的中序序列和後序序列,也可以唯一確定一棵二叉樹。29.試找出滿足下列條件的二叉樹 1 先序序列與後序序列相同 2 中序序列與後序序列相同 3 先序序列與中序序列相同 4 中序序列與層次遍歷序列相同 2 證明由二叉樹的中序序列和後序序列,也可以唯一確定一棵二叉樹。29.試找出滿足下列條...
2023年河北省資料總結入門
1 二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上,層次遍歷序列中的每個結點都是 區域性根 確定根後,到二叉樹的中序序列中,查到該結點,該結點將二叉樹分為 左根右 三部分。若左 右子樹均有,則層次序列根結點的後面應是左右子樹的根 若中序序列中只有左子樹或只有右子樹,則在層次序列的根結點後也只有...
2023年河北省資料總結基礎
1 二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上,層次遍歷序列中的每個結點都是 區域性根 確定根後,到二叉樹的中序序列中,查到該結點,該結點將二叉樹分為 左根右 三部分。若左 右子樹均有,則層次序列根結點的後面應是左右子樹的根 若中序序列中只有左子樹或只有右子樹,則在層次序列的根結點後也只有...