图的定义及分类
定义：图是由一组顶点和一组能够将两个顶点相连的边组成的
image.png
图的分类：
按照连接两个顶点的边的不同，可以把图分为以下两种：
无向图：边仅仅连接两个顶点，没有其他含义；
有向图：边不仅连接两个顶点，并且具有方向；
无向图
相邻顶点：当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点。
度：某个顶点的度就是依附于该顶点的边的个数
子图：是一幅图的所有边的子集(包含这些边依附的顶点)组成的图；
路径：是由边顺序连接的一系列的顶点组成
环：是一条至少含有一条边且终点和起点相同的路径
连通图：如果图中任意一个顶点都存在一条路径到达另外一个顶点
邻接矩阵
1.使用一个V*V的二维数组int[V][V] adj,把索引的值看做是顶点；
2.如果顶点v和顶点w相连，我们只需要将adj[v][w]和adj[w][v]的值设置为1,否则设置为0即可。
邻接表
1.使用一个大小为V的数组 Queue[V] adj，把索引看做是顶点；
2.每个索引处adj[v]存储了一个队列，该队列中存储的是所有与该顶点相邻的其他顶点
图的搜索
深度优先搜索: 如果遇到一个结点既有子结点，又有兄弟结点，那么先找子结点，然后找兄弟结点。
深度优先搜索：如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后找子结点。
有向图
定义：有向图是一副具有方向性的图，是由一组顶点和一组有方向的边组成的，每条方向的边都连着一对有序的顶点。
出度：由某个顶点指出的边的个数称为该顶点的出度。
入度：指向某个顶点的边的个数称为该顶点的入度。
有向路径：由一系列顶点组成，对于其中的每个顶点都存在一条有向边，从它指向序列中的下一个顶点。
有向环：一条至少含有一条边，且起点和终点相同的有向路径。
拓扑排序
给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，此时就可以明确的表示出每个顶点的优先级。
加权无向图
加权无向图是一种为每条边关联一个权重值或是成本的图模型。
最小生成树
图的生成树是它的一棵含有其所有顶点的无环连通子图，一副加权无向图的最小生成树它的一棵权值(树中所有边的权重之和)最小的生成树
切分:
要从一副连通图中找出该图的最小生成树，需要通过切分定理完成。
贪心算法
贪心算法是计算图的最小生成树的基础算法，它的基本原理就是切分定理，使用切分定理找到最小生成树的一条边，不断的重复直到找到最小生成树的所有边。
Prim算法
它的每一步都会为一棵生成中的树添加一条边。一开始这棵树只有一个顶点，然后会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边加入到树中。
kruskal算法
kruskal算法是计算一副加权无向图的最小生成树的另外一种算法，它的主要思想是按照边的权重(从小到大)处理它们，将边加入最小生成树中，加入的边不会与已经加入最小生成树的边构成环，直到树中含有V-1条边为止。
kruskal算法和prim算法的区别：
Prim算法是一条边一条边的构造最小生成树，每一步都为一棵树添加一条边。kruskal算法构造最小生成树的时候也是一条边一条边地构造，但它的切分规则是不一样的。
它每一次寻找的边会连接一片森林中的两棵树。如果一副加权无向图由V个顶点组成，初始化情况下每个顶点都构成一棵独立的树，则V个顶点对应V棵树，组成一片森林，
kruskal算法每一次处理都会将两棵树合并为一棵树，直到整个森林中只剩一棵树为止。
加权有向图
加权无向图中，边是没有方向的，并且同一条边会同时出现在该边的两个顶点的邻接表中，为了能够处理含有方向性的图的问题，我们需要实现以下加权有向图。
最短路径
定义：在一副加权有向图中，从顶点s到顶点t的最短路径是所有从顶点s到顶点t的路径中总权重最小的那条路径。
最短路径树：
给定一副加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一副子图，它包含顶点s以及从s可达的所有顶点。这棵有向树的根结点为s，树的每条路径都是有向图中的一条最短路径。
Disjstra算法
Disjstra算法的实现和Prim算法很类似，构造最短路径树的每一步都是向这棵树中添加一条新的边，而这条新的边是有效横切边pq队列中的权重最小的边。
网友评论