① 假設圖G採用鄰接表存儲，設計一個演算法，判斷圖G是否連通。若連通則返回1；否則返回0.
bool Connect(AlGraph*G)
{int i;
bool flag=true;
for(i=0;i<G->n;i++)
visited[i]=0;
DFS(G,0);
for(i=0;i<G->n;i++)
if(visited[i]==0)
{flag=false;
break;}
return flag;
}
② 無向圖採用鄰接表存儲結構,編寫演算法輸出圖中各連通分量的節點序列
//按廣度優先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數組visited.僅適用於鄰接表結構
void BFSTraverse1(ALGraph G,void(* Visit)(char *))
{
int v,u;
ArcNode * p;//p指向表結點
LinkQueue Q;//鏈隊列類型
for (v=0; v<G.vexnum; ++v)
{
visited[v] = FALSE;//置初值為未被訪問
}
InitQueue(&Q);//初始化輔助隊列Q
for (v=0; v<G.vexnum; ++v)//如果是連通圖，只v=0就遍歷全圖
{
if (! visited[v])//v尚未被訪問
{
visited[v] = TRUE;//設v為已被訪問
Visit(G.vertices[v].data);//訪問v
EnQueue(&Q,v);//v入隊
while (! QueueEmpty(Q))//隊列不空
{
DeQueue(&Q,&u);//隊頭元素出隊並置為u
for (p=G.vertices[u].firstarc; p; p=p->next)//p依次指向u的鄰接頂點
{
if (! visited[p->data.adjvex])//u的鄰接頂點尚未被訪問
{
visited[p->data.adjvex] = TRUE;//該鄰接頂點設為已被訪問
Visit(G.vertices[p->data.adjvex].data);//訪問該鄰接頂點
EnQueue(&Q,p->data.adjvex);//入隊該鄰接頂點序號
}
}
}//while
}//if
}//for(v=......)
printf("\n");
}
③ 具有n個頂點、e條邊的圖採用鄰接表存儲結構，進行深度優先遍歷和廣度優先遍歷運算的時間復雜度均為
答案是o（n+e） 但是鄰接表裡面不是每個邊被儲存兩次嗎，為什麼不是n+2e呢？
在大O表示法中O（n+2e)通常應表示為O（n+e）
④ 無向圖G.，有n個頂點，m條邊，如何採用鄰接表存儲該圖主要是想知道演算法~用c語言
無向圖就是不分方向的圖
連接表的橫列有N項，縱列也是N項
形成的N*N項每項都被稱為邊結點
每項都有縱橫兩個坐標，例如點（N,N-1），表示的就是從第N點向第N-1點有無路徑。
由於有E條邊，自然有E條路徑，但是由於無向，=雙向，所以要乘以二
⑤ 假設圖採用鄰接表存儲，編寫一個函數利用深度優先搜索方法求出無向圖中通過給定點v的簡單迴路。
你也是學數據結構的？？？我學的不好，不會。呵呵。
⑥ 在圖採用鄰接表存儲時，求最小生成樹的 Prim 演算法的時間復雜度為
鄰接表儲存時，是B。鄰接矩陣儲存就是C了。
⑦ 採用鄰接表存儲的圖的深度優先遍歷演算法類似於二叉樹的先序遍歷，為什麼是先序呢
這是因為圖的深度優先遍歷演算法先訪問所在結點，再訪問它的鄰接點。與二叉樹的先序遍歷先訪問子樹的根結點，再訪問它的孩子結點（鄰接點）類似。圖的廣度優先遍歷演算法類似於二叉樹的按層次遍歷。
先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。
首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。
例如，下圖所示二叉樹的遍歷結果是：ABDECF。
(7)假設圖採用鄰接表存儲擴展閱讀：
遍歷種類：
一、NLR：前序遍歷(Preorder Traversal 亦稱（先序遍歷）），訪問根結點的操作發生在遍歷其左右子樹之前。
二、LNR：中序遍歷(Inorder Traversal)，訪問根結點的操作發生在遍歷其左右子樹之中（間）。
三、LRN：後序遍歷(Postorder Traversal)，訪問根結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為 先根遍歷、中根遍歷和後根遍歷。
⑧ 數據結構問題
1、假設圖採用鄰接表存儲，編寫一個函數利用深度優先搜索方法求出無向圖中通過給定點v的簡單迴路。
2、若二叉樹中各結點的值均不相同，則由二叉樹的前序序列和中序序列，或由其後序序列和中序序列均能惟一地確定一棵二叉樹，但由前序序列和後序序列卻不一定能惟一地確定一棵二叉樹。
（1）已知一棵二叉樹的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF，請畫出此二叉樹。
（2）已知一棵二叉樹的中序序列和後序序列分別為BDCEAFHG和DECBHGFA，請畫出此二叉樹。
（3）已知兩棵二叉樹的前序序列和後序序列均為AB和BA，請畫出這兩棵不同的二叉樹
3、假設二叉樹包含的結點數據為1，3，7，2，12。
（1）畫出兩棵高度最大的二叉樹；
（2）畫出兩棵完全二叉樹，要求每個雙親結點的值大於其他孩子結點的值。
4、一個深度為h的滿k叉樹有如下性質：第h層上的結點都是葉子結點，其餘各層上每個結點都有k棵非空子樹。如果按層次順序（同層自左至右）從1開始對全部結點編號，問：
（1）各層的結點數目是多少？
（2）編號為i結點的雙親結點（若存在）的編號是多少？
（3）編號為i的結點的第j個孩子結點（若存在）的編號是多少？
（4）編號為i的結點有右兄弟的條件是什麼？其右兄弟的編號是多少？
5、
假設在樹中，結點x是結點y的雙親時，用（x，y）來表示樹邊。已知一棵樹邊的集合為：{（i，m），（i，n），（e，i），（b，e），（b，d），（a，b），（g，j），（g，k），（c，g），（c，f），（h，l），（c，h），（a，c）}
用樹形表示法畫出此樹，並回答下列問題：
（1）哪個是根結點：（2）哪些是葉結點？（3）哪個是g的雙親？
（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孫？
（7）哪些是e的兄弟？哪些是f的兄弟？（8）結點b和n的層次各是多少？
（9）樹的深度是多少？（10）以結點c為根的子樹的深度是多少？
（11）樹的度數是多少？
6、編寫下列演算法（假定下面所用的串均採用順序存儲方式，參數ch、ch1和ch2均為字元型）：
將串r中所有其值為ch1的字元換成ch2的字元。
將串r中所有字元按照相反的次序仍存放在r中。
從串r中刪除其值等於ch的所有字元。
從串r1中第index個字元起求出首次與字元r2相同的子串的起始位置。
從串r中刪除所有與串r3相同的子串（允許調用第（4）小題的函數和第（3）小題的刪除子串的函數）。
7、設二維數組A5*6的每個元素佔4個位元組，已知Loc（a00）=1000，A共佔多少個位元組？A的終端結點a45的起始地址為多少？按行和按列優先存儲時，a25的起始地址分別為多少？
8、假設稀疏矩陣A採用三元組表示，編寫一個函數計算其轉置矩陣B，要求B也採用三元組表示
⑨ 假設G採用鄰接表存儲、試設計一個演算法、求不帶權無向連通圖G中距離定點V的最遠的
圖G由兩個集合V和E組成,記為G=(V,E),
其中V是圖中頂點的有限集合，V={v1,v2,…,vn}，E是連接V中兩個頂點的邊的有限集合,邊是頂點的有序對或無序對，記作<vi,vj>或（vi, vj）。
如果代表邊的頂點對是無序的,則稱G為無向圖,無向圖中代表邊的無序頂點對通常用圓括弧括起來。
如果表示邊的頂點對是有序的,則稱G為有向圖,在有向圖中代表邊的頂點對通常用尖括弧括起來 。
⑩ 數據結構 ：假設圖G採用鄰接表存儲,試設計一個演算法,求不帶權無向連通圖G中距離頂點v的最遠的頂點
(1)每個點關聯一個量d，讓所有定點的d值都為0
(2)對v進行廣度優先搜索
(3)bfs後d值最大的點就是離v最遠的點。