精华内容
下载资源
问答
  • 概述图可以根据是否「向」和「带权」分成以下四种:无向图 (无向不带权)向图 (向不带权)加权无向图(无向带权)加权向图(向带权)无向图无向图定义:由一组顶点和一组能够将两个顶点链接在一起的边组成。...

    概述

    图可以根据是否「有向」「带权」分成以下四种:

    • 无向图    (无向不带权)
    • 有向图    (有向不带权)
    • 加权无向图(无向带权)
    • 加权有向图(有向带权)

    无向图

    无向图定义:由一组顶点和一组能够将两个顶点链接在一起的边组成。

    特殊情况下的图:自环,平行边。

    自环:就是自己连自己。

    平行边:同一对顶点上有多条边相连。例如就像家和学校两个点之间存在很多条路可以选择,而路与路之间称为平行边。

    63dbd36b35838052eac87ee7b1b90090.png

    术语

    图论方面存在很多相关术语,为了便于后续的叙述,先将这些术语罗列出来。

    • 相邻:两个顶点和同一条边相连称为相邻。同时也称这条边「依附」与这两个顶点。
    • 顶点的度:与该顶点相邻边的个数。
    • 子图:一幅图中所有边的子集以及这些边相关的点所组成的图。
    • 路径:边顺序连接起来的一系列的顶点。
    • 简单路径:没有重复顶点的路径。
    • 环:至少含有一条起点和终点相同的路径。
    • 简单环:不含有重复顶点和边的环。
    • 连通图:任意一个顶点都存在一条路径到达另一个任意顶点。
    • 极大连通子图:非连通图是由若干个连通子图组成,这些连通子图称为极大连通子图。
    • 连通分量:极大连通子图的个数称为非连通图的连通分量。
    • 树:无环「连通图」
    • 森林:互不相连的「树」组成「森林」
    • 生成树:「连通图」「子图」,含有图中的所有「顶点」并且还得是一棵「树」
    • 生成森林:「生成树」的集合,也就是该图的所有「连通子图」「生成树」的集合。
    • 稀疏图:被连接的顶点对很少,也就是边比较少的图。
    • 稠密图:大部分的顶点对都有边相连,只有少部分的顶点对之间没有边连接。
    • 二分图:顶点集可以分割成两个互不相交的子集。

    无向图的表示方法

    够将无向图需要满足两个条件:

    1. 为各种类型的图预留足够的空间。
    2. 处理时速度要快。

    存在三种类型的实现方法:

    1. 邻接矩阵,二维的布尔矩阵,两点 i 和 j 之间存在边则对应的下标 [i][j] 中的值为 true ,反之为 false 。当图很大时所需的空间也很大,无法满足第一个条件。

    2. 边的数组,实现一个 Edge 类,里面设置两个 int 实例变量。这种实现虽然简洁,但是处理慢,例如如果想要得到某个结点的所有边需要遍历全部结点。

    3. 邻接表数组,以顶点为索引,其中的元素都是与该顶点相邻的结点。如图:

    245699982f2b9e5259469d2f62d33182.png

    邻接表的数据结构

    在非稠密图种就是采用邻接表的数据结构实现的。每个顶点相邻顶点的元素都保存在该顶点对应的元素所指向的一张链表中。

    对于 V 个顶点 E 条边的图,使用的空间为 , 添加一条边所消耗的时间为常数。处理相邻顶点所需的时间也为常数。

    深度优先搜索

    搜索的本质是遍历全部节点,深搜就是一种遍历方式,如图:

    a0b0bb3e1e9cc121fb58a04875b08afd.png

    特点是每次都遍历到「尽头」,也就是走不下去的时候回头再遍历相关节点。

    广度优先搜索

    广搜和深搜相反,优先遍历相关节点,相关节点都遍历完成后再去遍历下一层的节点指导走到尽头。

    eca2b6c7eaa4c40c772c2728dc1118a5.png

    有向图

    有向图的边是单向的,每条边连接的两个顶点都是一个有序对。

    「背景:」 有向图的背景有很多,简单枚举几个,有一个大致的体会。

    1. 食物链物种的间的不是关系是单向的。
    2. 网页之间的超链接,往往有去无回。
    3. 程序间的模块间的外部引用。

    有向图有顶点和有方向的边组成。

    有向图中的「度」分为「出度」「入度」两种类型。出度为该「顶点指出」的边的总数,入度则为「指向该顶点」的边的总数。

    在一条有向边中,第一个顶点称为「头」,而第二个顶点则称为「尾」

    多点可达性可以应用于「垃圾回收」,顶点代表对象,而顶点之间的边代表对象与对象之间的「引用」

    最小生成树

    生成树表示含有所有顶点的无环连通子图。

    而最小生成树表示再生成树的基础上权重最小。

    最小生成树只考虑连通图。

    边的权重不一定表示距离。

    原理

    • 用一条边连接树中任意两个顶点都会产生一个新的环。
    • 从树中删去一条边将会得到两颗独立的树。

    7cdf895c25cf67b09494aa68221f02da.png

    切分定理:指将图中「所有顶点」分为「两个非空且不重叠」的两个集合,「横切边」是一条连接两个属于不同集合的顶点的边。

    b07f24fa92a1f1cb17abe86616e2d1b7.png

    从横切边中找权重最小的边,这条边一定属于最小生成树中。依次不断寻找权重最小的横切边即可。

    Prim 算法

    N 个顶点的图中,需要添加 N-1 条边才能构成最小生成树。

    对于 prim 算法而言,每次都需要选择一条最小的横切边加入树中。

    prim 算法也分为即使实现和延时实现,前者表示一条边的两个顶点都存在于树中的话将会立即删除,反之则不删除等待后续检查边的有效性。

    496d82f936f55c5be142dc53be2b521d.png

    延时实现的遍历顺序为:

    bb111e94e637f96e3f6c5b164e069d40.png

    即时实现的遍历顺序为:

    299772ac0f40e1138b222dd12550c732.png

    二者的区别在于即使实现会将某些边从优先队列中删去,这些边是新加入树中顶点与其他已经在书中顶点的所有边。

    Kruskal 算法

    这个算法比较简单,将所有的边按照权重排序,依次放入图中即可,注意要将不满足条件的边剔除,例如闭环。

    6338e81a88c88e290b69faeb9cdae8ee.png

    最短路径

    最短路径的现实背景就是两地之间存在多条路线,选择一条长度最短的路径。

    单点最短路径:在加权有向图中,从顶点 s 到顶点 t 的最短路径是所有从 s 到 t 的路径中的权重最小者。

    最短路径性质

    最短路径的定义:

    • 路径是有向的。
    • 权重不等价于距离。
    • 并不是所有的顶点都是可达的。
    • 负权重会使问题更复杂。
    • 最短路径一般都是简单的。(忽略环)
    • 最短路径不一定是唯一的。
    • 可能存在平行边和自环。

    注意,最短路径树和最小生成树不同,最短路径树是指从指定顶点出发,计算该顶点到达其他所有顶点的最短路径所构成的树。

    Dijkstra

    Dijkstra 用于处理权重非负的最短路径问题。

    Prim 算法每次拿到的都是权值最小的横切边,而 Dijkstra 算法选择横切边是按照距离起点最近的距离来选择,也就是哪个顶点距离起点最近就选择该顶点相关的横切边。

    展开全文
  • 有向无的 最长 首先阐明一点 最长dijkstra 是不能做 (当然我是不会做的,不过我貌似看到过网上的dalao有用dijstra做的)为什么dijstra难做呢(或者说不大好做呢) 这是因为,Dijkstra算法的大致思想是...

    洛谷P1807 最长路_NOI导刊2010提高(07)

    图论

    求有向无环图的 最长路

     

    首先阐明一点
    最长路dijkstra 是不能做
    (当然我是不会做的,不过我貌似看到过网上的dalao有用dijstra做的)
    为什么dijstra难做呢(或者说不大好做呢)
    这是因为,Dijkstra算法的大致思想是每次选择距离源点最近的结点加入,
    然后更新其它结点到源点的距离,直到所有点都被加入为止。当每次选择最短
    的路改为每次选择最长路的时候,出现了一个问题,那就是不能保证现在加入
    的结点以后是否会被更新而使得到源点的距离变得更长,而这个点一旦被选中
    将不再会被更新。例如这次加入结点u,最长路为10,下次有可能加入一个结
    点v,使得u通过v到源点的距离大于10,但由于u在之前已经被加入到集合中,
    无法再更新,导致结果是不正确的。
    如果取反用dijkstra求最短路径呢,记住,dijkstra不能计算有负边的情况。。。


    1、一种做法是拓扑排序之后再动态规划
    2、还有一种做法就是 直接SPFA求最长路,
    但是需要注意点不出队列,这样防止出现正环之后死循环

    总结一下求最长路径的方法
    首先对于最长路径可以分类
    1、可以重复走
    这个可以用SPFA 或者 floyd 来求 方法类似
    2、不能重复走
    这是个NP-hard 直接dfs暴搜
    因为每个边只能走一次,你用SPFA就得用f 标记,
    然后对于不同路径f数组还不一样,所以SPFA不可做 (也许可做,但我不会QwQ)
    但是如果再加上一些特殊的条件
    比如说是有向无环图
    这个就可做了
    1、一种方法拓扑排序一下 跑动态规划
    2、或者直接记忆化搜索
    3、或者直接SPFA 或者 floyd

    SPFA 其实很好改 松弛的时候条件变一下,然后dist初始值变一下就行了


    另一个人的博客
    1。 肯定不能用dijkstra算法,这是因为,Dijkstra算法的大致思想是每次选择距离源点最近的结点加入,然后更新其它结点到源点的距离,直到所有点都被加入为止。当每次选择最短的路改为每次选择最长路的时候,出现了一个问题,那就是不能保证现在加入的结点以后是否会被更新而使得到源点的距离变得更长,而这个点一旦被选中将不再会被更新。例如这次加入结点u,最长路为10,下次有可能加入一个结点v,使得u通过v到源点的距离大于10,但由于u在之前已经被加入到集合中,无法再更新,导致结果是不正确的。
    如果取反用dijkstra求最短路径呢,记住,dijkstra不能计算有负边的情况。。。

    2.
    可以用 Bellman-Ford 算法求最长路径,只要把图中的边权改为原来的相反数即可。也可以用Floyd-Warshall 算法求每对节点之间的最长路经,因为最长路径也满足最优子结构性质,而Floyd算法的实质就是动态规划。但是,如果图中含有回路,Floyd算法并不能判断出其中含有回路,且会求出一个错误的解;而Bellman-Ford算法则可以判断出图中是否含有回路。

    3. 如果是有向无环图,先拓扑排序,再用动态规划求解。

     

     1 #include <cstdio>
     2 #include <cmath>
     3 #include <cstdlib>
     4 #include <cstring>
     5 #include <string>
     6 #include <algorithm>
     7 #include <iostream>
     8 #include <iomanip>
     9 #include <queue>
    10 using namespace std ; 
    11 
    12 const int maxn = 1511,maxm = 50011 ; 
    13 struct node{
    14     int to,val,pre ; 
    15 }e[maxm];
    16 int n,m,x,y,val,cnt ; 
    17 int dist[maxn],vis[maxn],head[maxn] ; 
    18 queue <int> Q ; 
    19 
    20 inline void add(int x,int y,int v) 
    21 {
    22     e[++cnt] = (node){ y,v,head[x] } ; 
    23     head[x] = cnt ; 
    24 }
    25 
    26 inline void SPFA(int s,int t) 
    27 {
    28     int u,v ; 
    29     for(int i=1;i<=n;i++) 
    30         dist[ i ] = -1 ; 
    31     dist[ 1 ] = 0 ; 
    32     vis[ 1 ] = 1 ; 
    33     Q.push(1) ; 
    34     while(!Q.empty())  
    35     {
    36         u = Q.front() ; 
    37         Q.pop() ; 
    38         //
    39         for(int i=head[u];i;i=e[i].pre) 
    40         {
    41             v = e[ i ].to ; 
    42             if(dist[ u ]+e[ i ].val > dist[ v ]) 
    43             {
    44                 dist[ v ] = dist[ u ] + e[ i ].val ; 
    45                 Q.push(v) ; 
    46                 //if(!vis[ v ]) Q.push(v),vis[ v ] = 1 ; 
    47             }
    48         }
    49         //vis[ u ] = 0 ; 
    50     }
    51     printf("%d\n",dist[ n ]) ; 
    52 }
    53 
    54 int main() 
    55 {
    56     scanf("%d%d",&n,&m) ; 
    57     for(int i=1;i<=m;i++) 
    58         scanf("%d%d%d",&x,&y,&val),add(x,y,val) ; 
    59     if(n==1) 
    60     {
    61         printf("0\n") ; 
    62         return 0 ; 
    63     }
    64     SPFA(1,n) ; 
    65     return 0 ;  
    66 }

     

    转载于:https://www.cnblogs.com/third2333/p/7026076.html

    展开全文
  • 无向图 (无向不带权) 向图 (向不带权) 加权无向图(无向带权) 加权向图(向带权) 无向图 无向图定义: 由一组顶点和一组能够将两个顶点链接在一起的边组成。 特殊情况下的图: 自环,平行边。 自环...
    
    

    第四章:图

    概述

    图可以根据是否有向带权分成以下四种:

    • 无向图 (无向不带权)
    • 有向图 (有向不带权)
    • 加权无向图(无向带权)
    • 加权有向图(有向带权)

    无向图

    无向图定义: 由一组顶点和一组能够将两个顶点链接在一起的边组成。

    特殊情况下的图: 自环,平行边。

    自环:就是自己连自己。

    平行边:同一对顶点上有多条边相连。例如就像家和学校两个点之间存在很多条路可以选择,而路与路之间称为平行边。

    术语

    图论方面存在很多相关术语,为了便于后续的叙述,先将这些术语罗列出来。

    • 相邻:两个顶点和同一条边相连称为相邻。同时也称这条边依附与这两个顶点。
    • 顶点的度:与该顶点相邻边的个数。
    • 子图:一幅图中所有边的子集以及这些边相关的点所组成的图。
    • 路径:边顺序连接起来的一系列的顶点。
    • 简单路径:没有重复顶点的路径。
    • 环:至少含有一条起点和终点相同的路径。
    • 简单环:不含有重复顶点和边的环。
    • 连通图:任意一个顶点都存在一条路径到达另一个任意顶点。
    • 极大连通子图:非连通图是由若干个连通子图组成,这些连通子图称为极大连通子图。
    • 连通分量:极大连通子图的个数称为非连通图的连通分量。
    • 树:无环连通图
    • 森林:互不相连的组成森林
    • 生成树:连通图子图,含有图中的所有顶点并且还得是一棵
    • 生成森林:生成树的集合,也就是该图的所有连通子图生成树的集合。
    • 稀疏图:被连接的顶点对很少,也就是边比较少的图。
    • 稠密图:大部分的顶点对都有边相连,只有少部分的顶点对之间没有边连接。
    • 二分图:顶点集可以分割成两个互不相交的子集。

    无向图的表示方法

    构建无向图需要满足两个条件:

    1. 为各种类型的图预留足够的空间。
    2. 处理时速度要快。

    存在三种类型的实现方法:

    1. 邻接矩阵,二维的布尔矩阵,两点 i 和 j 之间存在边则对应的下标 [i][j] 中的值为 true ,反之为 false 。当图很大时所需的空间也很大,无法满足第一个条件。

    2. 边的数组,实现一个 Edge 类,里面设置两个 int 实例变量。这种实现虽然简洁,但是处理慢,例如如果想要得到某个结点的所有边需要遍历全部结点。

    3. 邻接表数组,以顶点为索引,其中的元素都是与该顶点相邻的结点。如图:

    邻接表的数据结构

    在非稠密图中就是采用邻接表的数据结构实现的。每个顶点相邻顶点的元素都保存在该顶点对应的元素所指向的一张链表中。

    对于 V 个顶点 E 条边的图,使用的空间为 V+EV+E , 添加一条边所消耗的时间为常数。处理相邻顶点所需的时间也为常数。

    深度优先搜索

    搜索的本质是遍历全部节点,深搜就是一种遍历方式,如图:

    特点是每次都遍历到尽头,也就是走不下去的时候回头再遍历相关节点。

    广度优先搜索

    广搜和深搜相反,优先遍历相关节点,相关节点都遍历完成后再去遍历下一层的节点指导走到尽头。

    有向图

    有向图的边是单向的,每条边连接的两个顶点都是一个有序对。

    背景: 有向图的背景有很多,简单枚举几个,有一个大致的体会。

    1. 食物链物种的间的不是关系是单向的。
    2. 网页之间的超链接,往往有去无回。
    3. 程序间的模块间的外部引用。

    有向图有顶点和有方向的边组成。

    有向图中的分为出度入度两种类型。出度为该顶点指出的边的总数,入度则为指向该顶点的边的总数。

    在一条有向边中,第一个顶点称为,而第二个顶点则称为

    多点可达性可以应用于垃圾回收,顶点代表对象,而顶点之间的边代表对象与对象之间的引用

    最小生成树

    生成树表示含有所有顶点的无环连通子图。

    而最小生成树表示在生成树的基础上权重最小。

    最小生成树只考虑连通图。

    边的权重不一定表示距离。

    原理

    • 用一条边连接树中任意两个顶点都会产生一个新的环。
    • 从树中删去一条边将会得到两颗独立的树。

    切分定理:指将图中所有顶点分为两个非空且不重叠的两个集合,横切边是一条连接两个属于不同集合的顶点的边。

    从横切边中找权重最小的边,这条边一定属于最小生成树中。依次不断寻找权重最小的横切边即可。

    Prim 算法

    N 个顶点的图中,需要添加 N-1 条边才能构成最小生成树。

    对于 prim 算法而言,每次都需要选择一条最小的横切边加入树中。

    prim 算法也分为即使实现和延时实现,前者表示一条边的两个顶点都存在于树中的话将会立即删除,反之则不删除等待后续检查边的有效性。

    延时实现的遍历顺序为:

    即时实现的遍历顺序为:

    二者的区别在于即使实现会将某些边从优先队列中删去,这些边是新加入树中顶点与其他已经在书中顶点的所有边。

    Kruskal 算法

    这个算法比较简单,将所有的边按照权重排序,依次放入图中即可,注意要将不满足条件的边剔除,例如闭环。

    最短路径

    最短路径的现实背景就是两地之间存在多条路线,选择一条长度最短的路径。

    单点最短路径:在加权有向图中,从顶点 s 到顶点 t 的最短路径是所有从 s 到 t 的路径中的权重最小者。

    最短路径性质

    最短路径的定义:

    • 路径是有向的。
    • 权重不等价于距离。
    • 并不是所有的顶点都是可达的。
    • 负权重会使问题更复杂。
    • 最短路径一般都是简单的。(忽略环)
    • 最短路径不一定是唯一的。
    • 可能存在平行边和自环。

    注意,最短路径树和最小生成树不同,最短路径树是指从指定顶点出发,计算该顶点到达其他所有顶点的最短路径所构成的树。

    Dijkstra

    Dijkstra 用于处理权重非负的最短路径问题。

    Prim 算法每次拿到的都是权值最小的横切边,而 Dijkstra 算法选择横切边是按照距离起点最近的距离来选择,也就是哪个顶点距离起点最近就选择该顶点相关的横切边。

    展开全文
  • 4.1.2 表示无向图的数据类型 4.1.3 深度优先搜索 4.1.4 寻找路径 4.1.5 广度优先搜索 4.1.6 连通分量 4.1.7 符号图 4.1.8 总结 4.2 向图 4.2.1 术语 4.2.2 向图的数据类型 4.2.3 向图中的可达性 ...
  • 4.3.2 加权无向图的数据类型 393 4.3.3 最小生成树的API和测试用例 396 4.3.4 Prim算法 398 4.3.5 Prim算法的即时实现 401 4.3.6 Kruskal算法 404 4.3.7 展望 407 4.4 最短路径 412 4.4.1 最短路径的...
  • 排序算法总结

    2012-10-07 18:50:33
    反复执行这两个步骤,直到所有的顶点都被输出,输出的序列就是这个有向图的拓扑序列。 二、递归归并排序、二归并排序  归并算法的两种方法: 1、使用分治法的递归归并算法

    一、拓扑排序

    拓扑排序的步骤:

              (1)从图中选择一个入度为0的顶点且输出之;

              (2)从图中删掉该顶点及其所有以该顶点为弧尾的弧;

    反复执行这两个步骤,直到所有的顶点都被输出,输出的序列就是这个无环有向图的拓扑序列。

    二、递归归并排序、二路归并排序 

    归并算法的两种方法:

    1、使用分治法的递归归并算法:

    /*递归归并排序
     *将有二个有序数列list[first...mid]和list[mid+1,...last]合并
     *list:待排序数组
     *first:子序列1的下界
     *mid:子序列1的上界
     *last:子序列2的上界
     *temp:临时保存数组
    */
    void Merge(element list[], int first, int mid, int last, element temp[])
    {
        int i = first, j = mid + 1;
        int m = mid,   n = last;
        int k = 0;
        
        while (i <= m && j <= n)
        {
            if (list[i] < list[j])
                temp[k++] = list[i++];
            else
                temp[k++] = list[j++];
        }
        
        while (i <= m)
            temp[k++] = list[i++];
        
        while (j <= n)
            temp[k++] = list[j++];
        
        for (i = 0; i < k; i++)
            list[first + i] = temp[i];
    
        return ;
    }
    /*递归归并排序
     *分治,完成递归归并
     *list:待排序数组
     *first:list下界
     *last:list上界
     *temp:临时保存数组
    */
    void mergesort(element list[], int first, int last, element temp[])
    {
        if (first < last)
        {
            int mid = (first + last) / 2;
            mergesort(list, first, mid, temp);    //左边有序
            mergesort(list, mid + 1, last, temp); //右边有序
            Merge(list, first, mid, last, temp); //再将二个有序数列合并
        }
        return ;
    }
    /*递归归并排序
     *list:待排序数组
     *n:为数组长度
    */
    bool MergeSort(element list[], int n)
    {
        element *p = new element[n];//空间复杂度为O(n)
        if (p == NULL)
            exit(1);
            
        mergesort(list, 0, n - 1, p);
        
        delete[] p;
        return true;
    }

    2、二路归并算法:
    /*归并算法二,二路归并
     *list:待排序数组
     *n:为数组长度
     *temp:临时保存数组
     *k:为有序子数组的长度,一次二路归并排序后有序子序列存于temp数组中
    */
    void Merge2(element list[], int n, element temp[], int k)
    {
        int i, j;
        int m=0;
    
        int low1=0;//第一有序的下界
        int up1, low2, up2;//第一有序的上界,第二有序的下界,第二有序的上界
    
        /*将原始数组中足够分为两组的数据元素二路归并存放到数组temp中*/
        while(low1+k < n-1)
        {
            low2 = low1+k;
            up1  = low2-1;
    
            up2 =(low2+k-1 < n-1) ? low2+k-1:n-1;
    
            for(i=low1, j=low2; i<=up1 && j <=up2; )
            {
                if (list[i] <= list[j])
                    temp[m++] = list[i++];
                else
                    temp[m++] = list[j++];
            }
    
            while (i <= up1)
                temp[m++] = list[i++];
        
            while (j <= up2)
                temp[m++] = list[j++];
    
            low1 = up2+1;
        }
    
        /*将原始数组中只够一组的数据元素顺序存放到数组temp中*/
        i=low1;
        while(i<n)
        {
            temp[m++] = list[i++];
        }
        return;
    }
    /*二路归并排序
     *list:待排序数组
     *n:为数组长度
    */
    bool MergeSort2(element list[], int n)
    {
        element *p = new element[n];//空间复杂度为O(n)
        if (p == NULL)
            exit(1);
    
        int k=1;//二路归并长度从1开始
        int i=0;
    
        while(k<n)
        {
            Merge2(list, n, p, k);//每次归并后保存在p中
            for(i=0; i<n; i++)
                list[i] = p[i];//从p中拷贝到list中
    
            k *=2;//归并长度加倍
        }
        delete[] p;
        return true;
    }

    三、希尔排序 

    /*@希尔排序:分组插入排序
     *@list:待排序数组
     *@n:总排序元素个数
     */
     void shellSort(element list[], int n)//希尔排序
     {
         int span=n;
         element temp;
         while(span > 1)//跨度为1时排序结束
         {
             span=(span+1)/2;
    
             for(int i=0; i<n-span; i++)
             {
                 if(list[i+span]<list[i])
                 {
                     temp=list[i+span];
                     list[i+span]=list[i];
                     list[i]=temp;
                 }
             }
         }
     }

    四、插入排序、选择排序 、冒泡排序

    /*
     *@list:待排序数组
     *@n:总排序元素个数
     */
    void insertSort(element list[], int n)//插入排序
    {
        int i=0;
        int j=0;
        element next;
        for(i=0; i<n; i++)
        {
            next=list[i];
            for(j=i-1;j>=0&&list[j]>next;j--)//j>=0且list[j]是和next比较
            {
                list[j+1]=list[j];//后一位等于前一位
            }
            list[j+1]=next;
        }
        return;
    }
    
    /*
     *@list:待排序数组
     *@n:总排序元素个数
     */
    void selectSort(element list[], int n)//选择排序
    {
        int i=0;
        int j=0;
        int k=0;
        element temp;
        for(i=0; i<n; i++)
        {
            temp=list[i];
            k=i;//不要忘记
    
            for(j=i+1; j<n; j++)
            {
                if(list[j]<temp)
                {
                    temp=list[j];
                    k=j;
                }
            }
    
            list[k]=list[i];
            list[i]=temp;
        }
        return;
    }
    
    /*
     *@list:待排序数组
     *@n:总排序元素个数
     */
    void bubbleSort(element list[], int n)//冒泡排序
    {
        int i=0;
        int j=0;
        element temp;
        bool exchange;//标记本趟是否有交换
    
        for(i=0; i<n; i++)
        {
            exchange=false;//本趟排序开始
    
            for(j=0; j<n-i-1; j++)//注意j的范围
            {
                if(list[j]>list[j+1])//j+1不能是后面排序好的元素,所以j<n-i-1
                {
                    temp=list[j];
                    list[j]=list[j+1];
                    list[j+1]=temp;
                    exchange=true;//本趟排序发生交换
                }
                if(!exchange)//本趟排序没有发生交换,说明前n-1个不用排序,提前终止算法
                {
                    return;
                }
            }
        }
        return;
    }

    五、堆排序

    /*
      *@list:待排序数组
      *@root:根结点下标
      *@n:总排序元素个数
      */
     void adjust(element list[], int root, int n)//调整最大堆方法一
      {
          int child=2*root+1;//左孩子
          element temp;
          while(child < n)//***while***  
          {
              if(child < n-1 && list[child]<list[child+1])//比较左右结点,得到较大的为child
              {
                  //注意child < n-1
                  child++;
              }
                  
              if(list[root] > list[child])//比较父节点与较大子节点child
              {
                     break;
              }
              else{
                  /*交换父子节点*/
                  temp = list[root];
                  list[root]=list[child];
                  list[child]=temp;
     
                 /*继续向下,特别要注意这里的*/
                  root=child;
                  child = 2*child +1;
              }
          }
      }
     void adjust2(element list[], int root, int n)//调整最大堆方法二
      {
          int child=2*root+1;//左孩子
     
          element rootkey=list[root];//标记最初根节点结点
     
          while(child < n)//***while***  
          {
              if(child < n-1 && list[child]<list[child+1])
              {
                  child++;//比较左右结点,得到较大的为child
              }
                  
              if(rootkey > list[child])//比较最初根节点结点 与 此时的最大子结点
              {
                     break;
              }
              else{
                  //这里不是交换父子结点,和insertSort思想类似
                  list[root]=list[child];//父节点等于较大孩子结点
                 
                  //分别向下移动
                  root=child;
                  child = 2*child +1;
              }
          }
          list[root]=rootkey;//找到最初根结点的合适位置
      }
     
     /*
      *@list:待排序数组
      *@n:总排序元素个数
      */
      void heapsort(element list[],int n)//堆排序
      {
          int i;
          element temp;
     
          /*初始化得到最大堆*/
          for(i=n/2;i>=0;i--)  //从n/2处依次向前调整 
            adjust(list,i,n); //或者采用 adjust2
     
          for(i=n-1;i>0;i--)//i为剩余规模
          {
              temp=list[i]; //交换根结点和i结点
              list[i]=list[0];
              list[0]=temp;
              //或者采用 adjust2
              adjust(list,0,i);//重新调整,此时参数root为0,规模n为i
           }
      }

    六、快速排序(最后修改)

    //2012-07-16
     void quickSort(element list[], int left, int right)//快速排序
     {
         int i=left;
         int j=right;
     
         if(i >= j) //判断需要i<j
             return;
     
         element temp=list[i];
     
         while(i<j)
         {
             while(i<j && list[j]>temp)//需要i<j
                 j--;
     
             list[i]=list[j];
             i++;
     
             while(i<j && list[i]<temp)//需要i<j
                 i++;
     
             list[j]=list[i];
             j--;
         }
         
         list[j+1]=temp;// 运行到此处j j+1 i
     
         quickSort(list,left,j);
         quickSort(list,i,right);
     }
     
     void quickSort2(element list[], int left, int right)
     {
         int i=left;
         int j=right;
     
         if(i>=j)
             return;
     
         element pivot=list[i];
         element temp;
         j++;//以下i++,j--了一次,i是需要首先+1,但j不需要,所以此处需要提前+1,抵消
         
         do{
             do{
                 i++;
             }while( list[i]<pivot);//不需要i<j,便于之后的交换操作和子快速排序
     
             do{
                 j--;
             }while(list[j]>pivot);//不需要i<j
     
             if(i<j)
             {
                 temp=list[i];
                 list[i]=list[j];
                 list[j]=temp;
             }
         }while(i<j);//运行到此处,a[i]>pivot,a[j]<pivot,j=i-1;
                     //一般情况结束时left...j,i...right  [j]<pivot,[i]>pivot所以交换left和j,
                     //特殊情况结束时left......right,i=j=right+1//1,2,3,4,5,6,7
                     //即结束时,i后的都大于pivot,j前的都小于pivot,其中[j]<pivot,[i]>pivot  
         list[left]=list[j];
         list[j]=pivot;
     
         quickSort(list,left,j-1);
         quickSort(list,j+1,right);
         
     }

    下面的是对quickSort方法的修改:

    删除了quickSort的18、24行,以及27、29、30进行对应修改。修改之后使得如下代码运行到23行时,i=j,这样思维更清晰。

    ★★★★★
    void quickSort3(element list[], int left, int right)//快速排序,修改时间2012-09-18 16:40:40
     {
         int i=left;
         int j=right;
     
         if(i >= j) //判断需要i<j
             return;
     
         element temp=list[i];
     
         while(i<j)
         {
             while(i<j && list[j]>temp)//需要i<j
                 j--;
     
             list[i]=list[j];
     
             while(i<j && list[i]<temp)//需要i<j
                 i++;
     
             list[j]=list[i];
         }
         list[i]=temp;// 运行到此处i=j
     
         quickSort3(list,left,i-1);
         quickSort3(list,j+1,right);
     }

    七、计数排序 

    计数排序是一种运行时间在输入的某种假设情况下可以为Θ(n)的算法,它的过程中没有比较环节。

    基本的思路就是假设输入序列中任意的元素x都满足x∈[0, k],且x和k都为整数。然后对每一元素x,都确定出序列中比它小的元素的个数,比如为n,则x排序后的位置就应当从n + 1处开始。实现的时候还需要考虑一些细节,比如序列中有几个元素大小相等,因此还需要对大小相等的元素个数进行计数,这样才能正确分配排序后各个元素的位置。

    过程中用到了一个辅助序列C,C的大小为k + 1,从C[0]到C[k],它的索引i代表序列中可能出现的大小为i的数,C[i]表示这个数有多少个。下面是算法导论上的例子:

    待排序的序列:A = [2, 5, 3, 0, 2, 3, 0, 3]    计数序列:C = [2, 0, 2, 3, 0, 1]

                                                                       索引:        0   1   2   3   4   5

    表示序列中0, 1, 2, 3, 4, 5的个数分别为2, 0, 2, 3, 0, 1。

    C序列中此时已经隐含了原序列中各个元素应该存放的位置,比如C[0] = 2,意味着大小为0的元素应当占据位置1, 2,而大小为1的元素应当从3开始,但原序列中没有1,因此向后遍历,大小为2的元素从3开始,个数为2,因此占据位置3, 4,以此类推。C[i]从0到n - 1求和的结果就是原序列中比n小的元素个数,假设为m,因此n应当从m开始,一直到m + c[n] - 1

    代码:(2012年7月16日 10:22:13)

    /*
      *@list:待排序数组,要求list[i]是大于等于0的整数;
      *@n:总排序元素个数
      */
      void countSort(element list[],int n)//计数排序
      {
          int max=list[0];
          for(int i=1; i<n; i++)//计算数组中最大元素
          {
              if(list[i]>max)
                  max=list[i];
          }
     
          element* count;
     
          count =(element*)malloc(sizeof(element)*(max+1));//数组下标为[0,...max]
          
          if(count==NULL)
              exit(1);//申请空间失败
     
          for(int i=0; i<=max; i++)//初试化计数数组
          {
              count[i]=0;
          }
     
          for(int i=0; i<n; i++)//计数
          {
              int index=list[i];
              count[index]++;
          }
          
          int j=0;
          for(int i=0; i<=max; i++)//根据计算数组排序
          {
              while(count[i]&&j<n)
              {
                  list[j]=i;
                  count[i]--;
                  j++;
              }
          }
     
          free(count);
          count=NULL;
      }

    八、二分查找

    递归和非递归二分查找
    //非递归二分查找算法
    /*list:待查找的有序数组
     *key:需要查找的元素
     *n:数组长度
     *return:返回查找的位置下标,返回-1表示未找到
        */
    int binarySearch(element list[], element key, int n)
    {
        int left =0;
        int right = n-1;
        int mid=0;
        while(left <= right)// <=,不能遗漏等于的情况
        {
            mid=left+(right-left)/2;
            if(list[mid] == key)
                return mid;
            else if(list[mid] < key)
                left=mid+1;
            else
                right=mid-1;
        }
        
        return -1;
    }
    //递归二分查找算法
    /*list:待查找的有序数组
     *key:需要查找的元素
     *left:数组下界
     *right:数组上界
     *return:返回查找的位置下标,返回-1表示未找到
        */
    int binarySearch2(element list[], element key, int left, int right)
    {
        int mid=0;
        if(left<=right)// <=,不能遗漏等于的情况
        {
            mid=left+(right-left)/2;
            if(list[mid] == key)
                return mid;
            else if(list[mid] < key)
                return binarySearch2(list, key, mid+1, right);
            else
                return binarySearch2(list, key, left, mid-1);
        }else{
            return -1;/*注意如果没有这种情况,返回值是永远是 mid,*/
        }
    }
    
    展开全文
  • 生成树是建立在无向图的基础上的,所以下面的讨论都是在无向图上进行的。 直观的一个应用就是:n个村庄,现在要在这些村庄之间修一些,其中村庄i和村庄j之间的距离是Dij,现在要修最短的使得所有村庄连接起来...
  • Fleury 算法,求欧拉回路

    千次阅读 2016-02-15 14:15:08
    简单的说:欧拉回路 就是经过图(向图、无向图)的每条边一次且仅一次,回到出发点的路径就叫欧拉回路; Fleury算法基本思想: ①.选择任意一个结点作为起点,选择一条从它开始的边,将其加到解的集合U中。...
  • 数据结构与算法分析

    2014-01-15 02:05:59
    9.6.1 无向图  9.6.2 双连通性  9.6.3 欧拉回路  9.6.4 向图  9.6.5 查找强分支  9.7 NP完全性介绍  9.7.1 难与易  9.7.2 NP类  9.7.3 NP完全问题  小结  练习  参考文献  第10章 算法设计...
  • 数据结构与算法.xmind

    2020-06-19 17:04:23
    无向图 表示方法 邻接矩阵 邻接表 遍历 深度优先搜索 广度优先搜索 哈希表 哈希函数 直接定址法 数字分析法 平方取中法 折叠法 除留余数法 随机数法 处理哈希冲突 ...
  • 30、 已知有向图G=,E>,试设计一算法以判断对于任意两点u和v,是否存在一条从u到v的路径,并分析其复杂度。 31、 对于给定的一个二叉树T(如下图) a) 设计一个算法,统计二叉树中结点总数; b) 设计一个算法,求...
  • 如果图为无向图或者环图,则无法判断具体的那个元素在那个元素之前。就会出现错误 实施方法:始终维持一个数组inDegree[]和队列Q,一旦当前度数减少后为零,则立刻加入队列,每次选择队列的中元素出队。由上面...
  • 9.6.1 无向图 9.6.2 双连通性 9.6.3 欧拉回路 9.6.4 向图 9.6.5 查找强分支 9.7 np-完全性介绍 9.7.1 难与易 9.7.2 np类 9.7.3 np-完全问题 总结 练习 参考文献 第10章 算法设计技巧...
  • 数据结构与算法分析—C语言描述 高清版

    千次下载 热门讨论 2008-04-05 21:01:56
    9.6.1 无向图 9.6.2 双连通性 9.6.3 欧拉回路 9.6.4 向图 9.6.5 查找强分支 9.7 NP完全性介绍 9.7.1 难与易 9.7.2 NP类 9.7.3 NP完全问题 总结 练习 参考文献 第10章 算法设计技巧 10.1 贪婪算法 10.1.1 一个...
  • 7.7.1 无向图的邻接表的建立和遍历 7.7.2 向无环图的拓扑排序和求关键路径 习题七 第8章 查找 8.1 基本概念 8.2 静态表查找 8.2.1 顺序表的查找 8.2.2 有序表的查找 8.2.3 索引顺序表的查找 8.3 动态查找...
  • 无向图 G n 个顶点,其邻接矩阵为 A[1…n,1…n],且压缩存储在 B[1…k],则 k 的 值至少为( )。 A.n(n+1)/2 B. n2/2 C. (n-1)(n+1)/2 D. n(n-1)/2 4.下列排序算法中,( )算法可能会出现下面情况:在最后一...
  • 有向无负权指的(弱连通)   假设求1到6的最短路径,用迪杰斯特拉(Dijkstra)算法如何求?   迪杰斯特拉算法像无权最短路径算法一样,按阶段进行。假设s是起点,在每个阶段,迪杰斯特拉算法选择离s...
  • 10.2.4 在无向图中寻找三角形 10.3 有关线性规划的归约 10.3.1 概述与定义 10.3.2 归约到线性规划的例子 10.4 下界的归约 10.4.1 寻找简单多边形算法复杂度的下界 10.4.2 关于矩阵的简单归约 10.5 常见的...
  • 整个森林可以认为是一个无向图,图中N 个美丽的景点,景点从1 至N编号。在景点之间一些连接。可可正在景点M (M ≤ N)处。以后的每个时间单位,可可都会选择去相邻的景点(可能多个)中的一...
  • 10.6.1 有向无 414 10.6.2 拓扑排序 415 10.7 关键路径 417 10.7.1 AOV网和AOE网 417 10.7.2 最长路径 419 10.7.3 关键路径 419 第11章 提高篇(5)——动态规划专题 425 11.1 动态规划的递归写法和递推写法 425...
  •  9.6.1 无向图   9.6.2 双连通性   9.6.3 欧拉回路   9.6.4 向图   9.6.5 查找强分支   9.7 NP完全性介绍   9.7.1 难与易   9.7.2 NP类   9.7.3 NP完全问题   小结   练习   参考...
  • 这片树林里N座房子,M条有向道路,组成了一张有向无。 树林里的树非常茂密,足以遮挡视线,但是沿着道路望去,却是视野开阔。 如果从房子A沿着走下去能够到达B,那么在A和B里的人是能够相互望见的。 现在cl2...
  • 题意:给你一个无向图的信息有关距离和花费,再给定起点和终点,求起点到终点的最小距离和花费,若最小距离多个,选择花费最小的那个。 解题思路:这是一个单源点最短路径问题,我们明显是要用Dijkstra算法去...
  •  9.6.1 无向图   9.6.2 双连通性   9.6.3 欧拉回路   9.6.4 向图   9.6.5 查找强分支   9.7 NP完全性介绍   9.7.1 难与易   9.7.2 NP类   9.7.3 NP完全问题   小结   练习   参考...
  • (2)求有向图的强连通分量(Strong_comp) (3)环图的两个算法  拓扑排序(Toposort)  关键路径(Critical_path) (4)求最小生成树  普里姆算法(Prim)  克鲁斯卡尔算法(Kruscal) (5)求关节点和重...
  • 9.6.1 无向图 9.6.2 双连通性 9.6.3 欧拉回路 9.6.4 向图 9.6.5 查找强分支 9.7 NP完全性介绍 9.7.1 难与易 9.7.2 NP类 9.7.3 NP完全问题 小结 练习 参考文献 第10章 算法设计技巧 10.1 贪婪算法...
  • 6.4.1 遍历有向图 6.4.2 传递闭包 6.4.3 DFS和垃圾收集 6.4.4 环图 6.5 Java示例:深度优先查找 6.5.1 修饰模式 6.5.2 DFS引擎 6.5.3 模板方法设计模式 6.6 习题 基础题 创新题 程序设计 6.7 本章注记 第7章 ...
  • 9.6.1无向图270 9.6.2双连通性271 9.6.3欧拉回路273 9.6.4向图275 9.6.5查找强分支276 9.7NP—完全性介绍277 9.7.1难与易278 9.7.2NP类278 9.7.3NP—完全问题279 小结280 练习280 参考文献284 第10章...
  • 20.2.4 有向图算法 378 20.2.5 哲学家饮水* 379 20.3 参考文献注释 383 20.4 习题 383 第21章 带进程故障的异步网络计算 386 21.1 网络模型 386 21.2 故障环境中一致性的不可能性 387 21.3 随机算法 ...
  • 20.2.4 有向图算法 378 20.2.5 哲学家饮水* 379 20.3 参考文献注释 383 20.4 习题 383 第21章 带进程故障的异步网络计算 386 21.1 网络模型 386 21.2 故障环境中一致性的不可能性 387 21.3 随机算法 388 21.4 ...

空空如也

空空如也

1 2 3 4 5
收藏数 82
精华内容 32
关键字:

无向图路有选择算法