→ exilelast: 依據維基上說的2edge-connect-graph 就是undirect grap 01/03 19:47
→ exilelast: 就是undirect graph的strongly conect component 喔 01/03 19:48
推 jimmylin1024: 是非第八題是false 紅黑數中red node和black node的 12/12 10:10
→ jimmylin1024: 比例最大可以到2 12/12 10:10
是非
1. B
max height of AVL tree: 1.44xlogn
max height of RB tree: 2 logn
2. B
3. A
4. B
5. B (我覺得是O(n)...)
6. A
7. A
8. A
9. A
10.B (O(1) time)
單選
1. C
2. B
3. E (12354)
4. E (0 double rotation, 2 left rotations)
非選
三 google一下應該有很多
array 可以randome access; linked list 只能sequential access
之類的等等等
四 自己有寫一個 可是不知道對不對 請大神補充
五 題目問的怪怪的 strongly connected component只有directed graph 才有
如果是undirected graph 求 connected component
int component=0;
for i=0 to n-1 // iterate throught all vertices in the graph
{ if vertex[i]==FALSE // if the vertex is not visited
dfs(G, i);
int j;
printf("%d", i);
visitied[i]=1;
for(j=0; j<n; j++){
if(visited[j]==0&&G[i][j]==1)
dfs(G, j);
}
component+=1;
}
不太確定 請大神幫忙debug!
如果是directed graph 求strongly connected component
---->google Kosaraju's algorithm
看不懂QQ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.125.97.119
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483441872.A.0C8.html
※ 編輯: tzutengweng (59.125.97.119), 01/03/2017 19:11:53