[部分内容由gpt自动生成]基本概念(摘自严蔚敏的教材)【定义】一个图(G)定义为一个偶对(V,E)，记为G=(V,E)。
其中： V是顶点(Vertex)的非空有限集合，记为V(G)；E是无序集V&V的一个子集，记为E(G) ，其元素是图的弧(Arc)。
其形式化定义为：G=(V ，E)V={v|v∈data object}E={<v,w>| v,w∈V∧p(v,w)}P(v,w)表示从顶点v到顶点w有一条直接通路。
弧(Arc) ：表示两个顶点v和w之间存在一个关系，用顶点偶对<v,w>表示。
通常根据图的顶点偶对将图分为有向图和无向图。
有向图(Digraph)： 若图G的关系集合E(G)中，顶点偶对<v,w>的v和w之间是有序的，称图G是有向图。
在有向图中，若 <v,w>∈E(G) ，表示从顶点v到顶点w有一条弧。
其中：v称为弧尾(tail)或始点(initial node)，w称为弧头(head)或终点(terminal node) 。
无向图(Undigraph)： 若图G的关系集合E(G)中，顶点偶对<v,w>的v和w之间是无序的，称图G是无向图。
在无向图中，若<v,w>∈E(G)，则<w,v>∈E(G)，即E(G)是对称，则用无序对(v,w)表示v和w之间的一条边(Edge)，因此(v,w) 和(w,v)代表的是同一条边。
例1：设有有向图G1和无向图G2，形式化定义分别是：(src: 严蔚敏教材)G1=(V1 ，E1)V1={a,b,c,d,e}E1={<a,b>,<a,c>, <a,e>,<c,d>,<c,e> ,<d,a>,<d,b>,<e,d>}G2=(V2 ，E2)V2={a,b,c,d}E2={(a,b), (a,c), (a,d), (b,d), (b,c), (c,d)}图中任意两个不同的顶点间都有一条无向边，这样的无向图称为完全无向图。
图中任意两个不同的顶点间都有一条弧，这样的有向图称为完全有向图。
有很少边或弧的图（e<n㏒n）的图称为稀疏图，反之称为稠密图。
权(Weight)：与图的边和弧相关的数。
权可以表示从一个顶点到另一个顶点的距离或耗费。
顶点的邻接(Adjacent)：对于无向图G=(V，E)，若边(v,w)∈E，则称顶点v和w 互为邻接点，即v和w相邻接。
边(v,w)依附(incident)与顶点v和w 。
对于有向图G=(V ，E)，若有向弧<v,w>∈E，则称顶点v “邻接到”顶点w，顶点w“邻接自”顶点v ，弧<v,w> 与顶点v和w“相关联”。
顶点的度、入度、出度：对于无向图G=(V，E)，vi∈V，图G中依附于vi的边的数目称为顶点vi的度(degree)，记为TD(vi)。
对有向图G=(V，E)，若vi∈V ，图G中以vi作为起点的有向边(弧)的数目称为顶点vi的出度(Outdegree)，记为OD(vi)；以vi作为终点的有向边(弧)的数目称为顶点vi的入度(Indegree)，记为ID(vi)。
顶点vi的出度与入度之和称为vi的度，记为TD(vi)。
即 TD(vi)=OD(vi)+ID(vi)路径(Path)、路径长度、回路(Cycle) ：对无向图G=(V，E)，若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。
对有向图G=(V，E)，从顶点vi到vj有有向路径，指的是从顶点vi经过若干条有向边(弧)能到达vj。
或路径是图G中连接两顶点之间所经过的顶点序列。
即(src:严蔚敏教材)路径上边或有向边(弧)的数目称为该路径的长度。
在一条路径中，若没有重复相同的顶点，该路径称为简单路径；第一个顶点和最后一个顶点相同的路径称为回路(环)；在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路(简单环)。
图的存储结构由于图G=(V,E)，是顶点和边的二元组。
因此在存储时，除了要存储边集E外，还要存储顶点集V。
一般情况下，顶点集V用顺序存储结构，而边集E则根据情况，采用顺序存储结构或者链式存储结构。
2.1 图的顺序存储结构边集E表示的是顶点之间的关系，因此用二维数组进行存储，也称为邻接矩阵(Adjacency Matrix)。
对于拥有n个顶点的图G，它的邻接矩阵是n*n的方阵，其中的元素定义为：下图展示了采用顺序存储结构表示的结果，包括了顶点集、边集的存储。
图的顺序存储——邻接矩阵 (src: https://blog.csdn.net/qq_40609809/article/details/96715357)typedef char Vertex[20]; typedef struct SeqGraph {Vertex *vertex; int c; int n_v; int *adjMatrix; int **fastAddr; } SeqGraph;int createSeqGraph(SeqGraph *g, int n);int insertVertexSeqGraph(SeqGraph *g, Vertex v);int insertEdgeSeqGraph(SeqGraph *g, Vertex u, Vertex v);void destroySeqGraph(SeqGraph *g);2.2 图的链式存储结构对图中的每个顶点vi都分别建立一个对应的单链表(对无向图称为“边表”，对有向图称为“出边表”）来存储所有邻接与顶点vi的边(对于有向图而言是指以vi为尾的弧)，边表中的每个结点分别对应于邻接于顶点vi的一条边。
边表中的每个结点主要包含两个域，其中邻接点域(adj_vex)指示与顶点vi邻接的点在图中的位置，链域(next_edge)指示下一条边或弧的结点。
如果是带权图，还可以再加一个域weight，表示从vi到adj_vex这条边的权值。
对于图中的所有顶点信息，用一个一维数组（称为"顶点表"）来存放。
对于顶点表中的每个顶点单元，需要存放:该顶点信息值(data)、一个指向由邻接于该顶点的所有的边组成的边表的头指针(first_edge)。
图的链式存储——邻接表 (src: https://blog.csdn.net/t11383/article/details/89073767)typedef char Vertex[20]; typedef struct AdjlinkedNode {int adjvex;struct AdjlinkedNode *next;}AdjlinkedNode;typedef struct linkedGraph {Vertex *vertex; int c; int n_v; AdjlinkedNode *adjHeaders;} linkedGraph;int createlinkedGraph(linkedGraph *g, int n);int insertVertexlinkedGraph(linkedGraph *g, Vertex v);int insertEdgelinkedGraph(linkedGraph *g, Vertex u, Vertex v);void destroylinkedGraph(linkedGraph *g);图的遍历图的遍历(Travering Graph)：从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次。
图的遍历算法是各种图的操作的基础。
图的任意顶点可能和其余的顶点相邻接，可能在访问了某个顶点后，沿某条路径搜索后又回到原顶点。
解决办法：在遍历过程中记下已被访问过的顶点。
设置一个辅助向量Visited[n](n为顶点数)，其初值为0，一旦访问了顶点vi后，使Visited[i]为1或为访问的次序号。
图的遍历算法有深度优先搜索算法和广度优先搜索算法。
3.1 深度优先搜索算法类似于二叉树的先序/中序/后序遍历，不同的地方在于：二叉树的结点只有固定的左右两个孩子，图的邻接点需要从邻接矩阵/邻接表中罗列出来。
void traverseSeqGraphInner(SeqGraph *g, int u, int visited[],int (*func)(Vertex v)){int v;if (visited[u] == 1) {return;}visited[u] = 1;func(g->vertex[u]);for(v=0; v<g->n_v; v++) {if (g->adjMatrix[u*g->c + v]>0) {traverseSeqGraphInner(g, v, visited, func);}}}void traverseSeqGraph(SeqGraph *g, int (*func)(Vertex v)){int i, *visited; visited = (int *)malloc(sizeof(int) * g->n_v);for(i=0; i<g->n_v; i++) {visited[i] = 0;}for(i=0; i<g->n_v; i++) {traverseSeqGraphInner(g, i, visited, func);}}3.2 广度优先搜索算法与树的广度优先遍历一样，需要通过队列来实现。
（代码略）图的生成树算法、最短路径算法为了介绍生成树的概念，先补充几个图相关的概念：子图和生成子图：设有图G=(V，E)和G’=(V’，E’)，若V’∈V且E’ ∈E ，则称图G’是G的子图；若V’=V且E’ E，则称图G’是G的一个生成子图。
生成树：一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树。
如果连通图是一个带权图，则其生成树中的边也带权，生成树中所有边的权值之和称为生成树的代价。
最小生成树(Minimum Spanning Tree) ：带权连通图中代价最小的生成树称为最小生成树。
4.1 最小生成树的Prime算法与最短路径的Dijkstra算法这两个算法非常相像，尽管用于解决不同的问题。
它俩可以归入动态规划（Dynamic Programming）中，由当前状态选择最优，然后更新下一步的状态。
这两个问题，都是把图中的顶点集V划分为两个集合，一个是已经解决的顶点集U，剩余的未解决顶点集V-U。
对于每个顶点，都记录下它们的解决代价，分别用costs[]和dist[]数组来表示每个顶点的生成代价和最短距离。
需要注意的是，costs[]和dist[]数组，记录的是从集合U到顶点v的代价，而不是源点直接到v的代价（源点到顶点v的解决方案，可能会经过集合U中的若干顶点）。
算法的执行采用贪心算法，每次从未解决的顶点集中挑选一个最小代价，把它归入已解决的顶点集U中，然后更新剩余V-U中的解决代价，如下图所示。
这两个问题的区别在于，代价的计算方式不一样而已。
下面是这两个算法的求解过程表示。
普里姆(Prime)算法的求解过程如下（从顶点V0开始）Dijkstra算法的求解过程如下（从顶点V0开始）：4.2 最小生成树的Kruskal算法其思想是，从最小代价的边挑选起，只要不形成回路即可。
新挑选的一条边是否形成回路，关键是看这条边关联的两个顶点，是否已经在同一棵树上（一棵树上的任意两个顶点都是可达的，新增一条边即可形成回路）。
树的存储采用简单的双亲表示法，很容易找到每个顶点所在树的树根，进而判断两个顶点是否在同一棵树上。
算法的解决过程如下：4.3 所有顶点之间最短距离的Floyd算法假设顶点Vk处于某对顶点的最短路径上，考虑从图中把Vk删除的情况。
假设顶点Vi和Vj都与顶点Vk相邻。
Vi到Vj的最短距离，有可能经过Vk，也有可能不经过。
注意，上述的公式中，使用的是dist数组而不是edge数组。
随着顶点的删除，会逐步构建出一个新的全连接图（任意两点都有边相连），该图的边权值就是原图中这两个顶点的最短距离。
每次dist[i][j]的更新，都意味着新图中一条边的生成，或者权值的更新。
算法的执行，只需要把所有Vk删除即可。
每次删除时，要考虑在新图中所有与Vk相邻的顶点Vi和Vj。
求解过程如下：第五节 有向图的关键路径