图
root(图) 图的定义 图结构的存储 邻接矩阵法 邻接表法 邻接多重表 十字链表 图的遍历 深度优先遍历 广度优先遍历 图的相关应用 最小生成树 Prim 算法 Kruskal 算法 最短路径 Dijkstra 算法 Floyd 算法 拓扑排序 AOV 网 关键路径 AOE 网图的基本概念
图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点关系的集合。注意线性表可以是空表，树可以是空树，但是图不可以是空图。
下面是图的一些基本概念和基本术语：
有向图和无向图
当E是有向边（弧）的有限集合时，则图G为无向图。若E是无向边的有限集合则图G为无向图。
简单图、多重图
一个图G如果满足不存在重复边、不存在顶点到自身的边，那么称图G为简单图。若图G中某两个顶点之间的边数大于1条，又允许顶点通过一条边和自身关联，则称图G为多重图。
完全图
任何两个顶点之间都存在边的无向图是完全图。有向完全图是任意两个顶点之间都存在方向相反的两条弧的有向图。
子图
如果一个图中的顶点集和边集是另一个图的子集，那么称前者为后者的子图。
连通、连通图和连通分量
在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。无向图中极大连通子图称为连通分量。
强连通图和强连通分量
在有向图中，如果有一对顶点v和w，从v到w和从w到v之间都有路径，则称为这两个顶点时强连通的。若图中任何一对顶点都是强连通的，则称为此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。
生成树和生成森林
连通图的生成树是包含图中全部顶点的一个极小连通子图。若痛中的顶点树为n，则它生成树包含n-1条边。在非连通图中，连通分量的生成树构成了非连通图的生成森林。
顶点的度、入度和出度
在无向图中，顶点v的度是指依附于顶点v的边的条数，无向图的全部顶点的度的和等于边数的2倍，因为每条边和两个顶点相关联。
在有向图中，顶点v的度分为入度和出度，入度是以顶点v为终点的有向边的数量，而出度是以顶点v为起点的有向边的数目。
边的权和网
在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称为网。
稠密图和稀疏图
边数很少的图称为稀疏图，反之称为稠密图。
路径、路径长度和回路
两个顶点之间的路径是指两个顶点间的顶点序列，路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有n个顶点，并且有大于n-1 条边，则此图一定有环。
简单路径和简单回路
在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
距离
从顶点u出发到顶点v的最短路径若存在，则此路径的长度为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷。
有向树
一个顶点的入度为0，其余顶点的入度均为1的有向图称为有向树。
图的存储及基本操作
图的存储需要完整、准确的反映顶点集和边集的信息。
邻接矩阵法
所谓邻接矩阵，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵。
图的邻接矩阵存储表示法具有以下特点：
- 无向图邻接矩阵一定是唯一的对称矩阵。因此，在实际存储邻接矩阵时只需存储上或下三角矩阵即可。
- 对于无向图，邻接矩阵的第i行或第i列非零元素的个数正好是顶点i的度。
- 对于有向图，邻接矩阵的第i行非零元素或非∞元素的个数正好是顶点i的出度，第i列非零元素或非∞元素的个数正好是顶点i的入度。
- 用邻接矩阵存储图，很容易确定两个顶点是否相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测。
- 稠密图适合使用邻接矩阵存储。
- 设图G的邻接矩阵为A，A^n^[i][j]等于由顶点i到顶点j的长度为n的路径的数目。
邻接表法
当一个图是稀疏图的时候，使用邻接矩阵法显然要量费大量的存储空间，而使用邻接表是指对图G中的每一个顶点vi建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边，如果是有向图则就是以顶点i为尾的弧，这个单链表就称为顶点i的边表。边表的头指针和顶点的数据信息采用顺序存储。
图的邻接表存储方法具有以下特点：
- 稀疏图适合使用邻接表法。
- 邻接表中对于一个顶点很容易找到他所有的邻边，但是确定两个点之间是否有边，则需要在相应结点对应的边表中查找另一个结点。
- 在有向图的邻接表表示中，求一个给定顶点的出度只需要计算其边表中结点的个数，如果是出度则需遍历整个表。
- 图的邻接表不唯一。
十字链表
十字链表是有向图的一种链式存储结构，在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。
邻接多重表
邻接多重表是无向图的另一种链式存储结构，在邻接表中，容易求的顶点和边的各种信息，但是在邻接表中求两点之间是否存在边对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率低，在邻接多重表中，所有依附于同一顶点的边串联在同一个链表中，由于每条边依附于两个顶点，因此每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接表的区别在于，同一条边在邻接表中用两个结点表示，二在邻接多重表只有一个。
图的基本操作
- Adjacent(G, x, y)：判断图G是否存在边<x,y>或（x,y）。
- Neighbors(G, x): 列出图G中与结点x邻接的边。
- InsertVertex(G, x): 在图G中插入顶点x。
- DeleteVertex(G, x): 在图G中删除顶点x。
- AddEdge(G, x, y): 若无向边（x,y）或有向边<x,y>不存在，则有向图G中添加该边。
- RemoveEdge(G, x, y): 若无向边（x,y）或有向边<x,y>存在，则自从图G中删除该边。
- FirstNeighbor(G, x): 求图G中顶点x的第一个邻接点。
- NextNeightbor(G, x, y): 假设图G中顶点y是顶点x的一个邻接点，返回除了y外顶点x的下一个邻接点的顶点号。
- Get_edge_velue(G, x, y): 获取图G中边（x，y）或<x,y>的权值。
- Set_edge_value(G, x, y, v): 设置图G中边（x，y）或<x,y>的权值。
图的遍历
图的遍历是指从图中的某一个顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。
广度优先搜索
广度优先搜索类似于二叉树的层序遍历算法。基本思想是：首先访问起始顶点v，然后从v出发，依次访问
深度优先搜索
图的遍历与连通性
图的遍历算法可以用来判断图的连通性，对于无向图来说，若无向图是连通的，则从任意一个结点出发，仅需一次遍历就能够访问图中的所有顶点；若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点在连通分量的所有顶点，而对于途中其他连通分量的顶点，则无法通过这次遍历访问。对于有向图来说，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。