图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

（1）在线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图数据元素称之为顶点（Vertex）。

（2）线性表中可以没有数据元素，称之为空表。树中可以没有结点称之为空树。对于图，图中不能没有顶点。强调顶点集合有穷非空。

（3）线性表中，相邻的两点之间具有线性关系，树结构中，相邻两层的结点具有等次关系。而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示。边集可以是空的。

         无向边：若顶点vi到vj之间的边没有方向，则称这条边为无向边（edge），用无序偶对（vi，vj）来表示。

         有向边：若顶点vi到vj之间的边有方向，则称这条边为有向边，也称为弧（Arc）。用有序偶对来表示，vi称为弧尾（Tail），vj称为弧头（Head）。如果图中任意两个顶点之间都是有向边，则称该图为有向图。

  在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。

   在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。

   在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。

有很少条边的图称为稀疏图，反之称为稠密图。

与图的边或弧相关的数叫作权（weight），这种带权的图通常称为网（Network）。

    假设有两个图G（V，{E}）和G1=（V1，{E1}），如果V1包含于V，且E1包含于E，则称G1位G的有向图。例子如下：

分别为无向图有其子图，和有向图及其子图。

对于无向图G，如果（v，v1）属于E，则称顶点v与v1互为邻接点，即v与v1相邻接

对于有向图G，如果弧属于E，则称顶点v邻接到v1，顶点v1邻接自顶点v。弧与顶点v、v1相关联，以顶点v为头的弧的数目称为v的入度（InDegree），记为ID（v），以v为尾的弧的数目称为v的出度（OutDegree），记为OD（v）；顶点v的度为TD（v）=ID（v）+OD（v）。即顶点的度为此顶点的入度加上出度。

无向图G中从顶点v到顶点v1的路径（Path）是一个·顶点序列

如下图为A到D的四种不同路径：

有向图的路径对方向严格要求。

路径的长度是路径上的边或弧的数目。

说的概念有些多，可能脑袋有些晕了吧。我们在来整理下所有的定义与术语。

图的定义与术语总结：

图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧头和弧尾之分。

图按照边或弧的多少分为稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。

图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫作度，有向图顶点分为入度和出度。

图上的边或弧上带权则称为网。

图中顶点之间存在路径，两顶点存在路径说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图。有向则称为强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称为强连通分量。

无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树，一个有向图由若干棵有向树构成生成森林。

        由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系，也就是说，图不可能用简单的顺序存储结构来表示。而多重链表的方式，即以一个数据域和多个指针域的结点表示图中的一个顶点，尽管可以实现图结构，但是以这种结构，如果各个结点的度数相差很大，按度数最大的顶点设置结点结构会造成很多存储单元的浪费，而若按每个顶点自己的度数设计不同的顶点结构，又带来操作的不便。如何实现物理存储是个难题。下面介绍前辈们提供的五种不同的存储结构。

1 、邻接矩阵

       图的邻接矩阵存储方式使用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

接下来分享几个实例来学习邻接矩阵

       从这个例子我们可以清楚的知道arc[i][j]=0说明顶点vi与vj之间没有边，若arc[i][j]=1说明顶点vi与vj之间有边。由于是无向图，所以无向图的邻接矩阵是对称矩阵即vi到vj有边，那么vj到vi也有边。

       如果我们要知道图中某个顶点的度那么只要将该顶点对应的行（或列）的元素值加起来，就是该顶点的度。

下面在来看一个有向图的例子：

如果arc[i][j]=0表示vi到vj不存在弧,arc[i][j]=1表示vi到vj存在弧。

有向图讲究入度与出度，某个顶点的入度为该顶点对应的列上所有元素之和，某个顶点的出度为该顶点对应的行上的所有元素之和。该顶点入度加上出度就是该顶点的度。

下面例看一个有向网图的例子：

这里用∞表示一个不可能的极限值用来代表不存在。

下面是图的邻接矩阵的结构定义：

2、邻接表

邻接表示不错的一种图的存储结构，但是我们发现对于边数相对顶点较少的图，这种结构时存在对存储空间的极大浪费。如我们要处理像下图这样的稀疏有向图：  

除了一条弧有权值外，没有其他弧，那么这就造成了存储空间的极大浪费。

这里我们采取了邻接表的存储方式。邻接表就是把数组与链表相结合的存储方法。

邻接表处理步骤如下：

1.图中顶点用一维数组存储，另外每个数据元素还需存储指向第一个邻接点的指针，以便于查找该顶点的信息。

2.图中每个顶点的vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储。无向图称为顶点vi的边表，有向图则称为vi作为弧尾的出边表。

下面举个无向图的邻接表的例子：

由这个例子知道顶点表的各个结点由data域和firstedge域（指针域）两个域表示。data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域用来存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。

若是有向图，邻接表结构同样类似，不过有向图有方向，所以有向图有邻接表与逆邻接表两种方式，看如下例子：

当然我们可以建立一个有向图的逆邻接表，即对每个顶点都建立一个以顶点vi都建立一个以vi为弧头的表，上例的逆邻接表如下：

此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。

对于带权值的网图，可以在边表结点中再定义一个weight的数据域，存储权值信息即可。

下面给出图的邻接表结构的定义：

3、十字链表

对于有向图来说，邻接表是有缺陷的，只知道出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。为了解决这个问题，我们要引出有向图的一种存储方法：十字链表。

实质上，十字链表就是将邻接表与逆邻接表结合起来。

我们需要重新定义顶点表结构如下图：

其中firstin表示入边表头指针，指向该顶点的入边表中的第一个顶点（相当于逆邻接表），firstout表示出边表头指针，指向该顶点的出边表中的第一个结点（相当于邻接表）。

重新定义边表结构如下：

其中tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的·下一条边，taillink是指向起点相同的下一条边。如果是网，还可以在增加一个weight域来存储权值。

下面来看一个例子：

上图中的虚线箭头其实就是该图的逆邻接表（入边（顶点做弧头））。实线就是该图的邻接表（出边（顶点做弧尾））。

有向图的十字链表存储方式代码如下：

4、邻接多重表

十字链表是对有向图的优化存储结构，对于无向图，如果我们关注的是顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已经访问的边做标记，删除某一条边等操作。那就意味，需要找到这条边的两个边表结点进行操作，显然这是比较麻烦的。

所以我们重新定义边表结点结构如下：  

其中ivex与jvex是与某条边依附的两个顶点在顶点表中下标。ilink是指依附顶点ivex的下一条边，jlink是指依附顶点jvex的下一条边。这就是邻接多重表结构。

看下面的例子：

此例中图中有4个顶点，五条边。然后依次按照顺序连线，当我们需要删除（v0，v2）这条边时，只需要将图中6和9的指针域置为空。

我想大家应该明白，邻接多重表与邻接表的区别，仅仅是在于同一条边在邻接多重表中用一个结点表示，而在邻接表中用两个边表结点表示。

5、边集数组

边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成。如下图是一个边集数组：

显然边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高，因此它更适合对边依次进行处理的操作。而不适合对顶点相关的操作。

图的遍历是和数的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。

树的遍历，毕竟根结点只有一个，遍历都是从根结点开始的。可图就复杂多了，因为它的任一顶点都可能和其余的所有顶点相邻接，极有可能存在沿着某条路径搜索后，又回到原点，而有些顶点确还没遍历到的情况。因此我们需要在遍历过程中把访问的顶点打上标记，以避免访问多次而不自知，具体办法是设置一个访问数组visited[n]，n是图中顶点个数，初值为0，访问过后设置为1。

对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通常有两种遍历次序方案：它们是深度优先遍历和广度优先遍历。

1、深度优先遍历

深度优先遍历（Depth_First_Search）,也称为深度优先搜索，简称DFS，它从图中某个顶点v出发，访问此顶点，然后从v未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相同的顶点都被访问到。这里我们将到的是连通图（任意两个顶点之间都有路径）

举个例子：

我们来走一遍这个例子，首先我们从A点出发，我们给自己定一个原则，在没有碰到重复顶点的情况下，始终向右手边走。于是我们依据右手通行原则，走到了B顶点，然后再走到了C顶点，继续走又走到了D顶点，接着又走到了E顶点，接着又走到F顶点，在F点我们发现右手边是A点，是已经访问过的点，于是我们走到了G顶点，在G点发现B、D两点都已经访问过了，于是走到H点，到了H点后发现没有没被访问过的点，退回到G点，G点也没有，所以退回F点，F点一样没有，所以退回到E点，E一样，再退回到D点，到了D点还有I点没有被访问过,走到I点，到了I点发现没有没被访问过的点，退回到D点，D点也没有，退回到C点，C点也没有，退回到B点，B点也没有，退回到A点。A点也没有。此时遍历过程结束。

通过这个例子应该可以清楚了深度优先遍历的步骤。本质上就是利用了递归。

下面是邻接矩阵的深度优先遍历操作代码：

我们通过代码可以看到，深度优先遍历就用到了递归。

2、广度优先遍历

广度优先遍历（Breadth_First_Search），又称为广度优先搜索，简称BFS。继续用上面深度优先遍历的例子。通过这个例子来说明广度优先遍历的过程原理。我们首先将图变形为下面：

实际上图中各个顶点和边的关系并没有发生变化，只是可以更直观的看整个过程。

首先，先将A点入队，A点访问过了，队列不为空，将A出队，然后将A未访问的邻接点B、F入队。此时队还不为空，将B出队，然后将B的未访问的邻接点C、I、G入队。队仍然不为空，将F出队，再将F的未访问邻接点E入队。队依然不为空，将C出队，然后把C的未访问的邻接点D入队。队依然不为空，将I出队，I没有未被访问的邻接点。此时队仍然不为空，将G出队，再将G的未访问邻接点H入队。然后队不为空E出队，E没有未被访问的邻接点。然后队依然不为空D出队，D没有未被访问的邻接点。然后队不为空H出队，H没有未被访问的邻接点。最后队为空。结束。

具体过程如下图：

广度优先遍历代码如下：

      我们把构造连通网的最小代价生成树称为最小生成树（Minimum Cost Spanning Tree），找连通网的最小生成树，经典的算法有两种，普里姆算法和克鲁斯卡尔算法。

1、普里姆（Prim）算法

普里姆算法理解起来十分困难，我这样解释或许会好点，adjvex与lowcost数组中的下标分别对应了该图中的顶点。普里姆算法就是选定一个起点（任一顶点）然后找到它的最小生成树，而adjvex数组就是我们选定的起点的邻接点表，假如我们选定下标为0的顶为我们的顶点，所以我们要将adjvex数组初始化为我们选定的顶点下标。即adjvex[i]=0。然后我们把lowcost[我们选定的起点下标]=我们选定的起点下标,即lowcost[0]=0，因为lowcost[任意下标]=起点下标，这说明下标为此的顶点任务完成，即lowcost[i] = 0表示第i个顶点加入到生成树中，即该顶点已经确定下来了。

然后将起点与除自身外的其他顶点的权值赋给lowcost中下标对应的数组元素，即将arc[0][j]赋给lowcost[j]，j是除过我们起点的所有点。

变量min用于存储lowcost数组中所有未加入生成树的顶点并且对应lowcost值最小的，即此条件lowcost[j]!=0&&locost[j]NumVexs; i++) { for (int j = 0; j < g->NumVexs; j++) { if (g->arc[i][j] != 0 && g->arc[i][j] != INFINITY) /*如果这条边存在且权值不为0*/ { e[n].weight = g->arc[i][j]; /*将权值赋给边集数组元素*/ e[n].begin = i; e[n].end = j; n++; /*边集数组下标*/ } } } } void Sort(Edge *e, int len) /*对边集数组根据权值进行排序（升序）*/ { for (int i = 0; i < len - 1; i++) { for (int j = 0; j < len - 1 - i; j++) { if (e[j + 1].weight < e[j].weight) { Edge t; t = e[j]; e[j] = e[j + 1]; e[j + 1] = t; } } } } int Find(int *p, int f) /*查询连线顶点的尾部下标*/ { while (p[f] > 0) { f = p[f]; } return f; }

克鲁斯卡尔算法的时间复杂度为O（eloge）e为边的数目。

1、最短路径的概念：

在网图和非网图中，最短路径的含义是不同的。由于非网图它没有边上的权值，所谓的最短路径，其实就是指两顶点经过的边数最少的路径；而对于网图来说，最短路径是指两顶点之间的边上权值之和最少的路径，并且我们称路径上的第一个顶点源点，最后一个顶点是终点。

下面介绍两个计算最短路径的算法，它们分别是迪杰斯特拉(Dijkstra)算法，弗洛伊德（Floyd）算法。

2、迪杰斯特拉(Dijkstra)算法

首先举个例子引出一点思路：

迪杰斯特拉算法是一个按路径长度递增的次序产生的最短路径算法。

如果你要求v0到v8之间的最短距离，根据迪杰斯特拉算法，我们不是一下子就能求出v0到v8的最短路径，而是要一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你想要的结果。

我们先放出代码供大家阅读，然后再对应起来讲解。

首先定义两个数组分别是：Pathmatrix数组、ShortPathTable数组，Pathmatrix就是一个并查集数组，Pathmatrix[i]=j表示v0到vi的最短路径（我们假定起点定位v0），vj是vi的前驱顶点，然后在通过vj又能找到vj的前驱结点，一直这样找下找到去，直到找到起点v0，这样就找到v0到vi的最短路径。

而另一个数组ShortPathTable[i]用来存放,起点到vi点的最短路径数。

然后在函数内部定义一个名为Final的数组，用该数组来标记每个顶点是否完成查找工作。如果数组元素Final[i]等于0表示还未找到v0到vi的最短路径，如果等于1表示找到了v0到vi的最短路径。

然后对Final数组初始化都为0，ShortPathTable[i]数组存放顶点v0到所有顶点vi的连线的权值。Pathmatrix数组全部初始化为0。并且对初始化D[0]=0，Final[0]=1,这表示v0自己到v0自己的最短路径已找到。

接下来除起点外的所有的进行查找。第一个循环，如果Final[w]=0并且D[w]j->w的距离小于v直接到w的距离，所以我们就让D[v][w]=D[v][j]+D[j][w]，并且接下来该使用P数组，使P[v][w]=P[v][j]即j顶点是v到w路径上的前驱矩阵。

然后我们来解读下弗洛伊德算法的实现代码：

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。

对AOV网进行拓扑排序的基本思路是：从 AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或AoV网中不存在入度为0的顶点。

我们需要为AOV网建立一个邻接表，考虑到算法过程中始终要查找入度为0的顶点，因此我们在原来的顶点表结点结构基础上，增加一个表示该顶点的入度的入度域（in），通过该结点的入度域，即可方便的知道此结点的入度。

AOV（activity on vertex ）网，顶点表示活动，弧代表活动（顶点）的制约关系

增加后的顶点结构如下：  

下面给出拓扑排序的代码及解析：

我们要定义一个变量count用来记录输出顶点的个数，然后定义一个栈s1，该栈用来存储入度为0的顶点的下标，我们用一个for循环将所有的入度为0的顶点压入栈s1中，然后在利用一个while循环，直到栈s1为空，弹出栈顶元素，然后根据弹出的top下标打印此结点，输出后数目count加1。接下来在一个for循环访问刚才弹栈的顶点top的边表域e，将在e边上的top顶点对应的邻接点k的入度减1，这个操作相当于删掉e边（实际并没有）,然后在判断k点的入度是否为0，是则将k压栈。

出了while循环后，需要判断输出的顶点数目是否与顶点数目相同，若不相同说明有环。

在前面讲了AOV网的基础上，来介绍一个新的概念AOE网，在一个表示工程的带权有向图中，用顶点表示事件，用弧表示活动，用弧上的权值表示活动持续时间，这种用有向图表示活动的网，我们称之为AOE网（activity on edge），把AOE网中没有入边的的顶点称为始点或源点，把没有出边的顶点称为终点或汇点。

下图为一个AOE网的例子：

我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点有最大的长度的路径叫关键路径，在关键路径上的活动叫关键活动

为了求出关键路径，我们需要定义如下几个参数： 1、事件的最早发生时间etv（earliest time of vertex）：即顶点vk的最早发生时间。

2、事件的最晚发生时间ltv（lastest time of vertex）：即顶点vk的最早发生时间。即每个事件的最晚需要开始的事件。

3、活动的最早开始时间ete（earliest time of edge）：即弧ak的最早发生时间。

4、活动的最晚开始时间lte（lastest time of edge）：即弧ak的最晚发生时间。

我们可以求出1，然后借助1求出2，然后再根据1、2可以求出3、4.

首先我们先给出关键路径算法的代码然后再分析：

如图已经求得了v5的最晚发生时间为ltv[5]=25;v6的最晚发生时间为ltv[6]=22;这时要求v4的最晚发生时间依据ltv[5]=25算得ltv[4]=16,依据ltv[6]=22算得ltv[4]=18,因为15weight。

然后进行判断如果该边（活动）的最早开始时间等于最晚开始时间，则说明该边（活动）在关键路径上，则将该边（活动）输出出。完成此循环过程后，算法结束。