图(Graph),分为有向图和无向图,其中有向图就是两个节点之间的边只能按照固定方向流通,无向图则可以按照任意方向流通。

图以如下的结构组成:

  1. 节点(vertice)。

  2. 边(edge)。

    对于一个图而言,节点和边构成了一整个图。值得注意的是,一个图可以只有节点没有边,这也符合图的定义。

图有以下的概念定义:

  1. 阶(order)。图的度就是他顶点的数量,记为V(G)

  2. 大小(size)。图的大小就是它边的数量,记为E(G)

  3. 子图(subdigraph)。若一个图的节点集、边集都是另一个图的子集,则称此图位另一个图的子图。记为V1⊆V2。

  4. 有向图的基本图(underlying graph),是它对应的无向图。

  5. 有向图的反向有向图(Reverse digraphs),是它所有路径方向改变的有向图。

  6. 有向图的邻接矩阵(Adjacency Matrix )。以有向图的节点个数为横纵坐标画矩阵,不能到达的赋0,能到达的赋开销。如0->2=1,那(0,2)则赋值1

  7. 有向图的邻接列表(adjacency list)。一维列表的第i位代表着i节点直接通向的节点列表。

  8. 图的周长(Girth of a graph)。一个图中最短环的长度被称为图的周长。

  9. 图的连通性(Digraph connectivity)。如果一个图每个节点间都有路径,那么这个图被称为一个连通的图。

    如果该有向图每个顶点都相互可到达,则这个图是强连通的。

    如果该有向图的基础图连通,则这个图是若联通的。

  10. 分量(Component)。一个图最大的连通子图被称之为分量。一个有向图的最大连通子图被称为强分量。

  11. 二部图(Bipartite graphs)。如果一个图可以划分为两个非空不相交的子集,则图G被称为一个二部图。

    等价条件:
    1. G有二部着色性G has a 2-coloring;
    2. G是二部的G is bipartite;
    3. G不包含技术长度循环G does not contain an odd length cycle.

  12. 加权图(Weighted graphs)。如果一个图每个路径的长度不唯一,则这个图被称为加权图。

边有以下的概念定义:

  1. 阶数(dgree)。顶点的阶数是他连接的边的数量。
    一个无向图最多有n(n-1)/2个边

节点有以下的概念定义:

  1. 距离(dgree)。两个节点之间的最短路径被称之为距离。

  2. 源点(source)。入度为0的点被称之为源点。

  3. 汇点(sink)。出度为0的点被称之为汇点。

游走有以下的概念定义:

  1. 游走(Walk)。从某个节点出发,经过若干条路径,最后到达另一个节点,这个过程被称之为游走。游走可以有重复节点,他只是一次“Walk”罢了。

  2. 路径(Path)。从某个节点出发,不重复经过若干条路径,最后到达另一个节点,这两个节点之间的游走被称之为路径。

  3. 环(Cycle)。从某个节点出发,经过若干条路径,最后回到原节点,这两个节点之间的游走被称之为环。

搜索

图的搜索方式主要为

1.深度优先搜索: Stack – Depth-first search (DFS)

​ 深度优先搜索所使用的数据结构是栈。栈遵循先入后出的原则,将遍历的新节点入栈后,该节点被优先遍历。

2.广度优先搜索: Queue – Breadth-first search (BFS)

​ 广度优先搜索所使用的数据结构是队列。队列遵循先入先出的原则,将遍历的新节点入栈后,该节点被最后遍历,继续遍历先前节点。

3.优先级搜索:Priority Queues – Priority first search (PFS)

​ 我们不难看出,无论深度优先搜索还是广度优先搜索,都只是为新加入的节点赋了不同的优先级而已。这就是优先级搜索。

迪克斯特拉算法

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。

贝尔曼-福特算法

贝尔曼-福特算法(英语:Bellman–Ford algorithm),求解单源最短路径问题的一种算法,由理查德·贝尔曼(Richard Bellman) 和莱斯特·福特创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法,因为Edward F. Moore也为这个算法的发展做出了贡献。

它的原理是对图进行|V|−1次最短路径估计,得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达O(|V||E|)。但算法可以进行若干种优化,提高了效率。

拓扑排序

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

简单的来说,就是全有序。

最近的文章

拂光算法资源共享站公约

本站由ray和tt共同建立,建立初衷是为所有自力更生的算法竞赛选手提供一个收录题目资源与发布题目解法的网站。本站由主站与个人站两部分构成。主站作为题单目录,个人站发布解法。您可以自建题单、扩充题单等,具体格式详见建站格式一节。本站非盈利目的,因此对于题目资源版权并无侵犯。本站不进行题目信息收录,仅收…

继续阅读
更早的文章

1.1 动态规划

动态规划之经典线性递归​动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。​动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于…

继续阅读