Skip to content
/ Graph Public

实现《算法导论》中,与图相关的算法

License

Notifications You must be signed in to change notification settings

mnmlyn/Graph

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

No packages published