1.图：G=(V,E) V:顶点(数据元素)的有穷非空集合；E:边的有穷集合。
1)按有没有箭头可分为：有向图和无向图
2)若任意两个点都有一条边相连接则为完全图
3)稀疏图：有很少边或弧的图(e<nlogn) [带箭头的边称为弧]
稠密图：有较多边或弧的图
4)网：边/弧带权的图
6)邻接与关联(依附)
7)顶点的度：与该顶点相关联的边的数目，记为TD(v)
注：在有向图中，顶点的度等于该顶点的入度和出度之和。顶点v的入度是以v为终点的有向边的条数，记为ID(v)；顶点v的出度是以v为始点的有向边的条数，记作OD(v)。
8)路径、路径长度、回路(环)、简单路径
路径：接续的边构成的顶点序列。
路径长度：路径上边或者弧的数目/权值之和。
回路(环)：第一个顶点和终点可以相同外，其余顶点均不相同的路径。
简单回路(简单环)：除路径七点和终点可以相同外，其他顶点均不相同的路径。
简单路径：除路径起点和终点相同外，其余顶点均不相同的路径。
9)连通图与强连通图
10)权和网
权：图中边或弧所具有的相关数称为权。表面从一个顶点到另一个顶点的距离或者耗费。
网：带权的图称为网。
11)子图
12)连通分量与强连通分量
13)极小连通子图、生成树与生成森林
2.图的存储结构
图的逻辑结构为：多对多；而图没有顺序存储结构，但可以借助二维数组来表示元素间的关系，即用数组表示法(邻接矩阵)
也可以用链式存储结构来表示：如多重链表(邻接表、邻接多重表、十字链表)
1)数组(邻接矩阵)表示法
首先建立一个顶点表(记录各个顶点信息)和一个邻接矩阵(表示各个顶点之间关系)
设图A=(V,E)有n个顶点，则顶点表Vexs[n]
图的邻接矩阵是一个二维数组A.arcs[n][n],定义为：
注意到：
(1)对角线上元素全为0，且是对称矩阵。
(2)对于无向图，邻接矩阵的第i行(或第i列)非零元素的个数为第i个顶点的度。
(3)完全图的邻接矩阵中，对角元素为0，其余为1。
注意：
在有向图的邻接矩阵中，第i行含义：以结点Vi为尾的弧(即出度边)；第i列含义：以结点Vi为头的弧(即入度边)。
有向图的邻接矩阵可能是不对称的。
顶点的出度=第i行元素之和
顶点的入度=第i列元素之和
图的邻接矩阵的存储表示：用两个数组分别存储顶点表和邻接矩阵
#define MaxInt 32767 //表示极大值，即∞
#define MVNum 100 //最大定点数
typedef char VerTexType; //设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整形
typedef stuct{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //图的当前点数和边数
}AMGraph;
邻接矩阵的优缺点：
1.直观、简单、好理解。
2.方便检查任意一对顶点间是否存在边。
3.方便找任一顶点的所有邻接点(有边直接相连的顶点)。
4.方便计算任一顶点的度。
5.但不便于增加和删除顶点。
6.浪费空间---存稀疏图有大量无效元素，而对稠密图(特别是完全图)还是很合算的。
7.浪费时间---统计稀疏图中一共有多少条边。
邻接表表示法(链式)
图的邻接表存储表示
#define MaxVertexNum 100 //图中顶点数目的最大值
typedef struct ArcNode{ //边表结点
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *next; //指向下一条弧的指针
InfoType info; //网的边权值
}ArcNode;
typedef struct VNode{ //顶点表结点
VertexType data; //顶点信息
ArcNode *first; //指向第一条依附该顶点弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
AdjList vertices; //邻接表
int vexnum,arcnum; //图的顶点数和弧数
} ALGraph; //ALGraph是以邻接表存储的图类型
图的遍历：
广度优先遍历(BFS):由图的某一结点出发，首先依次访问该结点的所有邻接结点，再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点。重复此过程，直到所有顶点均被访问为止。
算法实现：
bool visted[MAX_VERTEX_NUM]; //设置访问标记数组
void BFSTraverse(Graph G){
//对图进行广度优先遍历，设访问函数为visit()
for(i=0;i<G.vexnum,++i)
visited[i]=FALSE; //访问标记数组初始化
InitQueue(Q); //初始化辅助队列Q
for(i=0;i<G.vexnum;++i) //从0号顶点开始遍历
if(!visited[i]) //对每个连通分量调用一次BFS
BFS(G,i); //vi未访问过，从vi开始BFS
}
void BFS(Graph G,int v){
//从顶点出发，广度优先遍历图G，引入一个辅助队列Q
visit(v)； //访问初始顶点v
visited[v]=TRUE; //对顶点v作已访问标记
Enqueue(Q,v); //顶点v入队
while(!isEmpty(Q)){ //若队列不为空
Dequeue(Q,v); //顶点v出队
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
//检测v的所有邻接点
if(!visted[w]){ //若w为v尚未访问过的邻接结点
visit(w); //访问顶点w
visited[w]=TRUE; //对顶点w做已访问标记
EnQueue(Q,w); //顶点w入队列
｝
算法效率分析：
如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环监测矩阵中的整整一行(n个元素),总的时间代价为O(n²)
如果使用邻接表，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)
深度优先遍历(DFS)：一条道走到黑，没有路往回退，退到有路继续走，直到走完所有点
算法实现：
bool visited [MAX_VERTEX_NUM]; //访问标记数组
void DFSTraverse(Graph G){
//对图G进行深度优先遍历，访问函数为visit()
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE; //初始化已访问标记数据
for(v=0;v<G.vexnum;++v) //从v=0开始遍历
if(!visited[v])
DFS(G,v);
}
void DFS(Graph G,int v){
//从顶点v出发,采用递归思想，深度优先遍历图G
visit(v); //访问顶点v
visited[v]=TRUE; //设已访问标记
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w))
if(!visited[w]){ //w为v尚未访问的邻接顶点
DFS(G,w);
}
}
算法效率分析：
用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n²)
用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)
(稠密图适合在邻接矩阵上进行深度遍历，稠密图适合在邻接表上进行深度遍历)
转载：https://blog.csdn.net/south_layout/article/details/100713145