main.java

深度优先

package hartech.kids.grapher;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.event.*;
import hartech.ui.*;
import hartech.ds.Queue;

/**
 * <p>Title: 图的应用演示 </p>
 *
 * <p>Description: </p>
 *
 * <p>Date: 2006-09-07 </p>
 */
public class Main {

	// 图标
	static JLabel[] icon;

	// 图标数量
	static final int icon_num = 25;

	// 图存储结构
	static int arcs[][];

	// 图的存储结构二
	// 专门做为最短路径的参数
	// 因如用上面的arcs[][]则为完全图，点与点间最短距离当然就是两点用直线相连，没什么意思
	// 该结构继承上面的arcs[][]，但仅是相邻距离最小的四个节点可通，到其它节点不通
	static int arcs_last4[][];

	// 设置仅连相邻距离最小的 LAST_NUM 个节点可通
	static final int LAST_NUM = 2;

	// 图标移动范围
	static final int panel_width = 715, panel_height = 290;

	// 四个队列，图运算结果保存于该四队列，第五个为路径图
	// panel根据这些队列画线、箭头
	static Queue Q_DFS = new Queue();

	static Queue Q_BFS = new Queue();

	static Queue Q_tree = new Queue();

	static Queue Q_shortest = new Queue();

	static Queue Q_route = new Queue();

	// 记录各种遍历的路径总长度，用于在右下角显示
	static int length_DFS = 0, length_BFS = 0, length_tree = 0,
			length_short = 0, length_route = 0;

	// 预设25个图标的坐标
	static final int[] location_x = { 203, 180, 40, 458, 99, 118, 230, 409, 27,
			519, 259, 496, 695, 292, 415, 295, 320, 504, 342, 181, 575, 562,
			621, 419, 694 };

	static final int[] location_y = { 134, 181, 0, 112, 188, 73, 242, 169, 271,
			56, 72, 287, 10, 210, 247, 129, 0, 178, 54, 35, 219, 140, 77, 30,
			196 };

	// 初始化
	static {
		// arcs[][]
		arcs = new int[icon_num][icon_num];
		arcs_last4 = new int[icon_num][icon_num];
		// 自己到自己为不联通，-1
		for (int i = 0; i < icon_num; i++) {
			arcs[i][i] = -1;
		}

		// icon[]
		icon = new JLabel[icon_num];
		for (int i = 0; i < icon_num; i++) {
			icon[i] = new JLabel(ComboBoxRenderer
					.createImageIcon("images/smiles/" + i + ".gif"));
			icon[i].setBounds(location_x[i], location_y[i], 22, 22);
			icon[i].addMouseMotionListener(new MouseMotionListener_drag_icon());
		}

		updateArcs();
		//printLocations();
	}

	// 更新各图标距离到图存储结构 arcs[][]
	// 全联通，自己到自己为不联通：-1
	static void updateArcs() {
		int temp = 0;
		// 因无向图，仅计算矩阵上三角
		for (int i = 0; i < icon_num; i++) {
			for (int j = i + 1; j < icon_num; j++) {
				temp = (icon[i].getX() - icon[j].getX())
						* (icon[i].getX() - icon[j].getX())
						+ (icon[i].getY() - icon[j].getY())
						* (icon[i].getY() - icon[j].getY());
				arcs[i][j] = (int) Math.pow(temp, 0.5);
			}
		}
		// 复制到下三角
		for (int i = 0; i < icon_num; i++) {
			for (int j = 0; j < i; j++) {
				arcs[i][j] = arcs[j][i];
			}
		}
	}

	// 用updateArcs()计算出所有距离，再把非最小四的节点设为 -1
	// 先求出有向图，再转成无向图
	static void updateArcs_last4() {
		updateArcs();

		int min, p = 0;
		Q_route.clean();
		length_route = 0;
		boolean[] isLast4 = new boolean[icon_num];
		for (int i = 0; i < icon_num; i++) {
			for (int n = 0; n < icon_num; n++) {
				isLast4[n] = false;
			}
			// 找出四个最短的
			for (int n = 0; n < LAST_NUM; n++) {
				min = Integer.MAX_VALUE;
				for (int j = 0; j < icon_num; j++) {
					if (arcs[i][j] != -1 && arcs[i][j] < min && !isLast4[j]) {
						min = arcs[i][j];
						p = j;
					}
				}
				if (min == Integer.MAX_VALUE) {
					break;
				} else {
					isLast4[p] = true;
				}
			}
			// 输入到arcs_last4[][]
			for (int n = 0; n < icon_num; n++) {
				if (isLast4[n]) {
					arcs_last4[i][n] = arcs[i][n];
				} else {
					arcs_last4[i][n] = -1;
				}
			}
		}

		// 把上面的有向图变成无向图
		for (int i = 0; i < icon_num; i++) {
			for (int j = 0; j < icon_num; j++) {
				if (arcs_last4[i][j] != -1 && arcs_last4[j][i] == -1) {
					arcs_last4[j][i] = arcs_last4[i][j];
				}
			}
		}

		// 遍历上三角，把上面所得的无向图中所有路径入队列和统计总长度
		for (int i = 0; i < icon_num; i++) {
			for (int j = i + 1; j < icon_num; j++) {
				if (arcs_last4[i][j] != -1) {
					// 输出到 Global.Q_route 队列，用于画路径图
					Q_route.enQueue(new Dimension(i, j));
					length_route += arcs_last4[i][j];
				}
			}
		}
		UI.jTextField_route.setText(String.valueOf(length_route));
	}

	// 打印出当前所有图标的坐标
	static void printLocations() {
		StringBuffer out_x = new StringBuffer("{");
		StringBuffer out_y = new StringBuffer("{");
		Point d;
		for (int i = 0; i < icon_num; i++) {
			d = icon[i].getLocation();
			out_x.append((int) d.getX() + ",");
			out_y.append((int) d.getY() + ",");
		}
		System.out.println(out_x + "}");
		System.out.println(out_y + "}");
	}

	static JFrame jFrame;

	public static void main(String... args) {
		javax.swing.SwingUtilities.invokeLater(new Runnable() {
			public void run() {
				jFrame = new JFrame("Grapher  ---- www.hartech.cn");
				jFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

				// add
				jFrame.add(new UI(), BorderLayout.CENTER);
				jFrame.setSize(750, 475);
				J.goCenter(jFrame);
				jFrame.setVisible(true);
			}
		});
	}
}

// 图标拖动事件
class MouseMotionListener_drag_icon implements MouseMotionListener {
	static JLabel temp;

	static int x, y;

	public void mouseMoved(MouseEvent e) {
	}

	public void mouseDragged(MouseEvent e) {
		temp = ((JLabel) e.getSource());
		x = temp.getX() + e.getX() - 10;
		y = temp.getY() + e.getY() - 10;
		if (x > ((Dimension) UI.drawPanel.getSize()).width - 25) {
			x = ((Dimension) UI.drawPanel.getSize()).width - 25;
		}
		if (x < 5) {
			x = 5;
		}
		if (y > ((Dimension) UI.drawPanel.getSize()).height - 25) {
			y = ((Dimension) UI.drawPanel.getSize()).height - 25;
		}
		if (y < 5) {
			y = 5;
		}
		temp.setLocation(x, y);
		UI.drawPanel.repaint();
	}
}

class ActionListener_buttons implements ActionListener {
	public void actionPerformed(ActionEvent e) {

		//
		if (e.getActionCommand().equals("DFS_begin")) {
			Main.Q_DFS.clean();
			Main.length_DFS = 0;
			if (UI.jCheckBox_show_route.isSelected()) {
				Main.updateArcs_last4();
				Graph.traverse_DFS(Main.arcs_last4, UI.jComboBox_DFS_begin
						.getSelectedIndex());
			} else {
				Main.updateArcs();
				Graph.traverse_DFS(Main.arcs, UI.jComboBox_DFS_begin
						.getSelectedIndex());
			}
			UI.jTextField_DFS.setText(String.valueOf(Main.length_DFS));
			UI.drawPanel.repaint();
		} else if (e.getActionCommand().equals("DFS_clean")) {
			Main.Q_DFS.clean();
			Main.length_DFS = 0;
			UI.jTextField_DFS.setText(String.valueOf(Main.length_DFS));
			UI.drawPanel.repaint();
		}

		//
		else if (e.getActionCommand().equals("BFS_begin")) {
			Main.Q_BFS.clean();
			Main.length_BFS = 0;
			if (UI.jCheckBox_show_route.isSelected()) {
				Main.updateArcs_last4();
				Graph.traverse_BFS(Main.arcs_last4, UI.jComboBox_BFS_begin
						.getSelectedIndex());
			} else {
				Main.updateArcs();
				Graph.traverse_BFS(Main.arcs, UI.jComboBox_BFS_begin
						.getSelectedIndex());
			}
			UI.jTextField_BFS.setText(String.valueOf(Main.length_BFS));
			UI.drawPanel.repaint();
		} else if (e.getActionCommand().equals("BFS_clean")) {
			Main.Q_BFS.clean();
			Main.length_BFS = 0;
			UI.jTextField_BFS.setText(String.valueOf(Main.length_BFS));
			UI.drawPanel.repaint();
		}

		//
		else if (e.getActionCommand().equals("tree_begin")) {
			Main.Q_tree.clean();
			Main.length_tree = 0;
			if (UI.jCheckBox_show_route.isSelected()) {
				Main.updateArcs_last4();
				Graph.miniSpanTree(Main.arcs_last4);
			} else {
				Main.updateArcs();
				Graph.miniSpanTree(Main.arcs);
			}
			UI.jTextField_tree.setText(String.valueOf(Main.length_tree));
			UI.drawPanel.repaint();
		} else if (e.getActionCommand().equals("tree_clean")) {
			Main.Q_tree.clean();
			Main.length_tree = 0;
			UI.jTextField_tree.setText(String.valueOf(Main.length_tree));
			UI.drawPanel.repaint();
		}

		//
		else if (e.getActionCommand().equals("shortest_begin")) {
			Main.Q_shortest.clean();
			Main.length_short = 0;
			if (UI.jCheckBox_show_route.isSelected()) {
				Main.updateArcs_last4();
				Graph.shortestPath_DIJ(Main.arcs_last4,
						UI.jComboBox_shortest_begin.getSelectedIndex(),
						UI.jComboBox_shortest_end.getSelectedIndex());
			} else {
				Main.updateArcs();
				Graph.shortestPath_DIJ(Main.arcs, UI.jComboBox_shortest_begin
						.getSelectedIndex(), UI.jComboBox_shortest_end
						.getSelectedIndex());
			}
			UI.jTextField_short.setText(String.valueOf(Main.length_short));
			UI.drawPanel.repaint();
		} else if (e.getActionCommand().equals("shortest_clean")) {
			Main.Q_shortest.clean();
			Main.length_short = 0;
			UI.jTextField_short.setText(String.valueOf(Main.length_short));
			UI.drawPanel.repaint();
		} else if (e.getActionCommand().equals("show_route")) {
			if (UI.jCheckBox_show_route.isSelected()) {
				Main.updateArcs_last4();
				UI.drawPanel.repaint();
			} else {
				Main.Q_route.clean();
				Main.length_route = 0;
				UI.jTextField_route.setText(String.valueOf(Main.length_route));
				UI.drawPanel.repaint();
			}
		} else if (e.getActionCommand().equals("show_number")) {
			UI.drawPanel.repaint();
		}
	}
}