无向图的广度优先遍历跟深度优先遍历

无向图的广度优先遍历和深度优先遍历
public class MGraph {
private char[] vexs;// 顶点
private int[][] edge;// 存储边的二维数组
private int arcNum;// 边的数目
private boolean[] visited;// 访问标志数组

// 确定顶点在图中的位置
public int locataVex(char vex) {
for (int i = 0; i < vexs.length; i++) {
if (vex == vexs[i]) {
return i;
}
}
return -1;
}

// 构造无向图
public MGraph(int vexNo) throws IOException {
// 初始化访问数组
visited = new boolean[vexNo];
for (int i = 0; i < vexNo; i++) {
visited[i] = false;

}
// 顶点初始化
vexs = new char[vexNo];
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));
for (int i = 0; i < vexNo; i++) {
String value = reader.readLine();
char c = value.charAt(0);
vexs[i] = c;
}
// 初始化边的二维数组 默认都不相连 用0来表示
edge = new int[vexNo][vexNo];
for (int i = 0; i < vexNo; i++) {
for (int j = 0; j < vexNo; j++) {
edge[i][j] = 0;
}
}
// 输入边的数目
arcNum = Integer.parseInt(reader.readLine());
// 输入边的信息
for (int i = 0; i < arcNum; i++) {
System.out.println("请输入一条边所依附的两个顶点");
String value1 = reader.readLine();
char v1 = value1.charAt(0);
String value2 = reader.readLine();
char v2 = value2.charAt(0);

int m = locataVex(v1);
int n = locataVex(v2);

edge[m][n] = 1;
edge[n][m] = 1;
}
}

// v是图中的某个结点 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1
public int FirstAdjVex(char v) {
int i;
// 先确定v在顶点数组中的位置
i = locataVex(v);

// 返回第一个邻接定点的序号

for (int j = 0; j < vexs.length; j++) {
if (edge[i][j] == 1) {

return j;
}
}
// 如果没有邻接结点 则返回-1
return -1;

}

// int NextAdjVex(MGraph G,VertexType v,VertexType w)初始条件:
// 图G存在,v是G中某个顶点,w是v的邻接顶点 */
// 返回v的(相对于w的)下一个邻接顶点的序号 如果w是v的最后一个结点 则返回-1
public int NextAdjVex(char v, char w) {
int i;
// 先确定v在顶点数组中的位置
i = locataVex(v);

// 返回第一个邻接定点的序号
int j = locataVex(w);
for (j = j + 1; j < vexs.length; j++) {
if (edge[i][j] == 1) {

return j;
}
}
// 如果没有邻接结点 则返回-1
return -1;

}

// 深度优先遍历图 从第v个顶点开始
public void DFsTraverse(int v) {

// 对v尚未访问的邻接顶点进行DFS
for (int i = 0; i < vexs.length; i++) {
if (visited[i] == false) {
DFS(i);
}
}

}

public void DFS(int v) {
// 访问v结点
visited[v] = true;
System.out.println(vexs[v]);

for (int i = FirstAdjVex(vexs[v]); i >= 0; i = NextAdjVex(vexs[v],
vexs[i])) {
if (visited[i] == false) {
DFS(i);
}
}

}

// 广度优先遍历图

public void BFSTraverse() {
// 初始化队列
Queue queue = new LinkedList();
for (int i = 0; i < vexs.length; i++) {
if (visited[i] == false) {
queue.add(i);
while (!queue.isEmpty()) {
int v = (Integer) queue.remove();
if (visited[v] == false) {
visited[v] = true;
System.out.println(vexs[v]);
}
for (int j = FirstAdjVex(vexs[v]); j >= 0; j = NextAdjVex(
vexs[v], vexs[j])) {
if (visited[j] == false) {
queue.add(j);
}
}

}
}
}
}

public char[] getVexs() {
return vexs;
}

public void setVexs(char[] vexs) {
this.vexs = vexs;
}

public int[][] getEdge() {
return edge;
}

public void setEdge(int[][] edge) {
this.edge = edge;
}

public int getArcNum() {
return arcNum;
}

public void setArcNum(int arcNum) {
this.arcNum = arcNum;
}

public boolean[] getVisited() {
return visited;
}

public void setVisited(boolean[] visited) {
this.visited = visited;
}

}

//当用邻接矩阵来表示图的时候，其中图的深度优先遍历的算法时间复杂度是0(n*n)，而BFS 算法的时间复杂度为 O(n+e) ，此处 e 为无向图中边的数目或有向图中弧的数目