一、图的概念

图是由它的节点和连线组成，根据是否有向性可以分为有向图和无向图。节点与节点之间由有向的线段连接叫做有向图，无有向的线段连接叫做无向图。无向图中每个节点的连线可以理解为是有向图中节点的来去两个连线。

顶点：
每个节点都是一个顶点。

弧：
节点与节点之间的连线叫做弧。

弧头：
箭头的头部叫做弧头。

弧尾：
箭头的尾部叫做弧尾。

出度：
同一个节点发射出去的节点数量叫做出度数。

入度：
由其他节点发射过来的节点数量叫做入度数。

边：
无向图中的弧就是边。

权值
对弧或者边数量的一种抽象。

邻节点：
节点之间可以直接连接称为领节点。

连通图：
在无向图中，对于某一个节点来说，都有通向其他节点的连线。即任意两个节点之间都是连通的，叫做连通图。

完全图：
无向图中，所有的顶点与其他任意顶点，都有直接的连接线，叫做完全图。边数=顶点数*（顶点数-1）/2。

生成树：
完全图可以简化成生成树。由最小数量的边连接成的图就形成一颗生成树（由所有顶点及仅能够连接顶点的边组成）。生成树边数 = 顶点数 - 1。

二、图的应用

1. 路径规划：导航最小路径。
2. 工程规划：高速公路修建，电网，光纤修建等。
3. 战略规划：根据地图做战略规划，军事规划等。

三、图的存储方式

1. 邻接矩阵：节点与节点之间有弧的地方用1表示，如果有权值，直接用权值表示。没有弧的地方用0表示。

有向图的邻接矩阵
无向图的邻接矩阵

2. 邻接表（链式存储）：由顶点索引，以该顶点弧链表的头节点和顶点数据组成链表结构来存储图信息。
3. 十字链表（链式存储）：由顶点索引，顶点数据，第一条入弧节点指针和第一条出弧节点指针来存储图信息。
4. 邻接多重表（链式存储无向图）：由顶点索引，顶点数据以及第一条边的节点指针来存储图信息。

四、图的遍历

1. 深度优先搜索
   从一个根节点向下搜索，搜索到每一个子节点，深入到最终端。再由根节点向另一个子节点搜索，深入到另一个子节点的最终端，以此类推。
   

2. 广度优先搜索
   把图分成层次，一层一层地进行搜索。