赞
踩
题目要求:
1.对于下图所示的有向图(访问顺序按序号从小到大),试写出:
(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树;
(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树。
- package com.test.tree;
- import java.util.*;
-
- public class Graph {
- // 存储节点信息
- private Object[] vertices;
- // 存储边的信息
- private int[][] arcs;
- private int vexnum;
- // 记录第i个节点是否被访问过
- private boolean[] visited;
-
- /**
- * @param args
- */
- public static void main(String[] args) {
- Graph g = new Graph(5);
- Character[] vertices = { '1', '2', '3', '4', '5'};
- g.addVertex(vertices);
- g.addEdge(0, 1);
- g.addEdge(0, 2);
- g.addEdge(1, 2);
- g.addEdge(1, 3);
- g.addEdge(1, 4);
- g.addEdge(2, 3);
- g.addEdge(3, 4);
- g.addEdge(4, 0);
-
-
- System.out.println("深度优先遍历:");
- g.depthTraverse();
- System.out.println();
-
- System.out.println("广度优先遍历:");
- g.broadTraverse2(1);
- System.out.println();
-
- }
-
- public Graph(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 broadTraverse2(int n) {
- // LinkedList实现了Queue接口
- Queue<Integer> q = new LinkedList<Integer>();
- for (int i = 0; i < vexnum; i++) {
- visited[i] = false;
- }
- if (!visited[n]) {
- q.add(n);
- visited[n] = true;
- visit(n);
- while (!q.isEmpty()) {
- int j = (Integer) q.remove().intValue();
- int k = this.firstAdjVex(j);
- for ( k = this.firstAdjVex(j); k >= 0; k = this
- .nextAdjVex(j, k)) {
- if (!visited[k]) {
- q.add(k);
- visited[k] = true;
- visit(k);
- }
- }
-
- }
- }
- }
-
- // 广度优先遍历 默认从0开始
- public void broadTraverse(int n) {
- // 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 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;
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。