图的链式前向星存储与搜索

图的存储与搜索

链式前向星存储

图的存储方式有很多种，但是也都有各自的优缺点。例如：采用邻接矩阵的形式存储的时候，存储比较简单，但是遍历或者处理的时候就会比较浪费时间；而采用邻接表存储，则效率会有很大的提示，但是存储就比较麻烦。
而链式前向星存储类似于图的邻接表。我从百度上查到的是从前向星（也是一种存储图数据结构）优化而来的，它的存储也比较简单，效率也很快。当处理稠密图的时候可以选择使用邻接矩阵而当数据范围较大或者稀疏图的时候采用邻接表或者链式前向星就能很好的提高效率。
下边是它的代码实现以及解释。

int[] head; // head[i]存以为起点的最后一条边的下标（在中的下标）
int[] e; // e[i]存储第i条边的终点
int[] ne; // ne[i]存储的是与第i条边同起点的上一条边
int[] w; // w[i]存储的是第i条边的权值
public static void add(int a, int b, int c){
    // idx指的是第idx条边
    e[idx] = b; // 第idx边的终点是b
    w[idx] = c; // 权值是c
    ne[idx] = head[a]; 
    head[a] = idx ++; // 更新以a为起点的编号
}

完整的测试代码：

```java
package 图;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final int N = 10010;
    static int[] head = new int[N], e = new int[N], ne = new int[N], w = new int[N];
    static int idx = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Arrays.fill(head,-1);
        // 顶点个数
        int n = in.nextInt();
        // 边的个数
        int k = in.nextInt();
        for(int i = 0; i < k; i ++){
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            add(a, b, c);
        }

        for(int i = 1; i <= n; i ++){
            for(int j = head[i]; j != -1; j = ne[j]){
                System.out.println("start:" + i + ",end:" + e[j] + ",w:" + w[j]);
            }
        }
    }
    public static void add(int a, int b, int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = head[a];
        head[a] = idx ++;
    }
}

测试样例：

结果输出：

在这里插入图片描述

DFS

采用链式前向星存储的图的深度优先搜索。
深度优先搜索我就不过多解释，就是沿着一条路一直走下去，走不下去再回头取尝试别的路。

代码实现

    /**
     * 图的深度优先搜索
     * 以u为起点开始进行DFS
     * @param u
     */
    public static void dfs(int u){
        System.out.print(u + " ");
        st[u] = true; // 标记已经被访问过
        for(int i = head[u]; i != -1; i = ne[i]){
            int j = e[i];
            if(!st[j]) dfs(j);
        }
    }

结果输出：

以1为起点，进行DFS
在这里插入图片描述

BFS

图的广度优先搜索，借助队列来实现。
一层一层的遍历，可以用他来求路径固定的最短。

代码实现

    /**
     * 图的广度优先搜索
     * @param u
     */
    public static void bfs(int u){
        Queue<Integer> q = new ArrayDeque<>();
        q.add(u);
        st[u] = true;
        while(!q.isEmpty()){
            u = q.poll();
            System.out.print(u + " ");
            for(int i = head[u]; i != -1; i = ne[i]){
                int j = e[i];
                if(!st[j]) {
                    st[j] = true;
                    q.add(j);
                }
            }
        }
    }