图的定义

图是由一组顶点和一组能够将两个顶点相连的边组成的。

?特殊图：

图可以分为无向图和有向图。有向图就是连接是有方向的。

图的相关术语

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

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

连通图： 如果图中任意一个顶点都存在一条路径到达另外一个顶点

图的存储结构

要表示一幅图，只需要表示清楚以下两部分内容即可：

1. 图中所有的顶点；

2. 所有连接顶点的边；

常见的图的存储结构有两种：邻接矩阵和邻接表

?邻接矩阵

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] 存储了一个队列，该队列中存储的是所有与该顶点相邻的其他顶点。

无向图的实现

?无向图的构建：

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

public class Graph {
    private final int V; //顶点数量
    private int E; //边的数量
    private Queue<Integer>[] adj;

    public Graph(int V){
        //初始化
        this.V = V;
        this.E = 0;
        this.adj = new LinkedList[V];

        for(int i=0; i<adj.length; i++){
            adj[i] = new LinkedList();
        }
    }

    public int V(){
        return V;
    }

    public int E(){
        return E;
    }

    public void addEdge(int v, int w){
        // 无向图
        adj[v].offer(w);
        adj[w].offer(v);
        // 边的数量+1
        E++;
    }

    public Queue<Integer> adj(int v){
        return adj[v];
    }
    
}

?图的搜索

深度优先搜索（DFS）

先找子结点，再找兄弟结点。

?（搜索过的点不用再搜索）

public class DFS {
    private boolean[] marked; //数组索引代表顶点，表示当前顶点是否已经被搜索
    private int count;  // 记录有多少个顶点与顶点s相通
    public DFS(Graph G, int s){
        //初始化
        this.marked = new boolean[G.V()];
        this.count = 0;

        dfs(G,s);
    }

    private void dfs(Graph G, int V){
        // 把V顶点标识为已经搜索
        marked[V] = true;

        for(Integer w: G.adj(V)){
            //判断当前w顶点有没有被搜索过
            if(!marked[w]){
                dfs(G,w);
            }
        }
        count++; // 相通顶点数量+1
    }

    //判断W顶点是否和S顶点相通
    private boolean marked(int w){
        return marked[w]; //被搜索过则意味着相通
    }
    //获取与顶点s相同的所有顶点的总数
    public int count(){
        return count;
    }
}

广度优先搜索（BFS）

先找兄弟结点，再找子结点。

（搜索过的点不用再搜索）

层序遍历其实就是广度优先搜索。

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

public class BFS {
    private boolean[] marked;
    private int count;
    private Queue<Integer> waitSearch; //辅助队列

    public BFS(Graph G, int s){
        this.marked = new boolean[G.V()];
        this.count = 0;
        this.waitSearch = new LinkedList<Integer>();
        bfs(G,s);
    }

    private void bfs(Graph G, int v){
        marked[v] = true;
        waitSearch.offer(v);
        while(!waitSearch.isEmpty()){
            Integer wait = waitSearch.remove();
            //遍历wait顶点的邻接表
            for(Integer w: G.adj(wait)){
                if(!marked[w]){
                    bfs(G, w);
                }
            }
        }
        count ++;
    }

    public boolean marked(int w){
        return marked[w];
    }
    public int count(){
        return count;
    }
}