度： 某个顶点的度就是依附于该顶点的边的个数

子图 ：一幅图中所有边(包含依附边的顶点)的子集

路径： 是由边顺序连接的一系列定点组成

环： 至少含有一条边且终点和起点相同的路径

连通图 ：如果图中任一个到另一个节点都存在一条路径，该图就叫连通图。

图的存储方式

1.邻接矩阵：

空间复杂度较高。

2.邻接表

图结构的java实现代码

 

import java.util.LinkedList;
import java.util.Queue;

/**
 * 无向图
 * 数组索引代表顶点的值
 */public class Graph {
    private int V; //顶点数量
    private int E; //边数量
    private Queue<Integer>[] 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<Integer> 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<Integer> 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;
    }
}