1.思路图解兼样例：接下来将用此图例作为测试用例
2.输出结果：
（1）邻接矩阵：
（2）邻接表：
一、邻接矩阵
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
public class AdjacencyMatrix {
private ArrayList<String> vexs; // 顶点表
private int[][] edges; // 边表
int numVertexes;
int numEdges;
boolean[] visited;
public AdjacencyMatrix(int numVertexes, int numEdges) {
this.numVertexes = numVertexes;
this.numEdges = numEdges;
this.vexs = new ArrayList<String>(numVertexes);
this.edges = new int[numVertexes][numVertexes];
this.visited = new boolean[numVertexes];
}
private void insertVex(String v) {
vexs.add(v);
}
private void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
}
private void show() {
for (int[] link : edges) {
System.out.println(Arrays.toString(link));
}
}
private void DFS(int i) {
visited[i] = true;
System.out.print(vexs.get(i) + " ");
for (int j = 0; j < numVertexes; j++) {
if (edges[i][j] > 0 && !visited[j]) {
DFS(j);
}
}
}
private void DFSTraverse() {
int i;
for (i = 0; i < numVertexes; i++) {
visited[i] = false;
}
for (i = 0; i < numVertexes; i++) {
if (!visited[i]) {
DFS(i);
}
}
}
private void BFSTraverse() {
int i, j;
LinkedList queue = new LinkedList();
for (i = 0; i < numVertexes; i++) {
visited[i] = false;
}
for (i = 0; i < numVertexes; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.print(vexs.get(i) + " ");
queue.addLast(i);
while (!queue.isEmpty()) {
i = (Integer) queue.removeFirst();
for (j = 0; j < numVertexes; j++) {
if (edges[i][j] > 0 && !visited[j]) {
visited[j] = true;
System.out.print(vexs.get(j) + " ");
queue.addLast(j);
}
}
}
}
}
}
public static void main(String[] args) {
int numVertexes = 9;
int numEdges = 15;
AdjacencyMatrix graph = new AdjacencyMatrix(numVertexes, numEdges);
graph.insertVex("A");
graph.insertVex("B");
graph.insertVex("C");
graph.insertVex("D");
graph.insertVex("E");
graph.insertVex("F");
graph.insertVex("G");
graph.insertVex("H");
graph.insertVex("I");
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 5, 1);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 6, 1);
graph.insertEdge(1, 8, 1);
graph.insertEdge(2, 3, 1);
graph.insertEdge(2, 8, 1);
graph.insertEdge(3, 4, 1);
graph.insertEdge(3, 6, 1);
graph.insertEdge(3, 7, 1);
graph.insertEdge(3, 8, 1);
graph.insertEdge(4, 7, 1);
graph.insertEdge(4, 5, 1);
graph.insertEdge(5, 6, 1);
graph.insertEdge(6, 7, 1);
System.out.println("邻接矩阵");
graph.show();
System.out.print("深度优先遍历：");
graph.DFSTraverse();
System.out.println();
System.out.print("广度优先遍历：");
graph.BFSTraverse();
}
}
二、邻接表
import java.util.ArrayList;
import java.util.LinkedList;
class EdgeNode {
int vex;
int adjvex; // 邻接点域，存储该顶点对应的下标
int weight;
EdgeNode next;
public EdgeNode(int vex, int adjvex, int weight) {
this.vex = vex;
this.adjvex = adjvex;
this.weight = weight;
this.next = null;
}
}
class VertexNode {
String data; // 顶点域，存储顶点信息
EdgeNode firstedge; // 边表头
public VertexNode(String data) {
this.data = data;
this.firstedge = null;
}
}
public class AdjacencyList {
private ArrayList<VertexNode> vexs; // 顶点表
int numVertexes;
int numEdges;
boolean[] visited;
public AdjacencyList(int numVertexes, int numEdges) {
this.numVertexes = numVertexes;
this.numEdges = numEdges;
this.vexs = new ArrayList<VertexNode>(numVertexes);
this.visited = new boolean[numVertexes];
}
private void insertVex(VertexNode v) {
vexs.add(v);
}
private void insertEdge(EdgeNode e) {
int i = e.vex; // 顶点表中对应结点的下标
int j = e.adjvex; // 边表结点对应的下标
VertexNode vexi = vexs.get(i);
VertexNode vexj = vexs.get(j);
e.next = vexi.firstedge;
vexi.firstedge = e;
EdgeNode e2 = new EdgeNode(j, i, 1);
e2.next = vexj.firstedge;
vexj.firstedge = e2;
}
private void show() {
for (int i = 0; i < numVertexes; i++) {
VertexNode vex = vexs.get(i);
System.out.print("【" + vex.data + "】—>");
EdgeNode node = vex.firstedge;
while (node != null) {
System.out.print(vexs.get(node.adjvex).data + "(" + node.adjvex + ")" + "->");
node = node.next;
}
System.out.print("null");
System.out.println();
}
}
private void DFS(int i) {
EdgeNode p;
visited[i] = true;
System.out.print(vexs.get(i).data + " ");
p = vexs.get(i).firstedge;
while (p != null) {
if (!visited[p.adjvex]) {
DFS(p.adjvex);
}
p = p.next;
}
}
private void DFSTraverse() {
int i;
for (i = 0; i < numVertexes; i++) {
visited[i] = false;
}
for (i = 0; i < numVertexes; i++) {
if (!visited[i]) {
DFS(i);
}
}
}
private void BFSTraverse() {
EdgeNode p;
int i;
LinkedList queue = new LinkedList();
for (i = 0; i < numVertexes; i++) {
visited[i] = false;
}
for (i = 0; i < numVertexes; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.print(vexs.get(i).data + " ");
queue.addLast(i);
while (!queue.isEmpty()) {
i = (Integer) queue.removeFirst();
p = vexs.get(i).firstedge;
while (p != null) {
if (!visited[p.adjvex]) {
visited[p.adjvex] = true;
System.out.print(vexs.get(p.adjvex).data + " ");
queue.addLast(p.adjvex);
}
p = p.next;
}
}
}
}
}
public static void main(String[] args) {
int numVertexes = 9;
int numEdges = 15;
AdjacencyList graph = new AdjacencyList(numVertexes, numEdges);
graph.insertVex(new VertexNode("A"));
graph.insertVex(new VertexNode("B"));
graph.insertVex(new VertexNode("C"));
graph.insertVex(new VertexNode("D"));
graph.insertVex(new VertexNode("E"));
graph.insertVex(new VertexNode("F"));
graph.insertVex(new VertexNode("G"));
graph.insertVex(new VertexNode("H"));
graph.insertVex(new VertexNode("I"));
graph.insertEdge(new EdgeNode(0, 1, 1));
graph.insertEdge(new EdgeNode(0, 5, 1));
graph.insertEdge(new EdgeNode(1, 2, 1));
graph.insertEdge(new EdgeNode(1, 6, 1));
graph.insertEdge(new EdgeNode(1, 8, 1));
graph.insertEdge(new EdgeNode(2, 3, 1));
graph.insertEdge(new EdgeNode(2, 8, 1));
graph.insertEdge(new EdgeNode(3, 4, 1));
graph.insertEdge(new EdgeNode(3, 6, 1));
graph.insertEdge(new EdgeNode(3, 7, 1));
graph.insertEdge(new EdgeNode(3, 8, 1));
graph.insertEdge(new EdgeNode(4, 7, 1));
graph.insertEdge(new EdgeNode(4, 5, 1));
graph.insertEdge(new EdgeNode(5, 6, 1));
graph.insertEdge(new EdgeNode(6, 7, 1));
System.out.println("邻接表");
graph.show();
System.out.print("深度优先遍历：");
graph.DFSTraverse();
System.out.println();
System.out.print("广度优先遍历：");
graph.BFSTraverse();
}
}