一、图的定义
图由顶点的有穷非空集合和顶点间的边的集合组成，通常表示如下
g=(v，e ) )。
在此，g表示图，v是图g中的顶点的集合，e是图g中的顶点间的边的集合。
注：
在线性表中，元素个数可以为零，称为空表；
在树中，节点数可以为零，称为空树。
在图中，顶点的数量不能为零，但可以没有边。
二、图的遍历
图的扫描是从图中的某个顶点出发，对图中的所有顶点只访问一次，只访问一次。
图遍历操作中需要解决的关键问题：
在图中，如何选择导线测量的起始顶点？
解决方案：从编号小的顶点开始。
在路线表格中，表格中的数据元素编号是元素在序列中的位置，因此该编号是唯一的。 在树中，按层序对节点进行编号。 由于树具有层次性，因此其层序编号也是唯一的。 在图中，任何两个顶点之间都可能存在边缘，顶点没有确定的优先顺序，因此顶点的编号不是唯一的。 为了定义操作的方便性，将图中的顶点按任意顺序，例如顶点的存储顺序排列。
从一个起点可能无法到达所有其他顶点，该怎么办？
解决方案：多次调用从某个顶点出发遍历图表的算法。
图中存在电路，有些顶点可能会被重复访问，如何避免电路导致扫描陷入死循环？
解决方案：添加访问令牌数组visited[n]。
在图中，一个顶点可以与其他多个顶点相连。 访问这些顶点后，如何选择下一个要访问的顶点？
解决方案：深度优先遍历和广度优先遍历。
1、深度优先遍历
基本想法：
对顶点v的访问
从v的未接入的邻点中选出一个顶点w，根据w进行深度优先遍历；
重复上述两个步骤，直到与图的v相连的所有顶点都被访问。
2、广度优先遍历
基本想法：
对顶点v的访问
依次接入v的各未接入的邻点v1、v2、…、vk；
分别从v1、v2、…、vk开始依次访问未访问的邻点，使“先访问的顶点的邻点”先于“后访问的顶点的邻点”访问。 图中，直到与顶点v相连的所有顶点都被访问为止。
三、图的存储结构
是否可以使用顺序存储结构保存地图？
图的特征：顶点之间的关系为m:n。 即，任何2个顶点之间都可能存在关系(边)，由于不能用存储器位置表示这种任意的逻辑关系，所以图中不能采用顺序存储器结构。
如何保存图？
考虑到图的定义，图由顶点和边组成，分别考虑如何收纳顶点，如何收纳边。
邻接矩阵（数组表示法）
基本思想：用一维排列保存图中顶点的信息，用一维排列“邻接矩阵”保存图中各顶点间的邻接关系。
假设图g=(v，e )中有n个顶点，则邻接矩阵为nn的方阵，定义如下。
上述内容是从https://www.cn blogs.com/smile 233/p/8228073.html传送的
以上内容经常讨论邻接矩阵，但没有对邻接表进行说明(图都可以用邻接表和邻接矩阵记忆)。
邻接矩阵是优秀的图表记忆结构，但是在边数相对于顶点少的图表中，该结构的记忆空间浪费很大。 因此，数组和链表组合的存储方法称为邻接表。
相邻表的处理方法如下。
)1)图的顶点以一维数组存储。 当然，顶点也可以存储在单链表中，但数组容易读取顶点信息，非常方便。
)2)图中各顶点vi的所有邻接点构成一个线形表，邻接点的数量是不定的，所以用单链表记忆，有向图表称为顶点vi的边表，有向图表称为顶点vi的弧尾的边表。
例如，下图是没有有向图的邻接表的结构。
从图中可以看到，顶点表的各节点用data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指向边缘表的第一个节点，即该顶点的第一个邻接点的指针域边缘节点由adjvex和next两个域组成。 adjvex是邻接点区域，存储某顶点的邻接点的顶点表中的下标，next存储指向边表中下一个节点的指针。
对于加权网络图，在边表节点定义中再增加一个weight的数据字段，存储权重信息即可。 如下图所示。
从图中可以看到，顶点表的各个节点表示为data和firstedge两个域，data是数据域，存储顶点信息，firstedge存储
针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。如下图所示。
四.两者区别
对于一个具有n个顶点e条边的无向图
它的邻接表表示有n个顶点表结点2e个边表结点
对于一个具有n个顶点e条边的有向图
它的邻接表表示有n个顶点表结点e个边表结点
如果图中边的数目远远小于n2称作稀疏图，这是用邻接表表示比用邻接矩阵表示节省空间;
如果图中边的数目接近于n2,对于无向图接近于n*(n-1)称作稠密图,考虑到邻接表中要附加链域，采用邻接矩阵表示法为宜。
附上leetcode上关于有向无环图的应用的题，课表的安排没有用链表实现利用c++STL中的容器vector去实现。
class Solution {public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<int> indegree(numCourses,0);//入度表 vector<vector<int> >lis(numCourses,vector<int>());//用vector来存储邻接表 for(auto v:prerequisites) { indegree[v[0]]++; lis[v[1]].push_back(v[0]); } queue<int>q; //从入度为0的结点开始处理数据 for(auto i=0;i<indegree.size();i++) { if(indegree[i]==0) q.push(i); } vector<int>res; while(!q.empty()) { auto temp=q.front();q.pop(); res.push_back(temp); for(auto l:lis[temp])//以temp为头结点的链表 { if(--indegree[l]==0) q.push(l); } } return res.size() == numCourses; }};同样的代码修改一下return值就可以解决这个问题