数据结构 - 图

2. BFS-代码实现如下

package com.lj.advance;

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

public class BFS {
    public static final int MAX_NUM = 100;

    public static int[] visited = new int[MAX_NUM];

    /**
     * 顶点结构
     */
    static class VNode {
        //顶点的数据信息
        String data;
        //边结构依赖坐标指向
        ArcNode firstArc;
    }

    /**
     * 边结构
     */
    static class ArcNode {
        //指向的顶点位置
        int adjVex;
        //指向下一条边的指针
        ArcNode nextArc;
    }


    /**
     * 设置图的结构
     */
    static class ArcGraph {
        //顶点的列表
        VNode[] vertices = new VNode[MAX_NUM];
        //图的当前顶点数
        int vexNum;
        //图的当前的边数
        int arcNum;
    }

    static boolean createUDG(ArcGraph G) {
        Scanner sc = new Scanner(System.in);
        //设置图的顶点数目
        G.vexNum = sc.nextInt();
        //设置图的边数
        G.arcNum = sc.nextInt();
        sc = new Scanner(System.in);
        //构造顶点列表结构
        for (int i = 0; i < G.vexNum; i++) {
            VNode vNode = new VNode();
            vNode.data = sc.next();
            vNode.firstArc = null;
            G.vertices[i] = vNode;
        }
        //构造边结构
        for (int k = 0; k < G.arcNum; k++) {
            //输入边的关系
            sc = new Scanner(System.in);
            String v1 = sc.next();
            String v2 = sc.next();
            //点位边的下标索引
            int i = LocateVex(G, v1);
            int j = LocateVex(G, v2);
            ArcNode nodeI = new ArcNode();
            nodeI.adjVex = j;
            nodeI.nextArc = G.vertices[i].firstArc;
            G.vertices[i].firstArc = nodeI;
            ArcNode nodeJ = new ArcNode();
            nodeJ.adjVex = i;
            nodeJ.nextArc = G.vertices[j].firstArc;
            G.vertices[j].firstArc = nodeJ;
        }
        return true;
    }

    static void bfs(ArcGraph G, int v) {
        System.out.println("访问第" + v + "顶点");
        visited[v] = 1;
        Queue queue = new LinkedList<>();
        //将该顶点入队列
        queue.add(v);
        while (!queue.isEmpty()) {
            Integer index = queue.poll();
            for (int w = firstAdjVex(G,index);w>=0;w = nextAdjVex(G,index,w)){
                if(visited[w]==0){
                    System.out.println("访问第" + w + "顶点");
                    visited[w] = 1;
                    queue.add(w);
                }
            }
        }
    }

    static int nextAdjVex(ArcGraph G,int u, int index){
        ArcNode p = G.vertices[u].firstArc;
        ArcNode node = null;
        while (p!=null){
            int adjVex = p.adjVex;
            if(adjVex==index){
                node = p;
            }
            p = p.nextArc;
        }
        if(node!=null&&node.nextArc!=null){
           return node.nextArc.adjVex;
        }else {
            return -1;
        }
    }

    static int firstAdjVex(ArcGraph G, int u) {
        ArcNode firstArc = G.vertices[u].firstArc;
        if (firstArc != null) {
            return firstArc.adjVex;
        } else {
            return -1;
        }
    }

    static int LocateVex(ArcGraph G, String v) {
        for (int i = 0; i < G.vexNum; i++) {
            String data = G.vertices[i].data;
            if (v.equals(data)) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        ArcGraph graph = new ArcGraph();
        createUDG(graph);
        VNode[] vertices = graph.vertices;
        for (int i = 0; i < graph.vexNum; i++) {
            System.out.print("vex" + vertices[i].data + ":" + "\t");
            ArcNode p = vertices[i].firstArc;
            while (p != null) {
                System.out.print("next adj " + p.adjVex + "\t");
                p = p.nextArc;
            }
            System.out.println();
        }

        for (int i = 0;i