图：图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)的集合。
1.有向图 若E是有向边（简称弧）的有限集合时，则G为有向图。弧是顶点的有序对，记为<v,w>，其中 v，w 是顶点，v 是弧尾，w 是弧头。称为从顶点v到顶点w的弧。 G1可表示为： G=(V,E) V={1,2,3} E={<1,2>, <2,1>, <2,3>}
2.无向图 若E是无向边（简称边）的有限集合时，则G为无向图。边是顶点的无序对，记为 (v,w) 或(w,v) ，且有 (v,w) =(w,v) 。其中 v，w 是顶点。 G2可表示为： G=(V, E) V={1,2,3,4} E={(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}
3.简单图和多重图 简单图满足以下两条内容： 1）不存在重复边 2）不存在顶点到自身的边 所以上面的有向图和无向图都是简单图。与简单图相对的是多重图，即：两个结点直接边数多于一条，又允许顶点通过同一条边与自己关联。
4.完全图 无向图中任意两点之间都存在边，称为无向完全图； 有向图中任意两点之间都存在方向向反的两条弧，称为有向完全图； 5.子图 若有两个图G=(V,E),G1=(V1,E2)，若V1是V的子集且E2是E的子集，称G1是G的子图。 图中G3是G1的子图。 6.连通、连通图、连通分量 在无向图中，两顶点有路径存在，就称为连通的。若图中任意两顶点都连通，同此图为连通图，否则为非连通图。无向图中的极大连通子图称为连通分量。 7.强连通图、强连通分量 在有向图中，从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通。若任一对顶点都是强连通的，称为强连通。有向图中极大强连通子图为有向图的强连通分量。 G1的强连通分量： 8.生成树和生成森林 连通图的生成树是包含图中全部顶点的一个极小连通子图，若图中有n个顶点，则生成树有n-1条边。所以对于生成树而言，若砍去一条边，就会变成非连通图。在非连通图中，连通分量的生成树构成了非连通图的生成森林。 G2的生成树： 9.顶点的度、入度和出度 顶点的度：以该顶点为一个端点的边的数目。 对于无向图，顶点的边数为度，度数之和是顶点边数的两倍。 对于有向图，入度是以顶点为终点，出度相反。有向图的全部顶点入度之和=出度之和=边数。顶点的度等于入度与出度之和。 注意：入度与出度是针对有向图来说的。
10.边的权和网 图中每条边上标有某种含义的数值，该数值称为该边的权值。 这种图称为带树图，也称作网。
11.路径、路径长度和回路 两顶点之间的路径指顶点之间经过的顶点序列，经过路径上边的数目称为路径长度。若有n个顶点，且边数大于n-1，此图一定有环。
12.简单路径、简单回路 顶点不重复出现的路径称为简单路径。 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
13.距离 若两顶点存在路径，其中最短路径长度为距离。
14.稠密图、稀疏图 稠密图：边数很少的图；反之为稠密图。
15.有向树 有一个顶点的入度为0，其余顶点的入度均为1的有向图称作有向树。如下图：
1.图的存储结构概述 对于图G=(V, E)来说，可以有两种标准的表示方法，一个是邻接矩阵，另一个是邻接链表，这两种方法都可以表示有向图和无向图。除此之外，图的存储结构还有十字链表、邻接多重表、边集数组等。
2.邻接矩阵法
（1）邻接矩阵：用两个数组来表示一个图，一个一维数组用来存储每个顶点的信息；一个二维数组（即邻接矩阵）用来存储图中的边或弧信息。对于图G =(V, E)来说，邻接矩阵matrix是一个|V|*|V|的方阵，假设1 <= i, j <= |V|，如果matrix[i][j] == 0，则表示顶点i和顶点j之间没有边相连；反之，如果matrix[i][j] != 0，则表示表示顶点i和顶点j之间有边相连，且matrix[i][j]存储的值即为该边的权重。
无权值图： 带权图： 有向图、无向图和网对应的邻接矩阵案例： （2）图的邻接矩阵存储结构
#define Maximum 1000 typedef int VexType; typedef int EdgeType; typedef struct { VexType Vex[Maximum]; EdgeType Edge[Maximum][Maximum]; int vexnum; int arcnum; }MGragh;（3）图的邻接矩阵存储表示的特点 3.邻接表法
（1）邻接表：邻接链表是一种不错的图存储结构，由于它在表示稀疏图的时候非常紧凑而成为通常的选择。对于图G =(V, E)来说，在其邻接链表表示中，每个结点对应一条链表，因此这个图里有V条链表。假设用一个V维的数组Adj来存储这V条链表，且Adj[i]表示的是结点i对应的链表，那么Adj[i]这条链表里存储的就是所有与节点i之间有边相连的结点，即与结点i相邻的结点。 邻接表中存在两种结点：顶点表结点和边表结点。 无向图和有向图的邻接表的实例： （2）图的邻接表存储结构定义：
#define Maximum 1000 typedef struct ArcNode{ int adjvex; int weight;//权值 ArcNode* next; }ArcNode; typedef struct VNode{ int data; ArcNode* first; }VNode,AdjList[Maxinum]; typedef struct ALGragh{ AdjList vertices; int arcnum,vernum; }ALGragh;（3）图的邻接表存储方法的特点： 4.十字链表（针对有向图邻接链表的优化）
（1）十字链表：对于有向图而言，邻接链表的缺陷是要查询某个顶点的入度时需要遍历整个链表，而逆邻接链表在查询某个顶点的出度时要遍历整个链表。为了解决这些问题，十字链表将邻接链表和逆邻接链表综合了起来，其基本思想就是在邻接链表的出边表的基础上，增加一个入边表。 弧结点五个域分别表示的是：尾域、头域、指向弧头相同的下一条弧、指向弧尾相同的下一条弧、弧信息； 顶点结点三个域分别表示的是：顶点相关的数据信息、指向以该顶点为弧头的第一个弧结点、指向以该顶点为弧尾的第一个弧结点。
（2）十字链表案例： 5.邻接多重表
（1）邻接多重表：对于无向图而言，其每条边在邻接链表中都需要两个结点来表示，而邻接多重表正是对其进行优化，让同一条边只用一个结点表示即可。邻接多重表仿照了十字链表的思想，对邻接链表的边表结点进行了改进。 边结点： 顶点结点： data：存储该顶点相关信息；firstedge：指示第一条依附于该顶点的边。
（2）邻接多重表的案例： 6.图的基本操作
1.广度优先搜索（BFS）
（1）思想：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
（2）算法特点 广度优先搜索类似于树的层次遍历，是按照一种由近及远的方式访问图的顶点。在进行广度优先搜索时需要使用队列存储顶点信息。
（3）算法伪代码：
package com.hunter.Graph; import java.util.LinkedList; import java.util.Queue; public class graphBFS { public void BFSraverse(Gragh G){ Queue<Integer> que= new LinkedList<Integer>(); boolean[] visited = new boolean[gh.numVexs]; for(int i = 0; i < G.Vexnum; i++) visited[i] = false; for(int i = 0; i < G.Vexnum; i++){ if(!visited[i]){ BFS(G,i); } } } void BFS(Gragh G,int v){ visit(v); visited[v] = true; System.out.println("正在访问的节点是 ：" + G.vexs[i]); que.add(v);//入队 while(!que.isEmpty()){ v=que.remove(); //出队 for(w=FirstNeighbor(G,v);w>=0;w=nextNeighbor(G,v,w)){ if(!visited[w]){ visit(w); visited[w]=true; que.add(w); } } } } }（4）案例：
（1）选取A为起始点，输出A，A入队列，标记A，当前位置指向A。
（2）队列头为A，A出队列。A的邻接顶点有B、E，输出B和E，将B和E入队，并标记B、E。当前位置指向A。
（3）队列头为B，B出队列。B的邻接顶点有C、D，输出C、D，将C、D入队列，并标记C、D。当前位置指向B。
（4）队列头为E，E出队列。E的邻接顶点有D、F，但是D已经被标记，因此输出F，将F入队列，并标记F。当前位置指向E。
（5）队列头为C，C出队列。C的邻接顶点有B、D，但B、D均被标记。无元素入队列。当前位置指向C。
（6）队列头为D，D出队列。D的邻接顶点有B、C、E，但是B、C、E均被标记，无元素入队列。当前位置指向D。
（7）队列头为F，F出队列。F的邻接顶点有G、H，输出G、H，将G、H入队列，并标记G、H。当前位置指向F。
（8）队列头为G，G出队列。G的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向G。
（9）队列头为H，H出队列。H的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向H。
（10）队列空，则以A为起始点的遍历结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。
（5）BFS算法求解单源最短路径问题
void BFS_distance(Gragh G,int u){ for(i=0;i<G.vexnum;i++){ d[i]=integer.Max; } visited[u]=trueq; d[u]=0; EnQueue(Q,u); while(!isEmpty()){ DeQueue(Q,u); for(w=FirstNeighbor(G,v);w>=0;w=nextNeighbor(G,v,w)){ if(!visited[w]){ visited[w]=true; d[w]=d[u]+1; DeQueue(Q,w); } } } }（6）广度优先生成树 2.深度优先搜索（DFS）
（1）深度优先搜索 思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
（2）特点 深度优先搜索是一个递归的过程。首先，选定一个出发点后进行遍历，如果有邻接的未被访问过的节点则继续前进。若不能继续前进，则回退一步再前进，若回退一步仍然不能前进，则连续回退至可以前进的位置为止。重复此过程，直到所有与选定点相通的所有顶点都被遍历。
（3）算法伪代码：
package com.hunter.Graph; public class graphDFS { public void DFSraverse(Graph G){ //初始化visited数组，用 false 以表示该顶点是否已经访问过 boolean[] visited = new boolean[G.numVexs]; for(int i = 0; i < G.numVexs; i++){ visited[i] = false; } System.out.println(); for(int i = 0; i < G.numVexs; i++){ if(!visited[i]) DFS(G,i,visited); } } private void DFS(graph gh, int k,boolean[] visit) { // TODO Auto-generated method stub visit[k] = true; System.out.println("正访问的结点是 ： " + G.vexs[k]); for(w=FirstNeighbor(G,v);w>=0;w=nextNeighbor(G,v,w)){ if(G.arc[k][i] == 1 && !visit[i]) DFS(G,i,visit); } } }（4）案例：
（1）首先选取顶点A为起始点，输出A顶点信息，且将A入栈，并标记A为已访问顶点。
（2）A的邻接顶点有C、D、F，从中任意选取一个顶点前进。这里我们选取C顶点为前进位置顶点。输出C顶点信息，将C入栈，并标记C为已访问顶点。当前位置指向顶点C。
（3）顶点C的邻接顶点有A、D和B，此时A已经标记为已访问顶点，因此不能继续访问。从B或者D中选取一个顶点前进，这里我们选取B顶点为前进位置顶点。输出B顶点信息，将B入栈，标记B顶点为已访问顶点。当前位置指向顶点B。
（4）顶点B的邻接顶点只有C、E，C已被标记，不能继续访问，因此选取E为前进位置顶点，输出E顶点信息，将E入栈，标记E顶点，当前位置指向E。
（5）顶点E的邻接顶点均已被标记，此时无法继续前进，则需要进行回退。将当前位置回退至顶点B，回退的同时将E出栈。
（6）顶点B的邻接顶点也均被标记，需要继续回退，当前位置回退至C，回退同时将B出栈。
（7）顶点C可以前进的顶点位置为D，则输出D顶点信息，将D入栈，并标记D顶点。当前位置指向顶点D。
（8）顶点D没有前进的顶点位置，因此需要回退操作。将当前位置回退至顶点C，回退同时将D出栈。
（9）顶点C没有前进的顶点位置，继续回退，将当前位置回退至顶点A，回退同时将C出栈。
（10）顶点A前进的顶点位置为F，输出F顶点信息，将F入栈，并标记F。将当前位置指向顶点F。
（11）顶点F的前进顶点位置为G，输出G顶点信息，将G入栈，并标记G。将当前位置指向顶点G。
（12）顶点G没有前进顶点位置，回退至F。当前位置指向F，回退同时将G出栈。
（13）顶点F没有前进顶点位置，回退至A，当前位置指向A，回退同时将F出栈。
（14）顶点A没有前进顶点位置，继续回退，栈为空，则以A为起始的遍历结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。
（15）采用深度优先搜索遍历顺序为A->C->B->E->D->F->G。
（5）深度优先的生成树和生成森林 3.图的遍历与图的连通性 图的遍历算法可以用来判断图的连通性。
图的应用主要包括：最小生成树、最短路径、拓扑排序、关键路径。
1、最小生成树：普里姆算法(Prim)、克鲁斯卡尔算法(Kruskal)
（1）性质 （2）Prim算法
普里姆算法构造最小生成树的过程： （3）Kruskal算法
克鲁斯卡尔算法构造最小生成树的过程： 2、最短路径 最短路径：当图是带权图时，把从一个顶点Vo 到图中其余任意一个顶点Vi 的一条路径所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最小的那条路径称为最短路径。
最短路径分为两类： （1）单源最短路径，通过迪杰斯特拉算法求解； （2）求每对顶点间的最短路径，通过弗洛伊德算法求解；
（1）Dijkstra算法求单源路径最短问题（贪心算法）
案例： 求解过程： 执行过程： （2）Floyd算法求各顶点之间最短路径问题
案例： 算法执行过程： 3、有向无环图描述表达式
案例： 二叉树描述表达式和有向无环图描述表达式对比： 4、拓扑排序
(1）AOV网：若用DAG图表示一个工程，其顶点表示活动，用有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，记为AOV网。
(2）拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序： 1）每个顶点出现且只出现一次； 2）若A在序列中排在B的前面，则在图中不存在从B到A的路径。
(3）拓扑排序步骤： (4）拓扑排序算法的实现：
bool topsortSort(Gragh G) { InitStack(S); for(int i=0;i<G.vernum;i++) { if(indegree[i]==0) push(S,i); } int count=0; while(!isEmpty(S)) { pop(S,i); print[count++]=i; for(p=G.vertices[i].firstarc;p!=NULL;p=p->nextarc) { int k=p->adjvex; indegree[k]–-; if(indegree[k]==0) push(S,k); } } if(count<G.vernum){ return false; } else return true; }(5）逆拓扑排序： (6）拓扑排序处理AOV网时的注意事项： 5、关键路径
（1）AOE网：AOE网是一个表示工程的带权有向图，其中的顶点用来表示某个事件，弧用来表示活动，弧上的权值用来表示活动持续的时间。
（2）AOE网和AOV网的区别： AOV网：其顶点用来表示活动。AOE网是用来表示活动之间的制约关系。 AOE网：顶点表示事件，边表示活动，边上的权值用来表示活动持续的时间。AOV网是用来分析工程至少需要花多少时间完成，或是为了缩短时间需要加快哪些活动等问题。
（3）AOE网的两个性质： （4）关键路径、关键活动 在AOE网中，从源点到汇点具有最大长度的路径称为关键路径，在关键路径上的活动称为关键活动。
1.事件的最早发生时间：ve[k] 2.事件的最迟发生时间：vl[k] 3.活动的最早发生时间：e[i] 4.活动的最迟发生时间：l[i] 5.求关键路径的算法步骤： 6.关键路径的注意事项：
