数据结构-图
》一笔画：
-凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。
-凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。
》基本概念：
-图的抽象数据类型
ADT Graph{
数据对象V：数据元素的集合，顶点集。
数据关系R：R={VR}，VR={<v,w>|v,w∈V,且P(v,w),<v,w>表示从v到w的弧}。
基本操作:
CreateGraph(&G,V,VR) ; //构造图
DFSTraverse(G,V,visit()); //深度遍历图
BFSTraverse(G,V,visit()); //广度遍历图
-任意两个结点之间的关系是任意的，图中任意两个数据元素之间都可能相关。
-顶点：图的数据元素。
-V是顶点的集合，VR是两个顶点之间的关系的集合。
-有向图：<v,w>∈VR,v为弧尾、w为弧头。
-无向图：若<v,w>∈VR,必有<w,v>∈VR,用(v,w)表示。
-完全图：每一个顶点之间有且只有一条边的相连。
-无向完全图：有n(n-1)/2条边。
-有向完全图：有n(n-1)条弧。
-稀疏图：边或弧很少的图。
-稠密图：边或弧较多的图。
-子图：G=(V,{E}),G`=(V`,{E`})，若V`∈V,且E`∈ E,则称G`为G的子图。
-邻接点：对于无向图,若(v,v`)∈E,则称顶点v和v`互为邻接点，即v和v`相邻接,并称边(v,v`)关联于顶点v和v`，或称(v,v`)与顶点v和v`相关联。
-度：一个顶点v的度是与它相关联的边的条数，记做TD(v)。
-入度：是以v为终点的弧的条数，记做ID(v)。
-出度：是以v为始点的弧的条数，记做OD(v)。
-在一个图中，所有顶点的度数之和等于图的边数的2倍。
-在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。
-路径：图G=(V,E)中,若存在一个顶点序列(v=vi,0,vi,1,…,vi,m=v`),其中(vi,j-1,vi,j)均属于E，则称顶点vi到vj 存在一条路径。
-简单路径：若一条路径上除了vi 和vj 可以相同外,其余顶点均不相同，则称此路径为一条简单路径。
-简单回路（简单环）：起点和终点相同的路径称为简单回路或简单环。
-连通：在无向图G中,若两个顶点vi和vj之间有路径存在,则称vi和vj是连通的。
-连通图：若G中任意两个顶点都是连通的，则称G为连通图。
-连通分量：无向图的极大连通子图称为的连通分量。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。
-强连通图：有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。
-强连通分量：极大强连通子图叫做强连通分量。
-生成树：一个连通图的生成树是它的极小连通子图，含有图的全部顶点,在n个顶点的情形下，有n-1条边。
-不予讨论的图:包含顶点到其自身的边；一条边在图中重复出现。
》图的存储结构
#define INFINITY INT_MAX
#defineMAX_VERTEX_NUM 20
typedefenum{DG,DN,AG,AN} GraphKind;
typedefstruct ArcCell{
VRType adj;
InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct{
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
GraphKind kind;
}MGraph;
-数组表示法（邻接矩阵/顺序存储）：用两个数组分别存放顶点信息和边(弧)信息。
-图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。
-设图A = (V, E)是一个有n个顶点的图，则图的邻接矩阵是一个二维数组A .Edge[n][n]，定义：
-无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。
-在有向图中, 统计第i 行1 的个数可得顶点i 的出度，统计第j 列1 的个数可得顶点j 的入度。
-在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度。
-网络的邻接矩阵：可达用边的权值表示，不可达用正无穷表示。
-邻接表（链式存储）：图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边。
-逆邻接表：任一表头结点下的边结点的数量是图中该结点入度的弧的数量，与邻接表相反。
-图的邻接表反映的是节点的出度邻接情况，逆邻接表反映的是节点的入度邻接情况。
-有向图的邻接表中，第 i 个边链表链接的边都是顶点 i 发出的边。也叫做出边表。
-有向图的逆邻接表中，第 i 个边链表链接的边都是进入顶点 i 的边。也叫做入边表。
-表结点：由三个域组成：
>邻接点域(adjvex):指示与顶点vi邻接的点在图中的位置。
>链域(nextarc):指示下一条边(弧)的结点。
>数据域(info):存储和边(弧)相关的信息，如权值。
-网络的邻接表（带权图）
-邻接表（Adjacency List）
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
》图的遍历性
-图的遍历:从连通图中某一顶点出发访遍图中所有的顶点，且使每个顶点仅被访问一次。
-图的遍历目标：解决图的连通性问题、关键路径问题等。
-图的遍历方法：深度优先算法和广度优先算法。
-深度优先搜索DFS（Depth First Search）
注意：每个结点只能被访问一次，又因为一个结点可以和其它的任何结点相邻接，为了避免对一个结点的重复访问，必须对访问过的结点加以标记。结点的邻接结点的次序是任意的，因此深度优先搜索的序列可能有多种。深度优先搜索类似于树的前序遍历。
-访问方式：
(1)选中第一个被访问的结点。
(2)对结点作已访问过的标志。
(3)依次从结点的未被访问过的第一个、第二个、第三个……邻接结点出发，进行深度优先搜索。转向2。
(4)如果还有顶点未被访问，则选中一个起始结点，转向2。
(5)所有的结点都被访问到，则结束。
-图的深度遍历
Boolean visited[Max];
Status (*VisitFunc)(intv);
void DFSTraverse(GraphG, Status (*Visit) (int v)){
VisitFunc=Visit;
for(v=0;v<G.vexnum;++v) visited[v]=FALSE;
for(v=0;v<G.vexnum;++v)
if(!visited[v])DFS(G,v);
}//DFSTraverse
void DFS(Graph G, int v){
vistited[v]=TRUE; VisitFunc(v);
for(w=FirstAdjVex(G,v); w=NextAdjVex(G,v,w))
if(!visited[w]) DFS(G,w);
}//DFS
-广度优先搜索BFS（Breadth First Search）
注意：每个结点只能被访问一次，又因一个结点可以和其它的任何结点相邻接，为避免对一结点的重复访问，必须对访问过的结点加以标记。结点邻接结点的次序是任意的，因此广度优先搜索的序列可能有多种。广度优先搜索类似于树的从根出发的按层次遍历。
-访问方式：
(1)选中第一个被访问的结点V
(2)对结点V 作已访问过的标志
(3)依次从结点V 的未被访问过的第一个、第二个、第三个……第M个邻接结点W1、W2、W3……Wm ，且进行标记
(4)依次访问结点W1、W2、W3……Wm的邻接结点，且进行标记。
(5)如果还有结点未被访问，则选中一个起始结点，也标记为V，转向2。
(6)所有的结点都被访问到，则结束。
-图的广度遍历
void BFSTraverse(Graph G, Status (*Visit) (int v)){
for(v=0;v<G.vexnum;++v) visited[v]=FALSE;
InitQueue(Q);
for(v=0;v<G.vexnum;++v)
if(!visited[v]) {
EnQueue(Q,v);
while(!QueueEmpty(Q)){
DeQueue(Q,u);
vistited[u]=TRUE; Visit(u);
for(w=FirstAdjVex(G,u); w=NextAdjVex(G,u,w))
if(!visited[w]) EnQueue(Q,w);
}//while
}//if
}//BFSTraverse
》图的连通性
-连通图：仅需从任一顶点出发,进行深(广)度优先搜索，便可访问图中所有顶点。
-非连通图：利用深(广)度优先搜索算法，只能访问到该顶点所在的最大连通子图(连通分量)的所有顶点。
-生成树：极小连通子图。包含图的所有n 个结点，但只含图的n-1 条边。在生成树中添加一条边之后,必定会形成回路或环。
-生成方法：进行深度为主的遍历或广度为主的遍历，得到深度优先生成树或广度优先生成树。
-生成森林：在进行深度为主的遍历或广度为主的遍历时，对于非连通图，将得到多棵深度优先生成树或广度优先生成树。称之为生成森林。
》最小生成树（最小代价生成树）
-生成树中边的权值(代价)之和最小的树。
-MST 性质:
假设G = {V, {E}} 是一个连通图,U 是结点集合V 的一个非空子集。若(u,v) 是一条代价最小的边,且u 属于U,v 属于V –U,则必存在一棵包括边(u,v) 在内的最小代价生成树。
-实际应用：
把网络顶点看作城市，边的权看作连接城市的通讯线路成本，根据最小生成树建立的是城市间成本最低的通讯网。可类似考虑成本最低的公路网等
农村村庄之间的输电网络、有线电视网
输水管线、暖气管线、配送中心与线路的规划
-普里姆(Prim)算法(适合稠密图)
基本思想：
1. 从图G 的顶点集V 中任取一顶点(例取顶点v0) 放入集合U 中,这时U={v0},TE={ },(U,TE) 是树。
2. 在所有一个顶点在集合U 里另一顶点在集合V-U的边中,找出权值最小的边e=(u,v)(u∈U,v∈V-U),将顶点v加入集合U,将e 加入TE.(U,TE) 仍是一棵树。
3. 重复2,直至U=V(树中包含所有顶点)。这时TE 有n-1条边,T=(U,TE) 就是G 的一棵最小生成树算法直接利用MST 性质构造最小生成树。
-克鲁斯卡尔(Kruskal)算法（适合稀疏图）
基本思想：
设G = (V,E)是网络,构造最小生成树的过程：
1.初始状态是只有n个顶点而无边的非连通图T = (V,φ),T中每个顶点自成一个连通分量。
2.将E 中的边按递增顺序排列。构造中从小到大顺序选择两端点在T的两个不同连通分量的边e,把e加入T使这两个连通分量由于该边连接变成一个连通分量(每次操作,T 减少一个连通分量)。
3.不断加入新边,直到T所有顶点都在一个连通分量上为止,这个连通分量就是G的一棵最小生成树。
4.若不能得到一个连通分量,则图不连通,无最小生成树。
-按边权值递增
》最短路径
-问题的提出：
交通咨询系统、通讯网、计算机网络常要寻找两结点间最短路径；
交通咨询系统:A 到 B 最短路径；
计算机网络:发送Email节省费用 A到B沿最短路径传送；
-路径长度：路径上边数,路径上边的权值之和。
-最短路径：两结点间权值之和最小的路径。
-问题解法
-单源最短路径 — Dijkstra算法
对于给定的有向网G=（V，E），求源点v0到其它顶点的最短路径。Dijkstra提出了一个按路径长度递增的顺序逐步产生最短路径的方法，称为Dijkstra算法。
Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，以及执行算法过程中各步的状态。
-任意顶点对之间的最短路径 — Floyd算法
问题的提法：
已知一个各边权值均大于0的带权有向图，对每一对顶点vi不等于vj，要求求出vi与vj之间的最短路径和最短路径长度。
解决问题：
可以利用单源最短路径算法，具体做法是依次把有向网G中的每个顶点作为源点，重复执行Dijkstra算法n次，即执行循环体：总的时间复杂度为O(n3)。
for （v=0；v<g.n；v++）{
spath_dij（g，v，p，d）;
print_gpd（g，p，d）;
}
》AOV网与拓扑排序
-有向无环图：没有回路的有向图。
-AOV网（Activity On Vertex Network，顶点表示活动的网）：
用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网（Activity On Vertex Network)，简称AOV网。在网中，若从顶点i到顶点j有一条有向路径，则i是j 的前驱。
-拓扑排序
由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。
-拓扑排序过程
1)输入AOV网络。令 n 为顶点个数。
2)在AOV网络中选一个没有直接前驱(入度为0)的顶点, 并输出之;
3)从图中删去该顶点, 同时删去所有它发出的有向 边;
4)重复以上(2)、(3)步, 直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。