[筆記] The CutHill-McKee Algorithm

posted in: algorithm | 0

http://ciprian-zavoianu.blogspot.tw/…/project-bandwidth-red…

這篇講的好清楚,總結一下:
1.把所有的node丟進去做BFS,看那個在最前面都可以。
2.把expanded node丟進fringeList(使用priority queue,根據degree排序),繼續BFS未完成的流程。
3.把expanded的node丟進closed array,若這個array的size等於所有的node就完成了,否則則繼續step 1中丟進來的起始node重開BFS。
4.把closed array做reverse完再用這個label去重建graph就行啦。

 

boost的graph內有相關的實作:

http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/sparse_matrix_ordering.html

dorgon

dorgon

職業:LV3遊戲軟體工程師 為了追尋小時候玩遊戲的感動,而一頭栽入遊戲業界。 本來以撰寫遊戲劇本為主要志向,但回過神來才發現已經踏入程序猿的不歸路。 專長為client端跨平台遊戲開發架構與自動建置流程,主要使用引擎為cocos2d-x與UnrealEngine4。

More Posts - Website

Follow Me:
FacebookLinkedIn

有什麼想法嗎?請發表你的看法