一 需要创建的图

二 代码

package graph;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class BFSAM {
    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(BFSAM.AMGraph G, char x) {
        for (int i = 0; i < G.vexnum; i++) // 查找顶点信息的下标
            if (x == G.Vex[i])
                return i;
        return -1; // 没找到
    }
 
    static void CreateAMGraph(BFSAM.AMGraph G) {
        Scanner scanner = new Scanner(System.in);
        int i, j;
        char u, v;
        System.out.println("请输入顶点数：");
        G.vexnum = scanner.nextInt();
        System.out.println("请输入边数:");
        G.edgenum = scanner.nextInt();
        System.out.println("请输入顶点信息:");
 
        // 输入顶点信息，存入顶点信息数组
        for (int k = 0; k < G.vexnum; k++) {
            G.Vex[k] = scanner.next().charAt(0);
        }
        //初始化邻接矩阵所有值为0，如果是网，则初始化邻接矩阵为无穷大
        for (int m = 0; m < G.vexnum; m++)
            for (int n = 0; n < G.vexnum; n++)
                G.Edge[m][n] = 0;
 
        System.out.println("请输入每条边依附的两个顶点：");
        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)
                G.Edge[i][j] = 1; //邻接矩阵储置1
            else {
                System.out.println("输入顶点信息错！请重新输入！");
                G.edgenum++; // 本次输入不算
            }
        }
    }
 
    static void print(BFSAM.AMGraph G) { // 输出邻接矩阵
        System.out.println("图的邻接矩阵为：");
        for (int i = 0; i < G.vexnum; i++) {
            for (int j = 0; j < G.vexnum; j++)
                System.out.print(G.Edge[i][j] + "\t");
            System.out.println();
        }
    }
 
    // 基于邻接矩阵的广度优先遍历
    static void BFS_AM(AMGraph G, int v) {
        int u, w;
        // 创建一个普通队列(先进先出)，里面存放int类型
 
        Queue<Integer> Q = new LinkedList<>();
        System.out.println(G.Vex[v] + "\t");
 
        visited[v] = true;
        Q.add(v); // 源点 v 入队
        while (!Q.isEmpty()) { //如果队列不空
            u = Q.peek(); // 取出队头元素赋值给u
            Q.poll(); // 队头元素出队
            for (w = 0; w < G.vexnum; w++) {// 依次检查 u 的所有邻接点
                if (G.Edge[u][w] == 1 && !visited[w]) { // u、w 邻接而且 w 未被访问
                    System.out.println(G.Vex[w] + "\t");
 
                    visited[w] = true;
                    Q.add(w);
                }
            }
        }
    }
 
    public static void main(String[] args) {
        int v;
        char c;
        AMGraph G = new BFSAM.AMGraph();
        CreateAMGraph(G);
        print(G);
        System.out.println("请输入遍历图的起始点：");
        Scanner scanner = new Scanner(System.in);
        c = scanner.next().charAt(0);
 
        v = locatevex(G, c); // 查找顶点u的存储下标
        if (v != -1) {
            System.out.println("广度优先搜索遍历图结果：");
            BFS_AM(G, v);
        } else
            System.out.println("输入顶点信息错！请重新输入！");
    }
    
    static class AMGraph {
        char Vex[] = new char[CreateAMGraph.MaxVnum];
        int Edge[][] = new int[CreateAMGraph.MaxVnum][CreateAMGraph.MaxVnum];
        int vexnum; // 顶点数
        int edgenum; // 边数
    }
}
 
 

三 测试