-
Notifications
You must be signed in to change notification settings - Fork 0
实现《算法导论》中,与图相关的算法
License
mnmlyn/Graph
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
将会对图相关的基本算法进行实现,参考《算法导论》。
首先,第22章-基本的图算法。
采用邻接链表来表示图,节点用正的整形数来标识,每个节点有属性color表示图搜索的状态,有属性d和属性
pi等。因此,邻接链表的结构为,首先每个节点为一个结构体VNode,存储各种节点属性,且有一个指针指向当前节
点指向的邻接节点的链表。链表节点又是另外一种结构体LNode。
广度优先搜索。
借助一个队列,来对图进行广度优先搜索。参考22.2节。
BFS之后,pi属性记录了节点的前驱,得到一棵广度优先树。BFS之后每个节点v记录的属性d,为从s到v的最短
路径。借助pi属性,输出节点s到节点v的最短路径上的每个节点。
深度优先搜索。
使用递归方式来进行DFS。辅助递归函数,首先访问当前节点u,然后选择一个相邻的未被访问(白色)节点v进
行递归,递归调用结束后,再选择u其余的白色节点,直到所有节点都不为白色。将当前节点u涂为黑色,结束辅助递
归函数。DFS对所有仍为白色的节点,调用辅助递归函数。
DFS算法中,加入time,来表示访问的先后顺序,每个节点的属性d表示第一次访问时间,属性f表示完成所有相
邻节点访问的时间。About
实现《算法导论》中,与图相关的算法
Resources
License
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published