代码如下：
以邻接矩阵构建图
public class Graph {
public static void main(String[] args) {
/**
* 定义一个图
*
* 本次实验为无向图
*
* 为了与平日思维习惯，第一行和第一列不用
*
* 从map[1][1]算作第一个点
*
* map：图
*
* mapUsed：标识该结点有没有遍历到
*
* edges：存储结点到结点的权重
*/
int[][] map = new int[10][10];
boolean[] mapUsed = new boolean[10];
Edge edges[] = new Edge[11];
/**
* 初始化图
*
*/
initMap(map, edges);
/**
* 深度优先遍历
*/
Depth_First_Traversal(map, mapUsed);
/**
* 广度优先遍历
*/
Breadth_First_Traversal(map, mapUsed);
/**
* 两种方式求最小生成树
*/
Minimal_Spanning_Tree(map, edges);
}
/**
* 初始化图的数据
*/
public static void initMap(int[][] map, Edge[] edges) {
/**
* 假定不能到达的点为Integer类型最大值
*/
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
map[i][j] = Integer.MAX_VALUE;
}
}
/**
* 初始化图
*/
map[1][2] = 3;
map[2][1] = 3;
edges[1] = new Edge(1, 2, 3);
map[2][8] = 10;
map[8][2] = 10;
edges[2] = new Edge(2, 8, 10);
map[8][5] = 9;
map[5][8] = 9;
edges[3] = new Edge(5, 8, 9);
map[7][9] = 4;
map[9][7] = 4;
edges[4] = new Edge(7, 9, 4);
map[4][8] = 7;
map[8][4] = 7;
edges[5] = new Edge(4, 8, 7);
map[3][7] = 18;
map[7][3] = 18;
edges[6] = new Edge(3, 7, 18);
map[9][6] = 15;
map[6][9] = 15;
edges[7] = new Edge(6, 9, 15);
map[4][5] = 13;
map[5][4] = 13;
edges[8] = new Edge(4, 5, 13);
map[5][6] = 10;
map[6][5] = 10;
edges[9] = new Edge(5, 6, 10);
map[4][7] = 23;
map[7][4] = 23;
edges[10] = new Edge(4, 7, 23);
}
/**
* 深度优先遍历
*
* @param map
* @param mapUsed
*/
public static void Depth_First_Traversal(int[][] map, boolean[] mapUsed) {
System.out.println("从点1，递归方式深度优先遍历图：");
DFS_Recursion(map, mapUsed, 1);
System.out.println();
System.out.println("从点1，非递归方式深度优先遍历图：");
DFS_NotRecursion(map);
System.out.println();
}
/**
* 广度优先遍历
*
* @param map
* @param mapUsed
*/
public static void Breadth_First_Traversal(int[][] map, boolean[] mapUsed) {
System.out.println("从点1，非递归方式广度优先遍历图：");
BFS_NotRecursion(map);
System.out.println();
mapUsed = new boolean[10];
System.out.println("从点1，递归方式广度优先遍历图：");
System.out.print(1 + " ");
mapUsed[1] = true;
Queue nextBFS = new Queue();
BFS_Recursion(map, mapUsed, 1, nextBFS);
System.out.println();
}
/**
* 求最小生成树
*
* @param map
* @param edges
*/
public static void Minimal_Spanning_Tree(int[][] map, Edge[] edges) {
System.out.println("Prim算法求最小生成树：");
Prim(9, map);
System.out.println("Kruskal算法求最小生成树：");
Kruskal(edges);
}
/**
* 递归方式深度优先遍历
*
* @param map
*/
public static void DFS_Recursion(int[][] map, boolean[] mapUsed, int next) {
// 打印，即访问next结点
System.out.print(next + " ");
// 标识next结点已经被访问
mapUsed[next] = true;
// 在next结点的出度里寻找下一个
for (int i = 1; i < map.length; i++) {
// 找下一个需要遍历的点
if (!mapUsed[i] && map[next][i] < 1000) {
// 递归
DFS_Recursion(map, mapUsed, i);
}
}
}
/**
* 递归方式广度优先遍历
*
* @param map
*/
public static void BFS_Recursion(int[][] map, boolean[] mapUsed, int next,
Queue nextBFS) {
// 在next结点的出度里寻找下一个
for (int i = 1; i < map.length; i++) {
// 如果没有访问
if (!mapUsed[i] && map[next][i] < 1000) {
// 访问i结点
mapUsed[i] = true;
System.out.print(i + " ");
// 将i结点排入队列
nextBFS.enQueue(i);
}
}
// 如果队列不为空
while (!nextBFS.isEmpty()) {
// 出队列
int nextBFSNumber = nextBFS.deQueue();
// 递归
BFS_Recursion(map, mapUsed, nextBFSNumber, nextBFS);
}
}
/**
* 非递归方式深度优先遍历
*
* @param map
*/
public static void DFS_NotRecursion(int[][] map) {
Stack stack = new Stack();
boolean[] mapUsed = new boolean[10];
// 将1压入栈
stack.push(1);
System.out.print(1 + " ");
mapUsed[1] = true;
while (!stack.isEmpty()) {
// 取得栈顶元素
int next = stack.getTop();
for (int i = 1; i < map.length; i++) {
if (!mapUsed[i] && map[next][i] < 1000) {
// 访问i结点
mapUsed[i] = true;
stack.push(i);
System.out.print(i + " ");
// 访问完i之后，重新得到栈顶元素，即i元素
next = stack.getTop();
// 重新遍历
i = 1;
}
}
// 如果执行到这一步，说明该点没有什么好遍历的了，从栈顶弹出
stack.pop();
}
}
/**
* 非递归方式广度优先遍历
*
* @param map
*/
public static void BFS_NotRecursion(int[][] map) {
Queue queue = new Queue();
boolean[] mapUsed = new boolean[10];
for (int i = 1; i < map.length; i++) {
if (!mapUsed[i]) {
mapUsed[i] = true;
System.out.print(i + " ");
// 将i排入队列
queue.enQueue(i);
// 如果队列不空，就接着执行
while (!queue.isEmpty()) {
// 取得队列的第一个值
int next = queue.deQueue();
for (int j = 1; j < 10; j++) {
if (!mapUsed[j] && map[next][j] < 1000) {
// 访问j
mapUsed[j] = true;
System.out.print(j + " ");
// 将j排入队列
queue.enQueue(j);
}
}
}
}
}
}
/**
* Prim算法求最小生成树
*
* @param map
* @return
*/
public static void Prim(int n, int[][] map) {
// 权重
int[] lowcost = new int[n + 1];
// 相邻结点
int[] closest = new int[n + 1];
boolean[] s = new boolean[n + 1];
s[1] = true;
for (int i = 2; i <= n; i++) {
lowcost[i] = map[1][i];
closest[i] = 1;
}
// 取得lowcost中最小值的点
for (int i = 1; i < n; i++) {
int min = Integer.MAX_VALUE;
int j = 1;
for (int k = 2; k <= n; k++) {
if ((lowcost[k] < min) && (!s[k])) {
min = lowcost[k];
j = k;
}
}
// 访问j结点
System.out.println(j + ", " + closest[j]);
s[j] = true;
// 依次遍历k，找出j到k结点的最小值，给lowcost[k]
// 距离k最近的结点为：closest[k]=j
for (int k = 2; k <= n; k++) {
if ((map[j][k] < lowcost[k]) && (!s[k])) {
lowcost[k] = map[j][k];
closest[k] = j;
}
}
}
}
/**
* Kruskal算法求最小生成树
*
* @param edges
* @return
*/
public static void Kruskal(Edge edges[]) {
int[] parent = new int[100];
// 冒泡排序，将edges数组中的Edge按weight升序排列
for (int i = edges.length - 1; i > 0; i--) {
for (int j = 1; j < i; j++) {
if (edges[j].weight > edges[j + 1].weight) {
int bTemp = edges[j].begin;
int eTemp = edges[j].end;
int wTemp = edges[j].weight;
edges[j].begin = edges[j + 1].begin;
edges[j].end = edges[j + 1].end;
edges[j].weight = edges[j + 1].weight;
edges[j + 1].begin = bTemp;
edges[j + 1].end = eTemp;
edges[j + 1].weight = wTemp;
}
}
}
for (int i = 1; i < edges.length; i++) {
// 寻找指向i边头结点的结点
int n = Find(parent, edges[i].begin);
// 寻找指向i边尾结点的结点
int m = Find(parent, edges[i].end);
// 如果没有形成回路
// 因为parent的值都在一条树枝上，即如果i.begin和i.end在一条树枝上，则n必定与m相等
if (n != m) {
// 指向n结点的是m结点
parent[n] = m;
System.out.println(edges[i].begin + " " + edges[i].end + " "
+ edges[i].weight);
}
}
}
/**
* 寻找相连结点
*
* @param parent
* @param f
* @return
*/
public static int Find(int[] parent, int f) {
// 直到一条链最后的那个结点
while (parent[f] > 0) {
f = parent[f];
}
// 返回该结点
return f;
}
}
/**
* 边
*
* weight:权重
*
* begin:起始结点
*
* end:结束结点
*
* @author wanfeng
*
*/
class Edge {
public int weight;
public int begin, end;
Edge(int uu, int vv, int ww) {
begin = uu;
end = vv;
weight = ww;
}
}
/**
* 数据结构：栈
*
*
* @author wanfeng
*
*/
class Stack {
private int[] element;
private int length;
public Stack() {
element = new int[100];
length = -1;
}
/**
* 将元素压入栈顶
*
* @param integer
*/
public void push(int integer) {
length++;
element[length] = integer;
}
/**
* 得到栈顶元素
*
* @return
*/
public int getTop() {
return element[length];
}
/**
* 得到并删除栈顶元素
*
* @return
*/
public int pop() {
int res = element[length];
length--;
return res;
}
/**
* 因为初始值为-1，所以与-1进行判断
*
* @return
*/
public boolean isEmpty() {
return length == -1;
}
}
/**
* 数据结构：队列
*
* @author wanfeng
*
*/
class Queue {
private int[] element;
private int length;
public Queue() {
element = new int[100];
length = 0;
}
public void enQueue(int integer) {
element[length] = integer;
length++;
}
public int deQueue() {
int res = element[0];
for (int i = 0; i < length; i++) {
element[i] = element[i + 1];
}
length--;
return res;
}
public boolean isEmpty() {
return length == 0;
}
}