(1)入度为0的点入栈 (2)销毁节点,和与给节点相连的边 (3)重复上过程,直到没有元素。 若栈为空时,节点没有完全取出,则证明图中有环 对上图进行拓扑排序的结果: 2->8->0->3->7->1->5->6->9->4->11->10->12 //拓扑排序   void Graph::topologicalSort()   {      &…

2015年3月14日 0条评论 0点热度 阅读全文

遍历     图的遍历是指从图中的某一顶点出发,按照一定的策略访问图中的每一个顶点。当然,每个顶点有且只能被访问一次。     在图的遍历中,深度优先和广度优先是最常使用的两种遍历方式。这两种遍历方式对无向图和有向图都是适用的,并且都是从指定的顶点开始遍历的。先看下两种遍历方式的遍历规则: (1)深度优先 1)定义     深度优先遍历也叫深度优先搜索(Depth First Search)。它的遍历规则:不断地沿着顶点的深度方向遍历。顶点的深度方向是指它…

2015年3月14日 0条评论 0点热度 阅读全文

(q)根据哈弗曼树的定义,一棵二叉树要使其WPL值最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点 越远离根结点。 哈弗曼依据这一特点提出了一种构造最优二叉树的方法,其基本思想如下:   下面演示了用Huffman算法构造一棵Huffman树的过程: (2)例题: 假设一个文本文件TFile中只包含7个字符{A,B,C,D,E,F,G},这7个字符在文本中出现的次数为{5,24,7,17,34,5,13} 利用哈夫曼树可以为文件TFile构造出符合前缀编码要求的不等长编码   具…

2015年3月14日 0条评论 0点热度 阅读全文