Java 实现图的存储和创建，linux 编程基础课后答案第二章
this.name = name;
this.first = null;
}
}
怎样创建图？
由于是控制台应用，所以我选择创建图的方法自然是通过用户从键盘输入。具体为以下步骤：
输入图的顶点个数；
输入图的边个数；
输入各个顶点的名称，在一行内输入，以空格分隔。例如：有四个顶点，做如下输入：
A B C D；依次输入各条边的信息，具体做法是：有几条边就输入几行信息，每行表示一条边，以这种形式
"A 5 B"来表示一条边,其表示这条边连接 A,B 两个顶点，权值为 5.
实现代码
public void create(){
//以用户输入方式构造图
Scanner scanner = new Scanner(System.in);
int vexNumIn = this.vexNum;
int arcNumIn = this.arcNum;
if(this.vexNum == 0){
System.out.print("请输入顶点个数:");
vexNumIn = scanner.nextInt();
System.out.print("请输入边的个数:");
arcNumIn = scanner.nextInt();
scanner.nextLine();
}
System.out.println("请输入" + vexNumIn + "个顶点的名称，以空格分隔:");
String tmpStr = scanner.nextLine(); //临时字符串
String[] tmpDatas = tmpStr.split(" "); //临时数据列表
for (int i = 0; i < vexNumIn; i++) {
this.addNode(new VNode(tmpDatas[i]));
}
System.out.println("请输入" + arcNumIn + "条边的数据，每条占一行，形如: a b 5, 其中 a 为顶点 1，b 为顶点 2，5 为权值:");
int tmpCount = 0; //保存一个临时数据，表示当前已输入了几条边
while (tmpCount < arcNumIn){
tmpStr = scanner.nextLine();
tmpDatas = tmpStr.split(" ");
if(this.containVnode(tmpDatas[0]) >= 0&&this.containVnode(tmpDatas[1]) >= 0){
//当该边连接的两个顶点都存在时才能添加边
this.addArc(new ArcNode(this.getVNodeByName(tmpDatas[0]),this.getVNodeByName(tmpDatas[1]),
Integer.parseInt(tmpDatas[2])));
tmpCount ++; //成功添加一条边，标志位加一
}else{
for (int k = 0; k < 2; k++) {
if(!(this.containVnode(tmpDatas[0]) >= 0)){
//为不存在的顶点给出提示信息并重新输入
System.out.println("不存在顶点" + tmpDatas[k] + ",请重新输入该边");
break;
}
}
}
}
}
两个辅助创建图的方法
添加顶点
向图中添加顶点非常简单，只需要将邻接表增加一项并把顶点数加一即可。
public void addNo
de(VNode vnode){
//添加顶点
this.vertices.add(vnode);
this.vexNum ++;
}
添加边
向图中添加边稍难一些，因为要添加边首先要在邻接表中找到待添加边所连接的两个顶点，另外由于是无向图，所以每条边将会被添加两次，也就是在它所连接的两个顶点的边表中各出现一次。实现代码如下
public void addArc(ArcNode arcNode){
//添加边
boolean isAdded = false; //标记是否添加成功
for (VNode node:this.vertices) {
if(node.getName().equals(arcNode.getNode1().getName()) || node.getName().equals(arcNode.getNode2().getName())){
//找到对应顶点
/*这里必须复制一个 arcNode 的副本，不能只是简单地引用它否则有如下问题
添加 arcNode=(A,1,B)时
匹配到 A 时，会改变 arcNode.next 的值，当在匹配到 B 时又会改变一次导致 A 的边表发生变化
*/
ArcNode tmpArcNode = new ArcNode(arcNode);
//头插法插入新边
tmpArcNode.next = node.first;
node.first = tmpArcNode;
isAdded = true;
}
}
//如果添加成功就将边数目加 1
this.arcNum = isAdded == true?this.arcNum + 1 : this.arcNum;
}
在控制台展示图
由于直接在控制台展示图的原始形态，也就是把图画出来太过困难，于是我选择直接将图的邻接表打印在控制台上。具体的实现效果将在最后展示，实现代码如下：
public void showGraph(){
//展示图
for (VNode node: this.vertices) {
System.out.print(node.getName());
ArcNode tmpArcNode = node.first;
while (tmpArcNode!=null){
System.out.print("->" + tmpArcNode.toString());
tmpArcNode = tmpArcNode.next;
}
System.out.println();
}
}
运行效果
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论