有向图广度优先遍历 有向图 广度优先遍历 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 package des;import java.util.*;public class GraphErgodic { // 存储节点信息 private Object[] vertices; // 存储边的信息 private int[][] arcs; private int vexnum; // 记录第i个节点是否被访问过 private boolean[] visited; /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub GraphErgodic g = new GraphErgodic(8); Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' }; g.addVertex(vertices); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(1, 4); g.addEdge(3, 7); g.addEdge(4, 7); g.addEdge(2, 5); g.addEdge(2, 6); System.out.println("深度优先遍历:"); g.depthTraverse(); System.out.println(); System.out.println("广度优先遍历:"); g.broadTraverse(); System.out.println(); System.out.println("深度优先遍历非递归:"); g.depth(); System.out.println(); } public GraphErgodic(int n) { vexnum = n; vertices = new Object[n]; arcs = new int[n][n]; visited = new boolean[n]; for (int i = 0; i < vexnum; i++) { for (int j = 0; j < vexnum; j++) { arcs[i][j] = 0; } } } public void addVertex(Object[] obj) { this.vertices = obj; } public void addEdge(int i, int j) { if (i == j) return; arcs[i][j] = 1; arcs[j][i] = 1; } public int firstAdjVex(int i) { for (int j = 0; j < vexnum; j++) { if (arcs[i][j] > 0) return j; } return -1; } public int nextAdjVex(int i, int k) { for (int j = k + 1; j < vexnum; j++) { if (arcs[i][j] > 0) return j; } return -1; } // 深度优先遍历 public void depthTraverse() { for (int i = 0; i < vexnum; i++) { visited[i] = false; } for (int i = 0; i < vexnum; i++) { if (!visited[i]) traverse(i); } } // 一个连通图的深度递归遍历 public void traverse(int i) { // TODO Auto-generated method stub visited[i] = true; visit(i); for (int j = this.firstAdjVex(i); j >= 0; j = this.nextAdjVex(i, j)) { if (!visited[j]) this.traverse(j); } } // 广度优先遍历 public void broadTraverse() { // LinkedList实现了Queue接口 Queue<Integer> q = new LinkedList<Integer>(); for (int i = 0; i < vexnum; i++) { visited[i] = false; } for (int i = 0; i < vexnum; i++) { if (!visited[i]) { q.add(i); visited[i] = true; visit(i); while (!q.isEmpty()) { int j = (Integer) q.remove().intValue(); for (int k = this.firstAdjVex(j); k >= 0; k = this .nextAdjVex(j, k)) { if (!visited[k]) { q.add(k); visited[k] = true; visit(k); } } } } } } private void visit(int i) { // TODO Auto-generated method stub System.out.print(vertices[i] + " "); } // 深度非递归遍历 public void depth() { Stack<Integer> s = new Stack<Integer>(); for (int i = 0; i < vexnum; i++) { visited[i] = false; } for (int i = 0; i < vexnum; i++) { if (!visited[i]) { s.add(i); // 设置第i个元素已经进栈 visited[i] = true; while (!s.isEmpty()) { int j = (Integer) s.pop(); visit(j); for (int k = this.lastAdjVex(j); k >= 0; k = this .lastAdjVex(j, k)) { if (!visited[k]) { s.add(k); visited[k] = true; } } } } } } // 最后一个 public int lastAdjVex(int i) { for (int j = vexnum - 1; j >= 0; j--) { if (arcs[i][j] > 0) return j; } return -1; } // 上一个 public int lastAdjVex(int i, int k) { for (int j = k - 1; j >= 0; j--) { if (arcs[i][j] > 0) return j; } return -1; }} 这个顶点是确定的吧,我想可以变顶点~ g.broadTraverse(v); JTable的使用 菜鸟 求教!! hql中直接类型转换问题 一个很低级问题的java问题 那位仁兄看看这段错误代码的涵义? 请问用java做比较漂亮的界面用什么工具方便? 一个简单的java程序 java中怎么取得系统时间? CyberH() 朋友请进!!有事请问 谢谢!! 为什么从sun官方网站下的jdk无法打开? java 解析文本文件 中换行问题 java 如何获取指定ip地址的电脑上的盘符目录
package des;import java.util.*;public class GraphErgodic {
// 存储节点信息
private Object[] vertices;
// 存储边的信息
private int[][] arcs;
private int vexnum;
// 记录第i个节点是否被访问过
private boolean[] visited; /**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
GraphErgodic g = new GraphErgodic(8);
Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
g.addVertex(vertices);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(3, 7);
g.addEdge(4, 7);
g.addEdge(2, 5);
g.addEdge(2, 6);
System.out.println("深度优先遍历:");
g.depthTraverse();
System.out.println(); System.out.println("广度优先遍历:");
g.broadTraverse();
System.out.println(); System.out.println("深度优先遍历非递归:");
g.depth();
System.out.println();
} public GraphErgodic(int n) {
vexnum = n;
vertices = new Object[n];
arcs = new int[n][n];
visited = new boolean[n];
for (int i = 0; i < vexnum; i++) {
for (int j = 0; j < vexnum; j++) {
arcs[i][j] = 0;
}
} } public void addVertex(Object[] obj) {
this.vertices = obj;
} public void addEdge(int i, int j) {
if (i == j)
return;
arcs[i][j] = 1;
arcs[j][i] = 1;
} public int firstAdjVex(int i) {
for (int j = 0; j < vexnum; j++) {
if (arcs[i][j] > 0)
return j;
}
return -1;
} public int nextAdjVex(int i, int k) {
for (int j = k + 1; j < vexnum; j++) {
if (arcs[i][j] > 0)
return j;
}
return -1;
} // 深度优先遍历
public void depthTraverse() {
for (int i = 0; i < vexnum; i++) {
visited[i] = false;
}
for (int i = 0; i < vexnum; i++) {
if (!visited[i])
traverse(i);
}
} // 一个连通图的深度递归遍历
public void traverse(int i) {
// TODO Auto-generated method stub
visited[i] = true;
visit(i);
for (int j = this.firstAdjVex(i); j >= 0; j = this.nextAdjVex(i, j)) {
if (!visited[j])
this.traverse(j);
}
} // 广度优先遍历
public void broadTraverse() {
// LinkedList实现了Queue接口
Queue<Integer> q = new LinkedList<Integer>();
for (int i = 0; i < vexnum; i++) {
visited[i] = false;
}
for (int i = 0; i < vexnum; i++) {
if (!visited[i]) {
q.add(i);
visited[i] = true;
visit(i);
while (!q.isEmpty()) {
int j = (Integer) q.remove().intValue(); for (int k = this.firstAdjVex(j); k >= 0; k = this
.nextAdjVex(j, k)) {
if (!visited[k]) {
q.add(k);
visited[k] = true;
visit(k);
}
} }
}
}
} private void visit(int i) {
// TODO Auto-generated method stub
System.out.print(vertices[i] + " ");
} // 深度非递归遍历
public void depth() {
Stack<Integer> s = new Stack<Integer>();
for (int i = 0; i < vexnum; i++) {
visited[i] = false;
}
for (int i = 0; i < vexnum; i++) {
if (!visited[i]) {
s.add(i);
// 设置第i个元素已经进栈
visited[i] = true;
while (!s.isEmpty()) {
int j = (Integer) s.pop();
visit(j);
for (int k = this.lastAdjVex(j); k >= 0; k = this
.lastAdjVex(j, k)) {
if (!visited[k]) {
s.add(k);
visited[k] = true;
}
}
}
}
}
} // 最后一个
public int lastAdjVex(int i) {
for (int j = vexnum - 1; j >= 0; j--) {
if (arcs[i][j] > 0)
return j;
}
return -1;
} // 上一个
public int lastAdjVex(int i, int k) {
for (int j = k - 1; j >= 0; j--) {
if (arcs[i][j] > 0)
return j;
}
return -1;
}
}
这个顶点是确定的吧,我想可以变顶点~ g.broadTraverse(v);