存储方式
1、数组：用NxN二维数组表示含有N个顶点的图。需要N个顶点信息和N^2个弧信息的存储空间。对于无向图，可使用压缩存储方式。
2、邻接表：
。n个顶点、e条边的无向图需要n个头结点、2*e个表结点。在边稀疏的情况（e<<n*(n-1)/2）下，用邻接表比临街矩阵节省存储空间。邻接表不方便判断两个顶点之间是否有边或弧。
3、十字链表：
。将邻接表与逆邻接表相结合。若把图的邻接矩阵看成稀疏矩阵，则十字链表则可视作稀疏矩阵的链表存储结构。headvex/tailvex标识弧头/尾，hlink/tlink标识弧头/弧尾相同的下一条弧。顶点结点顺序存储，弧结点位置不定。
4、邻接多重表：
。设(ivex,jvex)为此边。ilink/jlink表示下一条依附于ivex/jvex的边。此结构便于对搜索过的边做标记或者删除一条边。
强连通分量
- 对于图G={V,A}，构造G_R={V,A_R}，使对于A中每一条弧J→K，A_R中都有K→J对应。
- 在G_R上从FIN[V_num-1]出发作深度优先遍历，序列FIN中的顶点按照对G作深度优先搜索遍历完成的先后顺序排列。则G_R上得到的深度优先生成森林中的每一棵树的顶点集都是G的一个强连通分量的顶点集。
最小生成树
1、Prim算法：设连通网N={V,{E}}，S是N上最小生成树中边的集合。从U={u_0}，u_0∈V、S=空集开始，重复地从U中选择顶点u、从V-U中选择顶点v，使（u,v）代价最小，将（u,v）并入S，将顶点v并入U，直到U=V。此算法T(n)=O(n^2)，与边数无关，适合于边稠密的网。
2、Kruskal算法：开始使每个顶点各自成为一个连通分量。从边集E中选取一条代价最小的边，其起点与终点分属于两个不同的连通分量。将此边加入边集S中，直到T中所有顶点属于同一个连通分量。此算法适合于边稀疏的图，T(n)=O[e×Log(2,e)]。
最短路径
1、Dijkstra算法：求其它顶点到顶点v0的最短路径D[1]、D[2]……D[n]。T(n)=O(n^2)。
- 设邻接矩阵M[Ⅰ，J]代表有向边（Ⅰ，J）的权，边不存在则取无穷大。又有顶点集合S，初始为空集。其元素e是当前已找到最短路径的终点。此时从起点到v_Ⅰ可能得最短路径长度得初始值是：D[Ⅰ]=M[LocateVex(N，v0)] [Ⅰ]，v_Ⅰ∈顶点集合V。
- 选择顶点v_J使得D[J]=Min{D[Ⅰ] | v_Ⅰ∈V－S}，再令S=S∪{v_J}。
- 若D[J]＋M[J][K]<D[K]则将D[K]修改为D[J]＋M[J][K]。
- 重复第2、3步n-1次。
2、Floyd算法：求每一对顶点v_Ⅰ与v_J之间的最短路径长度D[Ⅰ][J]。设n阶方阵D^(-1)=G.arcs[Ⅰ][J]，D^k=Min{D^(k-1)[Ⅰ][J]，D^(k-1)[Ⅰ][K]+D^(k-1)[K][J]}，0<=K<=n-1。从D^(-1)开始依次计算D^0、D^1……D^(n-1)。则D^(n-1)就是从顶点v_Ⅰ到v_J的最短路径的长度。T(n)=O(n^3)。
标签：结点,路径,连通,算法,顶点,随录,分量,图文 From： https://www.cnblogs.com/tingzhouduruo/p/sjjg_tu.html