一 需要创建的图

二 代码

package graph;

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

public class BFSAL {
    static final int MaxVnum = 100;  // 顶点数最大值
    // 访问标志数组，其初值为"false"
    static Boolean visited[] = new Boolean[MaxVnum];

    static {
        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }
    }

    static int locatevex(BFSAL.ALGraph G, char x) {
        for (int i = 0; i < G.vexnum; i++) // 查找顶点信息的下标
            if (x == G.Vex[i].data)
                return i;
        return -1; // 没找到
    }

    // 插入一条边
    static void insertedge(BFSAL.ALGraph G, int i, int j) {
        graph.AdjNode s = new graph.AdjNode();
        s.v = j;
        s.next = G.Vex[i].first;
        G.Vex[i].first = s;
    }

    // 创建有向图邻接表
    static void CreateALGraph(BFSAL.ALGraph G) {
        int i, j;
        char u, v;

        System.out.println("请输入顶点数和边数:");
        Scanner scanner = new Scanner(System.in);
        G.vexnum = scanner.nextInt();
        G.edgenum = scanner.nextInt();
        System.out.println("请输入顶点信息:");

        for (i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组
            G.Vex[i].data = scanner.next().charAt(0);
        for (i = 0; i < G.vexnum; i++)
            G.Vex[i].first = null;
        System.out.println("请依次输入每条边的两个顶点u,v");

        while (G.edgenum-- > 0) {
            u = scanner.next().charAt(0);
            v = scanner.next().charAt(0);
            i = locatevex(G, u); // 查找顶点 u 的存储下标
            j = locatevex(G, v); // 查找顶点 v 的存储下标
            if (i != -1 && j != -1)
                insertedge(G, i, j);
            else {
                System.out.println("输入顶点信息错！请重新输入！");
                G.edgenum++; // 本次输入不算
            }
        }
    }

    // 输出邻接表
    static void printg(BFSAL.ALGraph G) {
        System.out.println("----------邻接表如下：----------");
        for (int i = 0; i < G.vexnum; i++) {
            graph.AdjNode t = G.Vex[i].first;
            System.out.print(G.Vex[i].data + "：  ");
            while (t != null) {
                System.out.print("[" + t.v + "]\t");
                t = t.next;
            }
            System.out.println();
        }
    }

    // 基于邻接表的广度优先遍历
    static void BFS_AL(ALGraph G, int v) {
        int u, w;
        graph.AdjNode p;
        // 创建一个普通队列(先进先出)，里面存放int类型
        Queue<Integer> Q = new LinkedList<>();
        System.out.println(G.Vex[v].data + "\t");

        visited[v] = true;
        Q.add(v); // 源点 v 入队
        // 如果队列不空
        while (!Q.isEmpty()) {
            u = Q.peek(); // 取出队头元素赋值给u
            Q.poll(); // 队头元素出队
            p = G.Vex[u].first;
            while (p != null) { // 依次检查u的所有邻接点
                w = p.v; // w 为 u 的邻接点
                if (!visited[w]) { // w 未被访问
                    System.out.println(G.Vex[w].data + "\t");
                    visited[w] = true;
                    Q.add(w);
                }
                p = p.next;
            }
        }
    }

    public static void main(String[] args) {
        BFSAL.ALGraph G = new BFSAL.ALGraph();
        for (int i = 0; i < G.Vex.length; i++) {
            G.Vex[i] = new graph.VexNode();
        }
        CreateALGraph(G); // 创建有向图邻接表
        printg(G); // 输出邻接表
        System.out.println("请输入遍历图的起始点：");
        Scanner scanner = new Scanner(System.in);
        char c = scanner.next().charAt(0);
        int v = locatevex(G, c);//查找顶点u的存储下标
        if (v != -1) {
            System.out.println("广度优先搜索遍历图结果：");
            BFS_AL(G, v);
        } else
            System.out.println("输入顶点信息错！请重新输入！");
    }

    // 定义邻接点类型
    static class AdjNode {
        int v; // 邻接点下标
        graph.AdjNode next; // 指向下一个邻接点
    }

    // 定义顶点类型
    static class VexNode {
        char data; // VexType为顶点的数据类型，根据需要定义
        graph.AdjNode first; // 指向第一个邻接点
    }

    // 定义邻接表类型
    static class ALGraph {
        graph.VexNode Vex[] = new graph.VexNode[CreateALGraph.MaxVnum];
        int vexnum; // 顶点数
        int edgenum; // 边数
    }
}

三 测试

绿色为输入，白色为输出