graph.java

来自「1.程序基于java语言。运行要求java运行环境。即就使jdk1.2以上。否则」· Java 代码 · 共 302 行

package bfs;

import java.io.*;
import java.util.StringTokenizer;
import javax.swing.JTextArea;
import javax.swing.JOptionPane;
import java.util.Vector;

/**
 * <p>Title: 基于java语言的图的广度遍历</p>
 *
 * <p>Description: 版权所有严禁盗版</p>
 *
 * <p>Copyright: Copyright (c) 2005</p>
 *
 * <p>Company: 中南大学计算机0304班 </p>
 *
 * @author 李阳辉
 * @version 1.0
 */
/**
 * 该类是对图的定义
 *
 * 采用邻接矩阵表示
 */

public class Graph {
    private int kind; //图的类型
    private int[][] adjMatrix = new int[50][50]; //图的邻接矩阵,最大为50
    private int vex_num, arc_num; //当前的顶点数和弧数
    private boolean[] visited = new boolean[50]; //访问标志数组


    private BufferedReader input; //用来读文件
    private Vector queue = new Vector(); //用一个向量来做队列
    private Vector stack = new Vector(); //用一个向量来做堆栈
    public Graph() {
    }

    //从文件初始化图
    public void readGraph(String fileName, int kind) {
        //先进行初始化。
        this.kind = kind;
        for (int i = 0; i < 50; i++) {
            for (int j = 0; j < 50; j++) {
                adjMatrix[i][j] = 0;
            }
        }
        vex_num = arc_num = 0;
        try { //利用缓冲流读取文件内容
            input = new BufferedReader(new FileReader(fileName));
            System.out.println("成功打开文件");
        } catch (FileNotFoundException ex) {
            System.out.println(ex);
        }
        try {
            String line;
            while ((line = input.readLine()) != null) {
                StringTokenizer t = new StringTokenizer(line, " "); //分开头和尾
                int head = Integer.parseInt(t.nextToken()); //得到边的头
                int cauda = Integer.parseInt(t.nextToken()); //得到边的尾
                if (head >= vex_num) { //得到一个有多少个顶点
                    vex_num = head;
                }
                if (cauda >= vex_num) { //得到一个有多少个顶点
                    vex_num = cauda;
                }
                arc_num++; //弧数加 1
                adjMatrix[head - 1][cauda - 1] = 1; //把弧填入邻接矩阵中
                if (kind != JOptionPane.YES_OPTION) { //为无向图时
                    adjMatrix[cauda - 1][head - 1] = 1;
                }
            }
            input.close(); //关闭文件,停止文件读入;
        } catch (IOException ex1) {
            System.out.println(ex1);
        }
    }

    //输出相应的图的数据
    public void printGraph(JTextArea showArea) {
        showArea.append("\n");
        showArea.append("你输入的图的数据:\n");
        //顶点数边数
        showArea.append("     一共用" + vex_num + "个顶点; 和" + arc_num + "条边;\n");
        showArea.append("     边的数据为:\n");
        //从邻接矩阵中读出边的数据
        boolean flag = false; //先判断i是否存在邻接点，有则打印其边，否则跳过
        for (int i = 0; i < vex_num; i++) {
            for (int j = 0; j < vex_num; j++) {
                if (adjMatrix[i][j] != 0) {
                    flag = true;
                    break;
                }
            }
            if (flag == true) {
                showArea.append("               " + (i + 1) + "-->");
                for (int j = 0; j < vex_num; j++) {
                    if (adjMatrix[i][j] != 0) {
                        showArea.append((j + 1) + ", ");
                    }
                }
                showArea.append("\n"); //往下移行
            }
            flag = false; //对标志归位;
        }
    }

    /**
     *下面方法完成对图的DFS遍历。
     *
     *一个完全的基于非递归的算法
     */
    public void DFS(JTextArea showArea) {
        showArea.append("现在开始用DFS遍历图：\n");
        stack.clear(); //保证堆栈为空。
        for (int i = 0; i < 50; i++) {
            visited[i] = false;
        }
        int parent = -1;
        for (int v = 0; v < this.vex_num; v++) {
            if (!visited[v]) { //v点尚未访问
                visited[v] = true; //设定标志
                showArea.append("访问" + (v + 1) + "顶点;\n");
                stack.add(new Integer(v)); //把该点加入堆栈中
                showArea.append("把" + (v + 1) + "顶点加入堆栈中;\n");
                while (!stack.isEmpty()) {
                    int currentVex = ((Integer) stack.lastElement()).intValue(); //得到栈顶元素
                    showArea.append("访问" + (currentVex + 1) + "顶点的邻接点 ;\n");
                    int adjVex;
                    showArea.append("检查" + (currentVex + 1) +
                                    "的邻接点和其他顶点之间是否存在环路.\n");
                    for (adjVex = 0; adjVex < vex_num; adjVex++) {
                        if (adjMatrix[currentVex][adjVex] != 0 &&
                            adjVex != parent) { //看是否存在回路
                            if (visited[adjVex] == true &&
                                stack.indexOf(new Integer(adjVex)) >= 0) {
                                showArea.append("检查到" + (adjVex + 1) +
                                                "顶点时停止存在环路！！！\n");
                                JOptionPane.showMessageDialog(null, "存在环路!");
                                for (int i = 0; i < vex_num; i++) {//把图归位，使之能够多次使用
                                    visited[i] = false;
                                }
                                stack.clear();
                                return;
                            }

                        } //否则访问并压堆栈中
                        if (adjMatrix[currentVex][adjVex] != 0 &&
                            adjVex != parent && visited[adjVex] != true) {
                            visited[adjVex] = true;
                            stack.add(new Integer(adjVex)); //把该邻接点压入堆栈中
                            showArea.append("把顶点" + (adjVex + 1) + "压入堆栈。\n");
                            parent = currentVex;
                            break;
                        }
                    }
                    //没有邻接点出栈
                    if (adjVex == vex_num) {
                        parent = currentVex;
                        showArea.append((currentVex + 1) + "顶点弹出堆栈;\n");
                        stack.remove(stack.lastElement()); //弹出栈顶元素
                    }
                } //while
            } //if
        } //for
        showArea.append("DFS访问停止，没有发现环路!!!\n");
        JOptionPane.showMessageDialog(null, "没有环路!!!");
        for (int i = 0; i < vex_num; i++) {
            visited[i] = false;
        }
        stack.clear();
    }

    //对图进行BFS访问实录,一个完全的非递归的算法。
    public void BFS(JTextArea showArea) {
        showArea.append("现在开始用BFS访问该图:\n");
        for (int i = 0; i < vex_num; i++) { //对图的BFS后把图归位.
            visited[i] = false;
        }
        queue.removeAllElements();
        for (int v = 0; v < this.vex_num; ++v) {
            if (!visited[v]) { //v点尚未访问
                visited[v] = true;
                showArea.append("访问" + (v + 1) + "顶点;\n");
                queue.add(new Integer(v)); //加入队列中
                showArea.append("把" + (v + 1) + "顶点加入队列中;\n");
                while (!queue.isEmpty()) {
                    int currentVex = ((Integer) queue.get(0)).intValue(); //得到队头元素
                    queue.remove(queue.remove(0)); //队头元素出队列
                    showArea.append((currentVex + 1) + "顶点出队列;\n");
                    showArea.append("访问" + (currentVex + 1) + "顶点的邻接点 ;\n");
                    for (int adjVex = 0; adjVex < vex_num; adjVex++) { //访问它的邻接点
                        //当它的邻接点还没有被访问时,进行访问.
                        if (!visited[adjVex] &&
                            adjMatrix[currentVex][adjVex] != 0) {
                            showArea.append("访问" + (adjVex + 1) + "顶点;\n");
                            visited[adjVex] = true; //标志已经访问此顶点
                            showArea.append("把" + (adjVex + 1) +
                                            "顶点加入队列中;\n");
                            queue.add(new Integer(adjVex)); //把它压入队列中
                        } //if
                    } //for
                } //while
            } //if
        } //for
        showArea.append("BFS访问完成!!!\n");
        //完成对图的BFS后把图归位.
        for (int i = 0; i < vex_num; i++) {
            visited[i] = false;
        }
        queue.removeAllElements();
    }

    public void shortestPath(JTextArea showArea) {
        //一开始输入出发顶点和结束顶点
        String input = JOptionPane.showInputDialog("请输入出发点");
        int start = Integer.parseInt(input);
        input = JOptionPane.showInputDialog("请输入结束顶点");
        int end = Integer.parseInt(input);
        //判断是否输入正确.
        if (start > vex_num || end > vex_num) {
            JOptionPane.showMessageDialog(null, "不存在这样的出发点或者结束点");
            return;
        }
        //判断是否是同一个顶点
        if (start == end) {
            JOptionPane.showMessageDialog(null, "请你不要输入相同的顶点");
            return;
        }
        //开始查找最短路径
        //下面的二元数组用来保存好路径
        boolean[][] path = new boolean[vex_num][vex_num];
        int currentVex = 0;
        showArea.append("现在开始利用BFS查找从" + start + "顶点到" + end + "顶点的最短路径：\n");
        //v点尚未访问
        visited[start - 1] = true;
        showArea.append("访问" + start + "顶点;\n");
        queue.add(new Integer(start - 1)); //加入队列中
        showArea.append("把" + start + "顶点加入队列中;\n");
        while (!queue.isEmpty()) {
            currentVex = ((Integer) queue.get(0)).intValue(); //得到队头元素
            queue.remove(queue.remove(0)); //队头元素出队列
            showArea.append((currentVex + 1) + "顶点出队列;\n");
            showArea.append("访问" + (currentVex + 1) + "顶点的邻接点 ;\n");
            for (int adjVex = 0; adjVex < vex_num; adjVex++) { //访问它的邻接点
                if (!visited[adjVex] &&
                    adjMatrix[currentVex][adjVex] != 0) {
                    path[currentVex][adjVex] = true; //存储路径
                    showArea.append("访问" + (adjVex + 1) + "顶点;\n");
                    visited[adjVex] = true; //标志已经访问此顶点
                    if (adjVex == end - 1) {
                        showArea.append("找到了" + end + "顶点;\n");
                        path(showArea, path, start, end); //把路径找出来
                        return;
                    }
                    showArea.append("把" + (adjVex + 1) + "顶点加入队列中;\n");
                    queue.add(new Integer(adjVex)); //把它压入队列中
                } //if
            } //for
        } //while
        //他们之间不存在路径,输出路径不存在
        showArea.append((currentVex + 1) + "顶点没有邻接点,BFS访问停止.\n");
        showArea.append("他们之间不存在路径!!!\n");
        JOptionPane.showMessageDialog(null, "他们之间相隔千山万水,永无重逢之日!!!");
    }

    private void path(JTextArea showArea, boolean path[][], int start,
                      int end) {
        int node = end - 1;
        int length = 0; //用来保存路径的长度；
        Vector pathNode = new Vector(); //用向量来保存路径；当作堆栈用。
        for (int i = 0; i < vex_num; i++) {
            if (path[i][node]) {
                pathNode.add(new Integer(i)); //压入堆栈
                node = i; //反方向逆回，找到上一个顶点
                length++;
                i = -1; //把扫描哨归零,但考虑到for会自动地加一。故回到-1
            }
            if (node == start - 1) {
                break;
            }
        }
        //把路径显示出来
        showArea.append("路径查找成功!!!\n");
        showArea.append("从" + start + "顶点到" + end + "顶点的最短路径长度为:" + length +
                        "\n");
        showArea.append("最短路径经过的节点为:\n");
        for (int i = pathNode.size() - 1; i >= 0; i--) {
            int currentVex = ((Integer) pathNode.get(i)).intValue(); //得到堆栈弹出的元素
            showArea.append((currentVex + 1) + "-->");
        }
        showArea.append(end + ".\n");
        //完成对图的查找后把图归位.
        for (int i = 0; i < vex_num; i++) {
            visited[i] = false;
        }
        queue.removeAllElements();
        queue.clear();
    }
}