- 定义：
图可以用G=(v,e)表示，v是顶点的集合，e是连接边的集合。 有向图用<a,b>表示，无向图用(a,b)有向图 v={A,B,C},e={<a,b>,<b,c>,<c,a>}
无向图 v={A,B,C},e={(a,b),(b,c),(c,a)}
加权图 v={A,B,C},e={(a,b,1),(b,c,2),(c,a,3)}
- 邻接：如（Vi，Vj）是图中的一条边，则称Vi和Vj是邻接的。如<Vi，Vj>是图中的一条边，则称Vi邻接到Vj，或Vj和Vi邻接 [index->P7]
- 度：无向图中邻接于某一节点的边数 [index->P7]
- 入度：有向图中连接到一点的边的数量 [index->P7]
- 出度：有向图中从一点发出的边的数量 [index->P7]
- 子图：v’∈v e'∈e 则g'是g的子图 [index->P8~9]
- 路径和路径长度：对1<i<N，结点序列w1,w2,……wN 中的结点对（wi, wi+1）都有（wi, wi+1）∈ E或<wi, wi+1> ∈ E，那么，w1,w2,……wN是图中的一条路径。 非加权的路径长度就是组成路径的边数，对于路径w1,w2,……wN，非加权路径长度为N-1。 加权路径长度是指路径上所有边的权值之和。 简单路径和环：如果一条路径上的所有结点，除了起始结点和终止结点可能相同外，其余的结点都不相同，则称其为简单路径。一个回路或环是一条简单路径，其起始结点和终止结点相同，且路径长度至少为1 [index->P10]
- 连通：v->v'之间有路径存在 [index->P11]
- 连通图：任意两点都是连通的 [index->P11]
- 连通分量(->非连通图)：非连通图中的极大连通子图 [index->P11]
- 极大连通子图：加入剩下任意一个顶点就会使子图不连通 [ADD index->P11]
- 强连通图：任意两点都是连通的 [index->P13]
- 强连通分量：极大连通子图 [index->P13]
- 弱连通图：如果不是强连通图，但看成无向图时是连通的 [index->P13]
- 完全图：没有环，没有重边（无向图） [index->P15]
- 有向完全图：每两个节点之间都有两条环称作有向完全图 [index->P15]
- 有向无环图（DAG（Directed Acyclic Graph））：一个有向图里没有环 [index->P15]
- 生成树：连通图的极小连通子图 [index->P16]
- 极小连通子图：添加原图中一条边后，必定形成回路或环 [index->P16]
- 存储：
-
邻接矩阵（有向图）：设无向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该无向图；并且 A[i,j] = 1 , 如果i 至 j 有一条无向边；A[i,j] = 0如果 i 至 j 没有一条无向边 注意： 无向图的邻接矩阵是一个对称矩阵
i 结点的度: i 行或 i 列之和。[index->P24] -
邻接矩阵（有向图）：分别用 0、1、2、3 分别标识结点A、B、C、D。而将真正的数据字段之值放入一个一维数组之中。[index->P23]
-
加权邻接矩阵：设有向图具有 n 个结点，则用 n 行 n 列的矩阵 A 表示该有向图； 如果i 至 j 有一条有向边且它的权值为a ，则A[i,j] = a 。如果 i 至 j 没有一条有向边。则A[i,j] = 空 或其它标志 [index->P25]
-
邻接表：设有向图或无向图具有 n 个结点，则用结点表、边表表示该有向图或无向图。[index->P35~45]
- 结点表：用数组或单链表的形式存放所有的结点值。如果结点数n已知，则采用数组形式，否则应采用单链表的形式。
- 边表（边结点表）：每条边用一个结点进行表示。同一个结点出发的所有的边形成它的边结点单链表。
- 遍历：
-
DFS：
- 选中第一个被访问的顶点；
- 对顶点作已访问过的标志；
- 依次从顶点的未被访问过的第一个、第二个、第三个…… 邻接顶点出发，进行深度优先搜索；
- 如果还有顶点未被访问，则选中一个起始顶点，转向2；
- 所有的顶点都被访问到，则结束。[index->P47~59]
-
BFS:
- 选中第一个被访问的顶点；
- 对顶点作已访问过的标志；
- 依次访问已访问顶点的未被访问过的第一个、第二个、第三个……第 m 个邻接顶点 W1 、W2、W3…… Wm ，进行访问且进行标记，转向3；
- 如果还有顶点未被访问，则选中一个起始顶点，转向2；
- 所有的顶点都被访问到，则结束。 [index->P61~68]
- 拓补排序： 设G=（V，E）是一个具有n个顶点的有向无环图。V中的顶点序列V1，V2，…，Vn称为一个拓扑序列，当且仅当该序列满足下列条件：若在G中，从Vi到Vj有一条路径，则序列中Vi必须排在Vj的前面。 [index->P97~106]