图
图(Graph),分为有向图和无向图,其中有向图就是两个节点之间的边只能按照固定方向流通,无向图则可以按照任意方向流通。
图以如下的结构组成:
-
节点(vertice)。
-
边(edge)。
对于一个图而言,节点和边构成了一整个图。值得注意的是,一个图可以只有节点没有边,这也符合图的定义。
图有以下的概念定义:
-
阶(order)。图的度就是他顶点的数量,记为V(G)
-
大小(size)。图的大小就是它边的数量,记为E(G)
-
子图(subdigraph)。若一个图的节点集、边集都是另一个图的子集,则称此图位另一个图的子图。记为V1⊆V2。
-
有向图的基本图(underlying graph),是它对应的无向图。
-
有向图的反向有向图(Reverse digraphs),是它所有路径方向改变的有向图。
-
有向图的邻接矩阵(Adjacency Matrix )。以有向图的节点个数为横纵坐标画矩阵,不能到达的赋0,能到达的赋开销。如0->2=1,那(0,2)则赋值1
-
有向图的邻接列表(adjacency list)。一维列表的第i位代表着i节点直接通向的节点列表。
-
图的周长(Girth of a graph)。一个图中最短环的长度被称为图的周长。
-
图的连通性(Digraph connectivity)。如果一个图每个节点间都有路径,那么这个图被称为一个连通的图。
如果该有向图每个顶点都相互可到达,则这个图是强连通的。
如果该有向图的基础图连通,则这个图是若联通的。
-
分量(Component)。一个图最大的连通子图被称之为分量。一个有向图的最大连通子图被称为强分量。
-
二部图(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. -
加权图(Weighted graphs)。如果一个图每个路径的长度不唯一,则这个图被称为加权图。
边有以下的概念定义:
- 阶数(dgree)。顶点的阶数是他连接的边的数量。
一个无向图最多有n(n-1)/2个边
节点有以下的概念定义:
-
距离(dgree)。两个节点之间的最短路径被称之为距离。
-
源点(source)。入度为0的点被称之为源点。
-
汇点(sink)。出度为0的点被称之为汇点。
游走有以下的概念定义:
-
游走(Walk)。从某个节点出发,经过若干条路径,最后到达另一个节点,这个过程被称之为游走。游走可以有重复节点,他只是一次“Walk”罢了。
-
路径(Path)。从某个节点出发,不重复经过若干条路径,最后到达另一个节点,这两个节点之间的游走被称之为路径。
-
环(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)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
简单的来说,就是全有序。