Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3472268
  • 博文数量: 1450
  • 博客积分: 11163
  • 博客等级: 上将
  • 技术积分: 11101
  • 用 户 组: 普通用户
  • 注册时间: 2005-07-25 14:40
文章分类

全部博文(1450)

文章存档

2017年(5)

2014年(2)

2013年(3)

2012年(35)

2011年(39)

2010年(88)

2009年(395)

2008年(382)

2007年(241)

2006年(246)

2005年(14)

分类: C/C++

2006-04-28 17:53:59

 1.  什么是有向图
 2.  什么是无向图
 3.  图的顶点数N与图的片数E之间的关系
       若G是无向图,则0≤e≤n(n-1)/2
      
若G是有向图,则0≤e≤n(n-1)
 4.  顶点的度,什么是出度,什么是入度?
 5.  什么是路径?(包括有向图的路径和无向图的路径)
 6.  什么是简单路么
 7.  什么是简单回路或简单环?
 8.  有根图和图的根
 9.  连通图和连通分号。强连通图和强连通分量。
 10. 什么是网络?
 11.
图的存储结构有两种:邻接矩阵和邻接表
 12. 邻接表分为有向邻接表和无向邻接表,其中有向邻接表又分为正向邻接反向邻接
 13.
图的遍历:深度优先和广度优先。其中深度优先使用堆栈的方式进行遍历,而广度优先使用队列进行遍历。
 14. 图能够解决的问题有几下几种:

    一、生成树和最小生成树(普里姆(Prim)算法克鲁斯卡尔(Kruskal)算法
         普里姆(Prim)算法
         
T=(U,TE)是存放MST的集合。
         ①T的初值是({r},¢)
           即最小生成树初始时只有一个红点r,没有红边。
         ②T经过n-1次如下步骤操作,最后得到一棵含n个顶点,n-1条边的
            最小生成树(若蓝点与多个红点有连接,则取权值小的边作紫边
            1.选择紫边集中一条轻边并扩充进T
           2.将轻边连接的蓝点改红点
           3.将轻边改红边
            4.修改紫边集

        
克鲁斯卡尔(Kruskal)算法
        
算法思想
        ①T的初始状态
          只有n个顶点而无边的森林T=(V,¢ )
        ②按边长递增的顺序选择E中的n-1安全边(u,v)并加入T,生成MST

         注意:

         安全边指两个端点分别是森林T里两棵树中的顶点的边。加入安全边,可将森林          中的两棵树连接成一棵更大的树
         因为每一次添加到T中的边均是当前权值最小的安全边,MST性质也能保证最终          的T是一棵最小生成树。

    二、最短路径

        迪杰斯特拉(Dijkstra)算法求单源最短路径
   
       
设S为最短距离已确定的顶点集(看作红点集),V-S是最短距离尚未确定的顶点 集(看作蓝点集)。
        ①初始化
         初始化时,只有源点s的最短距离是已知的(SD(s)=0),故红点集S={s},蓝 点集为空。
        ②重复以下工作,按路径长度递增次序产生各顶点最短路径
         在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集,以保证算法按路径长度递增的次序产生各顶点的最短路径。

         当蓝点集中仅剩下最短距离为∞的蓝点,或者所有蓝点已扩充到红点集时,s到所有顶点的最短路径就求出来了。

       注意:
        ①若从源点到蓝点的路径不存在,则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
        ②从源点s到终点v的最短路径简称为v的最短路径;s到v的最短路径长度简称为v的最短距离,并记为SD(v)。

     三、拓扑排序
       
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若 ∈E(G),则u在线性序列中出现在v之前。
     通常,这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列,简称拓扑序列

    无前趋的顶点优先的拓扑排序方法

    该方法的每一步总是输出当前无前趋(即人度为零)的顶点,其抽象算法可描述为:
    NonPreFirstTopSort(G){//优先输出无前趋的顶点
      while(G中有人度为0的顶点)do{
       从G中选择一个人度为0的顶点v且输出之;
       从G中删去v及其所有出边;
       }
      if(输出的顶点数目<|V(G)|)
        //若此条件不成立,则表示所有顶点均已输出,排序成功。
        Error("G中存在有向环,排序失败!");
     }

     无后继的顶点优先拓扑排序方法
    该方法得到的是一个逆序的拓扑,可以通过堆栈来实现拓扑排序

   
利用深度优先遍历对DAG拓扑排序
   
当从某顶点v出发的DFS搜索完成时,v的所有后继必定均已被访问过(想像它们均已被删除),此时的v相当于是无后继的顶点,因此在DFS算法返回之前输出顶点v即可得到 DAG的逆拓扑序列。


阅读(1100) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~