图的基本定义与基本术语
基本概念
图（Graph）是由顶点的集合和顶点之间边的集合组成，通常表示为：
G（V，E）
其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。在图中的数据元素，我们称之为顶点（Vertex），顶点集合有穷非空。在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。图是非常复杂的非线性结构，表达能力强。
图有有向图，无向图，连通图，强连通图，完全图，赋权图，稀疏图，稠密图多种类型。
权（Weight）：与图的边或弧相关的数。
网（Network）：带权的图。
子图（Subgraph）：假设G=（V,{E}）和G‘=（V',{E'}），如果V'包含于V且E'包含于E，则称G'为G的子图。
度（Degree）：无向图中，与顶点V相关联的边的数目。有向图中，入度表示指向自己的边的数目，出度表示指向其他边的数目，该顶点的度等于入度与出度的和。
路径的长度：一条路径上边或弧的数量。
连通图：图中任意两个顶点都是连通的，仅需要调用一次搜索过程，即从任一个顶点出发，便可以遍历图中的各个顶点。
非连通图：需要多次调用一次搜索过程，而每次调用得到的顶点访问序列恰为各连通分量的顶点集。调用搜索过程的次数就是该图连通分量的个数。
连通分量：无向图中的极大连通子图。（子图必须是连通的且含有极大顶点数）。图1有两个连通分量
强连通分量：有向图中的极大强连通子图。
生成树：无向图中连通且n个顶点n-1条边叫生成树。
有向树：有向图中一顶点入度为0其余顶点入度为1。
森林：一个有向图由若干棵有向树构成生成森林。
图的存储结构
邻接矩阵：边的集合，用两个数组，一个数组保存顶点集，一个数组保存边集
邻接表（数组与链表相结合的存储方法），十字链表，邻接多重表：链接方式
邻接矩阵n*n和邻接表（邻接表只存有用信息，表头和边表，方便定位）最常用的储存结构，适用于有向图（网）无向图(网)表示与处理
图的遍历
遍历
1 设置访问标识数组，以走遍所有顶点，防止走回路
2 遍历规律及支撑技术（可用邻接矩阵和邻接表实现）
深度优先 （递归） -- 类似树的先序遍历
从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。
# 图的深度优先遍历# 1.利用栈实现# 2.从源节点开始把节点按照深度放入栈，然后弹出# 3.每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈# 4.直到栈变空 DFS(u) for each neighbor v of u if v is unvisited, tree edge, DFS(v) else if v is explored, bidirectional/back edge else if v is visited, forward/cross edge广度优先（队列）-- 类似于树的层次遍历
图的应用
图的遍历算法是图应用的重要基础。
求解生成树，最小生成树，连通分量，拓扑排序，关键路径，单源最短路径及所有顶点之间最短路径的重要算法应用。
4.1 图的连通性问题--遍历的直接应用
1 无向图的连通分量
2 两顶点之间的简单路径
3 生成树
4 最小生成树
最小生成树：构造连通网的最小代价生成树。
重要性质：设N={V,{E}}是一个连通网，U是顶点集V的一个非空子集。若(u，v）是一条具有最小权值的边，其u∈U ，v∈V-U,则存在一颗包含边(u，v）的最小生成树。
反证法证明最小生成树的性质：
假设不存在这样一颗包含边(u，v）的最小生成树。任取一颗最小生成树T，将(u，v）加入T中。根据数的性质，此时T中必形成一个包含(u，v）的回路，且回路中必有一条边(u'，v'）的权值大于或者等于(u，v）的权值。删除(u，v），则得到一颗代价小于等于T的生成树T',且T'为一颗包含边(u，v）的最小生成树，这与假设矛盾。
普里姆（prime）：
第一种：
先将一个起点加入最小生成树，之后不断寻找与最小生成树相连的边权最小的边能通向的点，并将其加入最小生成树，直至所有顶点都在最小生成树中。
第二种：
1.将一个图的顶点分为两部分，一部分是最小生成树中的结点（A集合），另一部分是未处理的结点（B集合）。
2.首先选择一个结点，将这个结点加入A中，然后，对集合A中的顶点遍历，找出A中顶点关联的边权值最小的那个（设为v），将此顶点从B中删除，加入集合A中。
3.递归重复步骤2，直到B集合中的结点为空，结束此过程。
4.A集合中的结点就是由Prime算法得到的最小生成树的结点，依照步骤2的结点连接这些顶点，得到的就是这个图的最小生成树。
本来应该v1->v5是无穷大，通过修正改为v3->v5
克鲁斯卡尔（kluskal）:在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。
4.2 有向无环图的应用
1 拓扑排序
2 关键路径
求拓扑排序的基本思想：有向无环才可求拓扑序列
1 从有向图中选一个无前驱的顶点输出，
2 将此顶点和以它为起点的弧删除
3 重复1 2直至不存在无前驱的顶点，
4 若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。
基于邻接矩阵表示的存储结构，
A为有向图G的邻接矩阵，则有
1 找栈中无前驱的顶点--在A中找到值全为0的列。
2 删除以i为起点的所有弧--将矩阵中i对应的行全部置为0
算法步骤为
1 取1作为第一新序号
2找一个未编号的，值全为零的列j，若找到，则转到3；否则所有的列全部都编 过号，拓扑排序结束；若有列为曾被编号，则该图中有回路
3 输出列号对应的顶点j，把新序列号赋给所找到的列，
4 将矩阵中既对应的行全部置为零，
5 新序列加1，转2
基于邻接表的存储结构
入度为零的顶点即没有前驱的顶点，因此我们可以附设一个存放各顶点入度的数组indegree[]，于是有
1 找G中无前驱的顶点--查找indegree[i]为零的顶点vi，
2 删除以i为起点的所有弧--对链在顶点i后面的所有连接顶点k，可以将对应的indegree[k]减1。
关键路径
AOE网
在AOE--网中的基本概念
几个重要的定义，
求光线路径的基本步骤，
修改后的拓扑排序算法，
求关键路径的实现算法。
修正的拓扑排序算法
增加T栈增加ve，事件发生最早时间，初始化数组为0，计算结束保存在T栈
邻接表求关键路径--拓扑排序主要是为解决一个工程能否顺序进行的问题，但有时我们还需要解决工程完成需要的最短时间问题。增加了weight域，用来存储弧的权值。
求关键路径的基本步骤：
1 对途中顶点进行拓扑排序，在排序过程中按拓扑排序求出每个事件的最早发生时间etv
2 按逆拓扑序列求每个事件的最晚发生时间ltv
3 求出每个活动ai的最早开始时间ete和最晚发生时间lte
4 找出e（i）=I（i）的活动ai，即为关键活动
if语句如果求出一个最早发生时间则返回ok
栈循环套的while顺着边表进行循环，把所有和该点有关联的点最迟发生时间求出来
for(j=0;j<G.vexnum;j++)// 求ei，li和关键活动 { p=G.vextex[j],firstarc; while(p!=NULL) { k=p->Adjvex; dut=p->weight; ei=ve[j]; li=vl[k]-dut; tag=(ei==li)? ' * ' : ' ' ; printf("%c,%c,%d,%d,%d,%c\n",G.vertex[j].data,G.vertex[k].data,dut,ei,li,tag);// 输出关键活动 p=p->nextarc; } return(ok); }4.3 最短路径
一顶点到其余个顶点最短路径，可用一维数组表示
迪杰斯特拉算法（Dijkstra）：下一条最短路径或者是弧（v0，vx），或者是中间经过S中的某些顶点，而后到达vx的路径。
反证法证明：
假设下一条最短路径上有一个顶点vy不在S中，即此路径为（v0，……，vy，……vx）。显然（v0，……，vy）的长度小于（v0，……，vy，……vx）的长度，故下一条最短路径应为（v0，……，vy），这与假设的下一条最短路径（v0，……，vy，……vx）相矛盾！因此，下一条最短路径上不可能有不在S中的顶点vy,即假设不成立。
把图中的顶点集合V分成两组，第一组为已求出最短路径的顶点集合S（初始时S中只有源节点，以后每求得一条最短路径，就将它对应的顶点加入到集合S中，直到全部顶点都加入到S中）；第二组是未确定最短路径的顶点集合U。
算法步骤： （1）初始化，g为用邻接矩阵表示的带权图，S只含有源节点S<--{v0},dist[i]=g.arcs[v0][vi]，将v0到其余顶点的路径长度初始化为权值； （2）从U中选取一个距离v最小的顶点k加入S中（该选定的距离就是v到k的最短路径长度）使得dist[vk]= min( dist[i] | vi∈V-S ),vk为目前求得的下一条从v0出发的最短路径的终点； （3）以k为新考虑的中间点，修改U中各顶点的距离；若从源节点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短（dist[k] + g.arcs[k][i] <dist[i]，则则修改顶点u的距离值，修改后的距离值是顶点k的距离加上k到u的距离；(将dist[i]修改为dist[k] = g.arcs[k][i] )
（4）重复步骤（2）和（3）n-1次，按照最短路径长度递增的顺序，诸葛求出v0到图中其他顶点的最短路径，直到终点在S中。
ShortestPath_DJS(AdjMatrix g ,int v0 ,WeightType dist[MAX_VERTEX_NUM]) /*存放i的当前最短路径长度*/ ,VertexSet path[MAX_VERTEX_NUM]) /*存放i的当前最短路径*/ { VertexSet s; /*s为已经找到的最短路径的终点集*/ for(i=0;i<g.vexnum;i++) { InitList(&path[i]);// 路径数组的初值 dist[i]=g.arcs[v0][i];// 从i= 1到顶点个数个每次都把v0【i】放在数组的距离初值第i列 if(dist[i]<MAX) { AddTail(&path[i] , g.vexs[v0]); AddTail(&path[i] , g.vexs[i]); InitList(&s); AddTail(&s , g.vexs[v0]); } } for(t = 1;t<g.vexnum-1;t++)// t=1->n-1在不属于s中的顶点去选择 { Min=MAx; // 记下最小值的下标位置和值，第一个for进行第二步选vk for(i=0;i<g.vexnum;i++) if(!Member(g.vex[i].s)&&dist[i]<min) { K=i; Min=dist[i]; } AddTail(&s ,g.vexs[k]); // for循环进行修正 ，更新距离数组，路径数组也更新 for(i=0;i<g.vexnum;i++) { if(!Member(g.vex[i].s)&&dist[k]+g.arcs[k][i]<dist[i]) { dist[i]=dist[k]+g.arcs[k][i]; path[i]=path[k]; AddTail(&s ,g.vexs[i]); /*path[i]=path[k]∪{Vi}*/ } } } }弗洛伊德算法（Floyd）：
1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
经过n次比较和修正，在第(n-1)步，将求得的vi到vj的且中间顶点号不大于n-1的最短路径，这必是从vi到vj的最短路径。
ShortestPath_Floyd(AdjMatrix g ,WeightType dist [MAX][MAX],VertexSet path[MAX] [MAX]) {// 经过i j双循环初始化工作，得到初始状态 for(i=0;i<g.vexnum;i++) for(j=0;j<g.vexnum;j++) { InitList(&path[i][j]); // 初始化dist[i][j]和path[i][j]，d p两个数组都是n*n的 dist[i][j]=g.arcs[i][j]; if(dist[i][j]<MAX) { AddTail(&path[i][j] , g.vexs[i]); AddTail(&path[i][j] , g.vexs[j]); } for(k=0;k<g.vexnum;k++) for(i=0;i<g.vexnum;i++) for(j=0;j<g.vexnum;j++) if(dist[i][k]+dist[k][j]<dist[i][j]) { // 矩阵阵列经过中间顶点不大于k可达的最小值，进行修正 dist[i][j]=dist[i][k]+dist[k][j]; Path[i][j]=JoinList(path[i][k] , path[k][j]); } } }
求距离顶点v0的路径长度为k的所有顶点
已知无向图g设计算法求距离顶点为零的最短路径长度v0的所有顶点，要求尽可能的节省时间。
问题分析：
从顶点v0开始进行广度优先搜索,将一步可达的，两步可达的，直至k步可达的所有顶点记录下来，同时用一个队列记录每个节点的称号输出，第k+1层的所有结点即为所求。
Void bfsKLevel (Graph g , int v0 int K) { InitQueue(Q1); /*Q1是存放已访问顶点的队列*/ InitQueue(Q2); /*Q2是存放已访问顶点层号的队列*/ for(i=0;i<g.vexnum;i++) Visited[i]=FALSE; /*初始化访问标志数组*/ Visited[v0]=TRUE; Level=1; EnterQueue(Q1, v0); EnterQueue(Q2 Level); While(! IsEmpty(Q1)&& Level<K+1) { V=DeleteQueue(Q1); /*取出已访问的顶点号*/ Level=DeleteQueue(Q2); /*取出已访问的顶点层号*/ W=firstAdjVertex(g , v); /*找到第一个领节点*/ While(w!=-1) { If(!visited[w]) { If(Level==K) printf(“%d”,w); /*输出符合条件的节点*/ Visited[w]=TRUE; EnterQueue( Q1 w); } W=NextAdjVertex(g, v ,m); /*找下一个邻节点*/ } } }层次遍历二叉树
算法思想
1 初始化空队列Q;
2 若二叉树bt为空数，则直接返回;
3 将二叉树的根结点指针bt放入队列Q，
4 若队列非空，则重复如下操作:
队头元素出队并访问该元素；
若该结点的左孩子非空，则该结点的左孩子结点指针入队，
若该结点的右孩子非空，则该结点的右孩子结点指针入队。
支撑方法--队列
层次遍历是指从二叉树的第一层（根结点）开始逐层遍历，同一层中按照从左到右对节点访问，直到二叉树中所有结点均被访问且仅访问一次。
实现层次遍历需采用队列技术
设置一个队列Q，暂存某存已经访问过的结点，同时也保存了该层节点访问的先后次序，按照该层节点访问的次序实现对其下层孩子节点的按次序访问。
