Java实现无向图的建立与遍历

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

一、基于邻接矩阵表示法的无向图

邻接矩阵是一种利用一维数组记录点集信息、二维数组记录边集信息来表示图的表示法，因此我们可以将图抽象成一个类，点集信息和边集信息抽象成类的属性，就可以在Java中描述出来，代码如下：

class AMGraph{ private String[] vexs = null; //点集信息 private int[][] arcs = null; //边集信息 }

每一个具体的图，就是该类的一个实例化对象，因此我们可以在构造函数中实现图的创建，代码如下：

public AMGraph(int vexNum,int arcNum) { //输入点的个数和边的个数 this.vexs = new String[vexNum];
this.arcs = new int[vexNum][vexNum]; System.out.print("请依次输入顶点值，以空格隔开：");
Scanner sc = new Scanner(System.in);
for(int i = 0; i < vexNum; i++) { //根据输入建立点集
this.vexs[i] = sc.next();
} for(int i = 0; i < vexNum; i++) { //初始化边集
for(int j = 0; j < vexNum; j++) {
this.arcs[i][j] = 0; //0表示该位置所对应的两顶点之间没有边
}
} start:for(int i = 0; i < arcNum; i++) { //开始建立边集 sc = new Scanner(System.in);
int vex1Site = 0;
int vex2Site = 0;
String vex1 = null;
String vex2 = null; System.out.print("请输入第" + (i+1) + "条边所依附的两个顶点，以空格隔开：");
vex1 = sc.next();
vex2 = sc.next();
for(int j = 0; j < this.vexs.length; j++) { //查找输入的第一个顶点的位置
if (this.vexs[j].equals(vex1)) {
vex1Site = j;
break;
}
if (j == this.vexs.length - 1) {
System.out.println("未找到第一个顶点，请重新输入！");
i--;
continue start;
}
}
for (int j = 0; j < this.vexs.length; j++) { //查找输入的第二个顶点的位置
if(this.vexs[j].equals(vex2)) {
vex2Site = j;
break;
}
if (j == this.vexs.length - 1) {
System.out.println("未找到第二个顶点，请重新输入！");
i--;
continue start;
}
}
if(this.arcs[vex1Site][vex2Site] != 0) { //检测该边是否已经输入
System.out.println("该边已存在！");
i--;
continue start;
}else {
this.arcs[vex1Site][vex2Site] = 1; //1表示该位置所对应的两顶点之间有边
this.arcs[vex2Site][vex1Site] = 1; //对称边也置1
}
}
System.out.println("基于邻接矩阵的无向图创建成功！");
sc.close();
}

创建好图后，我们还要实现图的遍历。由于图已经被我们抽象成一个类，因此我们可以将图的遍历定义成类的方法。对于连通图，调用遍历算法后即可访问所有结点，但对于非连通图，调用遍历算法后仍有一些结点没有被访问，需要从图中另选一个未被访问的顶点再次调用遍历算法。因此需要附设一个访问标志数组visited[n]，来记录被访问的结点。增加了访问标志数组的类属性如下：

class AMGraph{ private String[] vexs = null; private int[][] arcs = null; private boolean[] visited = null; //false表示该位置的顶点未访问，true表示已访问 }

图的遍历分为深度优先遍历和广度优先遍历，接下来我们来分别实现它们。深度优先遍历代码如下：

public void dFSTraverse() { this.visited = new boolean[this.vexs.length]; //初始化访问标志数组
for(int i = 0; i < this.visited.length; i++) {
this.visited[i] = false;
} for(int i = 0; i < this.visited.length; i++) {
if(!this.visited[i]) { //对未访问的顶点调用深度优先遍历算法
dFS_AM(i);
}
}
}

public void dFS_AM(int site) { //输入深度优先遍历的开始顶点
System.out.println(this.vexs[site]); //输出该顶点
this.visited[site] = true; //置访问标志为true
for(int i = 0; i < this.vexs.length; i++) { //依次查找未访问邻接点，并以该邻接点为始点调用深度优先遍历算法
if(this.arcs[site][i] != 0 && !this.visited[i]) {
this.dFS_AM(i);
}
}
}

广度优先遍历代码如下：

public void bFSTraverse() { this.visited = new boolean[this.vexs.length]; //初始化访问标志数组
for(int i = 0; i < this.visited.length; i++) {
this.visited[i] = false;
} for(int i = 0; i < this.visited.length; i++) {
if(!this.visited[i]) { //对未访问的顶点调用广度优先遍历算法
bFS_AM(i);
}
}
}

public void bFS_AM(int site) { //输入开始顶点
System.out.println(this.vexs[site]); //输出该顶点
this.visited[site] = true; //置访问标志为true
LinkedList<Integer> linkedList = new LinkedList<Integer>(); //借助队列来实现广度优先遍历
linkedList.offer(site); //将访问过的顶点入队
while(!linkedList.isEmpty()) {
int vexSite = linkedList.poll(); //队头顶点出队
for(int i = 0; i < this.vexs.length; i++) {
if(this.arcs[vexSite][i] != 0 && !this.visited[i]) { //依次查找未访问的邻接点进行访问后入队
System.out.println(this.vexs[i]);
this.visited[i] = true;
linkedList.offer(i);
}
}
}
}

以上基于邻接矩阵表示法的无向图的类就定义好了，接着我们在客户端里使用即可：

public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in);
int vexNum = 0;
int arcNum = 0;
while(true) {
System.out.print("请输入要建立无向图的总顶点数和总边数，以空格隔开：");
try {
vexNum = sc.nextInt();
arcNum = sc.nextInt();
break;
} catch (Exception e) {
System.out.println("输入不合法！");
continue;
}
} AMGraph aMGraph = new AMGraph(vexNum, arcNum);
System.out.println("由深度优先遍历得：");
aMGraph.dFSTraverse();
System.out.println("由广度优先遍历得：");
aMGraph.bFSTraverse(); sc.close();
} }

二、基于邻接表表示法的无向图

邻接表是一种基于链式存储结构的表示法。在邻接表中，对图的每个顶点建立一个单链表，单链表的第一个结点存放顶点信息，称为点结点，其余结点存放边信息，称为边结点。此外，还需要一个顶点数组，存储对所有单链表的引用。因此我们需要定义三个类，第一个类为顶点类，用来生成点结点；第二个类为边类，用来生成边结点；第三个类为图类，里面定义有属性——顶点数组和方法——图的遍历。代码如下：

class ALGraph_Head{ //顶点类 private String data = null; //点结点值 private ALGraph_Arc firstArc= null; //第一条边的指针 public String getData() {
return data;
} public ALGraph_Arc getFirstArc() {
return firstArc;
} public void setFirstArc(ALGraph_Arc firstArc) {
this.firstArc = firstArc;
} public ALGraph_Head(String data) {
this.data = data;
}
}

class ALGraph_Arc{ //边类 private int adjVexSite = 0; //该边所连接的顶点的邻接点的位置 private ALGraph_Arc nextArc = null; //下一条边的指针 public int getAdjVexSite() {
return adjVexSite;
} public ALGraph_Arc getNextArc() {
return nextArc;
} public ALGraph_Arc(int adjVexSite, ALGraph_Arc nextArc) {
this.adjVexSite = adjVexSite;
this.nextArc = nextArc;
}
}

class ALGraph{ //图类 private ALGraph_Head[] aLGraph_Heads = null; //顶点数组 }

同样的，我们在构造方法中进行图的建立，代码如下：

public ALGraph(int vexNum,int arcNum) { //输入顶点个数，边的个数 this.aLGraph_Heads = new ALGraph_Head[vexNum]; System.out.print("请依次输入顶点值，以空格隔开：");
Scanner sc = new Scanner(System.in);
for(int i = 0; i < vexNum; i++) { //建立顶点数组存储点结点
this.aLGraph_Heads[i] = new ALGraph_Head(sc.next());
} start:for(int i = 0; i < arcNum; i++) { //开始存储边信息 sc = new Scanner(System.in);
int vex1Site = 0;
int vex2Site = 0;
String vex1 = null;
String vex2 = null; System.out.print("请输入第" + (i+1) + "条边所依附的两个顶点，以空格隔开：");
vex1 = sc.next();
vex2 = sc.next();
for(int j = 0; j < this.aLGraph_Heads.length; j++) { //查找第一个顶点的位置
if (this.aLGraph_Heads[j].getData().equals(vex1)) {
vex1Site = j;
break;
}
if (j == this.aLGraph_Heads.length - 1) {
System.out.println("未找到第一个顶点，请重新输入！");
i--;
continue start;
}
}
for (int j = 0; j < this.aLGraph_Heads.length; j++) { //查找第二个顶点的位置
if(this.aLGraph_Heads[j].getData().equals(vex2)) {
vex2Site = j;
break;
}
if (j == this.aLGraph_Heads.length - 1) {
System.out.println("未找到第二个顶点，请重新输入！");
i--;
continue start;
}
}
ALGraph_Arc aLGraph_Arc = this.aLGraph_Heads[vex1Site].getFirstArc(); //获取点结点里的边指针
while(aLGraph_Arc != null) { //判断边是否已存储
if(aLGraph_Arc.getAdjVexSite() == vex2Site) {
System.out.println("该边已存在！");
i--;
continue start;
}
aLGraph_Arc = aLGraph_Arc.getNextArc();
}
this.aLGraph_Heads[vex1Site].setFirstArc(new ALGraph_Arc(vex2Site, this.aLGraph_Heads[vex1Site].getFirstArc())); //将边结点加入单链表中
this.aLGraph_Heads[vex2Site].setFirstArc(new ALGraph_Arc(vex1Site, this.aLGraph_Heads[vex2Site].getFirstArc())); //对称边结点也加入单链表
}
System.out.println("基于邻接表的无向图创建成功！");
sc.close();
}

接着实现图的遍历，同样需要附设一个访问标志数组，因此将图类属性修改如下：

class ALGraph{ private ALGraph_Head[] aLGraph_Heads = null; private boolean[] visited = null; //访问标志数组 }

深度优先遍历：

public void dFSTraverse() { this.visited = new boolean[this.aLGraph_Heads.length]; //建立并初始化访问标志数组
for(int i = 0; i < this.visited.length; i++) {
this.visited[i] = false;
} for(int i = 0; i < this.visited.length; i++) { //以未访问的点为始点调用深度优先遍历算法
if(!this.visited[i]) {
dFS_AM(i);
}
}
}

public void dFS_AM(int site) {
System.out.println(this.aLGraph_Heads[site].getData()); //输出点值
this.visited[site] = true; //置访问标志为true
ALGraph_Arc aLGraph_Arc = this.aLGraph_Heads[site].getFirstArc(); //获取点结点中的边指针
while(aLGraph_Arc != null) {
if(!visited[aLGraph_Arc.getAdjVexSite()]) { //如果该边所连接的顶点的邻接点未访问，则以该邻接点为始点调用深度优先遍历算法
this.dFS_AM(aLGraph_Arc.getAdjVexSite());
}
aLGraph_Arc = aLGraph_Arc.getNextArc(); //获取下一条边
}
}

广度优先遍历：

public void bFSTraverse() { this.visited = new boolean[this.aLGraph_Heads.length]; //建立并初始化访问标志数组
for(int i = 0; i < this.visited.length; i++) {
this.visited[i] = false;
} for(int i = 0; i < this.visited.length; i++) { //以未访问的点为始点调用广度优先遍历算法
if(!this.visited[i]) {
bFS_AM(i);
}
}
}

public void bFS_AM(int site) {
System.out.println(this.aLGraph_Heads[site].getData()); //输出点值
this.visited[site] = true; //置访问标志为true
LinkedList<Integer> linkedList = new LinkedList<Integer>(); //利用队列实现广度优先遍历
linkedList.offer(site); //点入队
while(!linkedList.isEmpty()) {
int vexSite = linkedList.poll(); //点出队
ALGraph_Arc aLGraph_Arc = this.aLGraph_Heads[vexSite].getFirstArc(); //获取点结点中的边指针
while(aLGraph_Arc != null) {
vexSite = aLGraph_Arc.getAdjVexSite(); //获取该边所连接的顶点的邻接点
if(!this.visited[vexSite]) { //如果该邻接点未访问，则访问
System.out.println(this.aLGraph_Heads[vexSite].getData());
this.visited[vexSite] = true;
linkedList.offer(vexSite); //被访问的点入队
}
aLGraph_Arc = aLGraph_Arc.getNextArc(); //获取下一个邻接点
}
}
}

客户端代码如下：

public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in);
int vexNum = 0;
int arcNum = 0;
while(true) {
System.out.print("请输入要建立无向图的总顶点数和总边数，以空格隔开：");
try {
vexNum = sc.nextInt();
arcNum = sc.nextInt();
break;
} catch (Exception e) {
System.out.println("输入不合法！");
continue;
}
} ALGraph aLGraph = new ALGraph(vexNum, arcNum);
System.out.println("由深度优先遍历得：");
aLGraph.dFSTraverse();
System.out.println("由广度优先遍历得：");
aLGraph.bFSTraverse(); sc.close();
} }