一.序 和树的遍历类似,我们希望从图中的某一个顶点出发访问图中其余顶点,保证每个顶点只被访问一次,这一过程叫做图的遍历。图的遍历算法是求解图的连通性问题(最小生成树),拓扑排序,求关键路径的基础。 而为了保证同一个顶点不被访问多次,在遍历图的的过程中,必须记下访问过的顶点。为此,需要设立一个辅助数组visited[0..n-1],初始值设置为0或假,这样其不为0或者为真时,表示此顶点已经被访问过。 通常有两条遍历图的路径:深度优先搜索和广度优先搜索。他们对有向图和无向图都适用。 二.简单介绍两种算法 深度优先搜索算…

2017年2月28日 0条评论 16点热度 阅读全文

一.有向无环图 1.Directed Acircline Graph,即一个无环的有向图,它是描述含有公共子式表达式的有效工具,可以实现共享相同子式,节省存储空间。 例如:对于下面的表达式分别用二叉树描述和有向无环图描述 2.有向图无环的判断 二.拓扑排序与最短路径的引入 一个工程,往往会分成几个阶段,某些子工程的开始必须建立在一些子工程已经完成的基础之上,这影响着工程是否能够顺利进行。对整个工程和系统,人们最关心两个问题:1.工程是否能顺利进行。2.估算整个工程完成的最短时间。这对应于有向图,分别是拓扑排序和求最…

2017年2月26日 0条评论 8点热度 阅读全文