度：某个顶点的度就是依附于该顶点的边的个数
子图：一幅图中所有边(包含依附边的顶点)的子集
路径：是由边顺序连接的一系列定点组成
环：至少含有一条边且终点和起点相同的路径
连通图：如果图中任一个到另一个节点都存在一条路径，该图就叫连通图。
图的存储方式
1.邻接矩阵：
空间复杂度较高。
2.邻接表
图结构的java实现代码
import java.util.LinkedList;import java.util.Queue;/** * 无向图 * 数组索引代表顶点的值 */public class Graph { private int V; //顶点数量 private int E; //边数量 private Queue[] adj; //邻接表 public Graph(int vertical) { this.V = vertical; this.adj = new Queue[vertical]; for (int i = 0; i < vertical; i++) { adj[i] = new LinkedList<>(); } } public int getV() { return V; } public int getE() { return E; } /*** 向图中某一顶点加一条边* 无向图是没有方向的，需要让w出现在v的邻接表中，还需要让v出现在w的邻接表中** @param w* @param v*/ public void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); this.E++; } /*** 获取和某一顶点关联的所有顶点** @param v* @return Queue*/ public Queue adj(int v) { return adj[v]; }}
深度优先搜索：指的是如果遇到一个子节点既有兄弟节点又有子节点，那么先找子节点，再找兄弟节点
实现代码如下:
/** * 深度优先搜索 */public class DepthFirstSearch { private int sCount; //记录多少个节点与s节点相通 private boolean[] marked; //代表顶点是否被搜索过 //找出g中与顶点s所有相邻的节点 public DepthFirstSearch(Graph g, int s) { marked = new boolean[g.getV()]; //初始化跟顶点s相通的数量 this.sCount = 0; dfs(g, s); } //找出g中与顶点v所有相通的节点 private void dfs(Graph graph, int v) { //将v节点标识为已搜索 marked[v] = true; for (Integer w : graph.adj(v)) { if (!marked[w]) {dfs(graph, w); } } sCount++; } private boolean marked(int w) { //判断w顶点与s顶点是否相通 return marked[w]; } private int count() {//获取所有与s顶点相通的总数 return sCount; }}
广度优先搜索：指的是如果遇到一个子节点既有兄弟节点又有子节点，那么先找兄弟节点，再找子节点,类似于层次遍历
代码如下：
import java.util.LinkedList;import java.util.Queue;/** * 广度优先搜索 */public class BreadthFirstSearch { private int sCount; //记录多少个节点与s节点相通 private final boolean[] marked; //代表顶点是否被搜索过 private final Queue waitSearch; //存储带搜索顶点 //找出g中与顶点s所有相邻的节点 public BreadthFirstSearch(Graph g, int s) { marked = new boolean[g.getV()]; //初始化跟顶点s相通的数量 this.sCount = 0; waitSearch = new LinkedList<>(); bfs(g, s); } //找出g中与顶点v所有相通的节点 private void bfs(Graph graph, int v) { waitSearch.add(v); while (!waitSearch.isEmpty()) { Integer wait = waitSearch.poll(); for (Integer w : graph.adj(wait)) {if (!marked(w)) {marked[w] = true;sCount++;waitSearch.add(w);} } } } public boolean marked(int w) { //判断w顶点与s顶点是否相通 return marked[w]; } public int count() {//获取所有与s顶点相通的总数 return sCount; }}
