G = (V, E)
V:顶点（数据元素的）有穷非空集合；
E：边的有穷集合。
无向图：每条边都是无方向的。
有向图：每条边都是有方向的。
完全图：任意两个顶点都有一条边两连
无向完全图：n个顶点 n(n-1)/2条边
有向完全图：n个顶点 n(n-1)条边
稀疏图：有很少边或弧地的图
稠密图：有较多的边或弧的图
网：边/弧带权的图
邻接：有边/弧相连的两个顶点之间的关系
关联（依附）：边/弧与顶点之间的关系
顶点的度：与该顶点相关联的边的数目，记为TD(v)
在有向图中，顶点的度等于该顶点的入度和出度之和。
顶点v的入度是以b为终点的有向边的条数，记为ID(v)
顶点的出度是以v为始点的有向边的条数，记作OD（v）
路径：接续的边构成的顶点序列
路径长度：路径上边或弧的数目/权值之和。
第一个顶点和最后一个顶点相同的路径。
简单路径:除路径起点和终点可以相同外，其余顶点均不相同的路径。
简单回路（简单环）:除路径起点和终点相同外，其余顶点均不相同的路径。
连通图（强连通图）:在无（有）向图G=(V,{E})中，若对任何两个顶点v,u都存在从v到u的路径，则称G是连通图（强连通图）。
权与网：图中边或弧所具有的相关数称为权。标明从一个顶点到另一个定点的距离或耗费。
带权的图称为网。
子网：设有两个图G = （V，{E}）、G1 = （V1，{E1}）,若V1∈V， E1∈E，则称G1是G的子图。
例如：（b）（c）是（a）的子图
连通分量（强连通分量）：无向图的极大连通子图称为G的连通分量
极大连通子图的意思是：该子图是G连通子图，将G的任何不在孩子图中的顶点加入，子图不再连通。
有向图G的极大强连通子图称为G的强连通分量。
极大强连通子图意思是：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通。
极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通
生成树：包含无向图G所有顶点的极小连通子图。
生成森林：对非连通图，由各个连通分量的生成树的集合
建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）
无向图的邻接矩阵是对称的
顶点i的度 = 第i行（列）中1的个数
有向图的邻接矩阵中：
第i行含义：以结点vi为尾的弧（即出度边）
第i列含义：以结点vi为头的弧（即入度边）
顶点的出度= 第i行元素之和。
顶点的入度=第i列元素之和
有向图的邻接矩阵可能是不对称的。
#define MaxInt 222222(一个很大的数)
#define MVNum 100//最大顶点数
typedef char VerTexType;
typedef struct{
VerTextType vexs[MVNum];//顶点表
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum. arcnum;//图的当前点数和边数
}AMGraph
采用邻接矩阵表示法创建无向图
算法思想：
Status CreateUDN(AMGraph &G){
//采用邻接矩阵表示法，创建无向网G
cin >> G.vexnum >> arcnum;//输入顶点数和总边数
for(int i = 0; i < G.vexnum;++i)
cin >> G.vexs[i];
for(int i = 0; i < G.vexnum; ++i)
for(int j = 0; j < G.vexnum; ++j)
G.arcs[i][j] = MaxInt;//边的权值置为最大值
for(int k = 0; k < G.arcnum;++k)
cin >> v1 >> v2 >> w;//输入一条边所依附的顶点及边的权值
i = LocateVex(G, v1);
j = LocateVex(G, v2);//确定v1和v2在G中的位置
G.arcs[i][j] = w;//边<v1,v2>的权值置为w
G.arcs[j][i] = G.arcs[i][j];//置<v1, v2>的对称边<v2, v1>的权值为w
return OK
}
int LocateVex(AMGraph G, VertexType u){
//图G种查找顶点u，存在则返回顶点表中的下标，否则返回-1
int i;
for(i = 0; i < G.vexnum; i++)
if(u == G.vexs[i]) return i
return -1;
}
typedef struct VNode{
VerTextType data;//顶点信息
ArcNode * firsarc;//指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum];//AdjList表示邻接表类型
//弧（边）的结点结构
#define MVNum 100//最大顶点数
typedef struct ArcNode{ //边结点
int adjvex;//改变所指向的顶点的位置
strcut ArcNode * nextarc;//指向下一条边的指针
OtherInfo info;//和边相关的信息
}ArcNode;
//图结构的定义
typedef struct{
AdjList vertices;
int vexnum, arcnum;//图的当前顶点数和弧数
}ALGraph;
ALGragh G;//定义了邻接表表示的图G
G.vernum = 6, G.arcnum = 6//图G之包含5个顶点。5条边
G.vertices[1].data = 'b'//图G中的第2个顶点是b
p = G.vertices[1].firstarc;//指针p指向顶点b的第一条边结点
p->adjvex = 4;//p指针所指边结点时到下标4的结点的边
算法思想
Status CreateUDG(ALGraph &G){//采用邻接表表示法，创建无向图G
cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
for(int i = 0; i < G.vexnum;++i){//输入各点，构造表头结点表
cin >> G.vertices[i].data;//输入顶点值
G.vertices[i].firstarc = NULL;//初始化表头结点的指针域
}
for(int k = 0; k < G.arcnum; ++k)//输入各边，构造邻接表
{
cin >> v1 >> v2;//输入一条边依附的两个顶点
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p1 = new ArcNode;//生成一个新的边结点*p1
p1 -> adjvex = j;//邻接点序号为j
p1 -> nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p1;//将新结点*p1插入顶点vi的边表头部
p2 = new ArcNode;//生成另一个对称的新的边结点p2
p2 -> adjvex = i;
p2 -> nextarc = G.vertices[j].firstarc;
G.vertices[j].first = p2;//将新结点*p2插入顶点vj的边表头部
}
return OK;
}
用途：邻接矩阵多用于稠密图，而邻接表多用于稀疏图
十字链表是有向图的另一种链式存储结构，我们可也可以把它看成是将有向图的链接表和逆邻接表结合起来形成的一种链表
有向图中的每一条胡对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点
遍历定义：从已给的连通图中某一顶点触发，沿着一些边访图中所有的顶点，且使乜咯顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。
遍历的实质：找每个顶点的邻接点的过程。
图的特点：图中可能存在回路，且图的任一顶点都看与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
图常用的遍历：
邻接矩阵表示的无向图深度优先遍历实现：
void DFS(AMGraph G, int v){//图G为邻接矩阵类型
cout << v;//访问第v个顶点
visited[v] = true;
for(int w = 0; w < G.vexnum; w++)//依次检查邻接矩阵v所在的行
{
if(G.arcs[v][w] != 0 && (!visited[w]))
DFS(G,w);//w是v的邻接点，如果w未访问，则递归调用DFS
}
}
用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O（n^2）
用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O（n+e）
结论：稠密图适用于在邻接矩阵上进行深度遍历。稀疏图时域在邻接表上进行深度遍历
方法：从图的某一结点出发，首先一次访问该结点的所有邻接点vi1,vi2,……vin,再按这些顶点被访问的先后次序依次访问与他们相邻接的所有违背访问的顶点。重复此过程，纸质所有顶点被访问为止。
按广度优先非递归遍历连通图G
void BFS(Graph G, int v){
cout << v; visited[v] = true;//访问第v分顶点
InitQueue(Q);//辅助队列Q初始化，置空
EnQueue(Q,v);//v进队
while(!QueueEmpty(Q)){//队列非空
DeQueue(Q, u);//队头元素出队并置为u
for(w = FirstAdjVex(G,u); w >= 0; w = NextAdjVex(G, u, w))
if(!visited[w])//w为u的尚未访问的邻接顶点
cout << w;
visited[w] = true;
EnQueue(Q,w);//进队
}
}
}
生成树：所有的顶点均有边连接在一起，但不存在回路的图
一个图可以有许多棵不同的生成树
所有的生成树具有以下共同特点
一个图中可以有许多不同的生成树。
含有n个顶点n-1条边的图不一定是生成树。
最小生成树：给定一个无向网络，在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树。也称最小代价生成树。
构造最小生成树的算法很多，其中多数算法都利用了MST性质
MST性质：设N = (V,E)是一个连通网，U是顶点集V的一个非空子集。若边（u,v）s是一条具有最小权值的边，其中u∈U，v属于V-U，则必存在一棵包含(u,v)的最小生成树。
在生成树的构造过程中，图中n个顶点分属两个集合：
已落在生成树上的顶点集:U
尚未若在生成树上的顶点集V-U
接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。
算法思想：
构造最小生成树方法二：克鲁斯卡尔（kruskal）算法
算法思想：
问题抽象：在有向网中A点（源点）到达B点（终点）的多条路径，寻找一条各边权值之和最小的路径，即最短路径。
最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边。
步骤：
有向无环图：无环的 有向图，简称DAG图
AOV网：用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网简称AOV网
AOE网：用一个有向图表示一个工程的各子工程及其相互制约的关系，以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，称为AOE网
在AOV网没有回回路的前提下，我们将全部活动排列成一个线性序列，使得若AOV网中有弧<i,j>存在，则在这个序列中,i一定排在j的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。
一个AOV网的拓扑序列不是唯一的。
检测AOV网中是否存在环方法：对该有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环
把工程计划表示为边表示活动的网络，即AOE网，同顶底表示事件，弧表示活动，弧的权表示活动持续时间
事件表示在他之前的活动已经完成，在它之后的活动可以开始。
关键路径——路径长度最长的路径
路径长度——路径上各活动持续时间之和
列，使得若AOV网中有弧<i,j>存在，则在这个序列中,i一定排在j的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。
一个AOV网的拓扑序列不是唯一的。
检测AOV网中是否存在环方法：对该有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环
把工程计划表示为边表示活动的网络，即AOE网，同顶底表示事件，弧表示活动，弧的权表示活动持续时间
事件表示在他之前的活动已经完成，在它之后的活动可以开始。
关键路径——路径长度最长的路径
路径长度——路径上各活动持续时间之和