图
图（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）的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
简单的来说，就是全有序。