图 package 实验三;/** * * @author 黄良运 * time：2017.12.6 * 枚举 * */public enum GraphKind {UDG , //无向图UnDirected GraphDG, //有向图Directed GraphUDN, //无向网 UnDirected NetworkDN,//有向网Directed Network}package 实
package 实验三;
/**
*
* @author 黄良运
* time：2017.12.6
* 枚举
*
*/
public enum GraphKind {
UDG , //无向图UnDirected Graph
DG, //有向图Directed Graph
UDN, //无向网 UnDirected Network
DN,//有向网Directed Network
}
package 实验三;
import java.util.Scanner;
/*
* author :黄良运
* time:2017.12.7
* 邻接表存储结构
*/
public class ALGraph
> {
private GraphKind kind;// 图的种类标志
private int vexNum, arcNum;// 图的顶点和边数
private VNode
[] vexs; Scanner in = new Scanner(System.in); public ALGraph(GraphKind kind, int vexNum, int arcNum, VNode
[] vexs) { super(); this.kind = kind; this.vexNum = vexNum; this.arcNum = arcNum; this.vexs = vexs; } public ALGraph() { this(null, 0, 0, null); } // 创建图 public void createGraph() { System.out.println("请输入图的类型"); GraphKind kind = GraphKind.valueOf(in.next()); switch (kind) { case UDG: createUDG(); return; case DG: createDG(); return; case UDN: createUDN(); return; case DN: createDN(); return; } } public void createUDG() { } public void createDG() { } public void createUDN() { System.out.println("请输入图的顶点数，图的边数"); vexNum = in.nextInt(); arcNum = in.nextInt(); vexs = new VNode[vexNum]; System.out.println("请分别输入图的各顶点"); for (int v = 0; v < vexNum; v++)// 构造顶点向量 vexs[v] = new VNode
((AnyType)in.next()); System.out.println("请输入各边顶点及其权值"); for (int k = 0; k < arcNum; k++) { int v = locateVex((AnyType)in.next()); int u = locateVex((AnyType)in.next()); int value = in.nextInt();// 权值 addArc(v, u, value); addArc(u, v, value); } } public void createDN() { System.out.println("请输入图的顶点数，图的边数"); vexNum = in.nextInt(); arcNum = in.nextInt(); vexs = new VNode[vexNum]; System.out.println("请分别输入图的各顶点"); for (int v = 0; v < vexNum; v++)// 构造顶点向量 vexs[v] = new VNode
((AnyType)in.next()); System.out.println("请输入各边顶点及其权值"); for (int k = 0; k < arcNum; k++) { int v = locateVex((AnyType)in.next()); int u = locateVex((AnyType)in.next()); int value = in.nextInt();// 权值 addArc(v, u, value); } } // 在顶点v，u之间添加一条弧，其权值为value public void addArc(int v, int u, int value) {// u该弧所指向的顶点位置，该顶点的位置 ArcNode
arc = new ArcNode
(u, value);// v1 v2 1 v2 v3 1 v2 v4 1 v3 v4 1 arc.nextArc = vexs[v].firstArc; vexs[v].firstArc = arc; } public void isValid_V(int v) throws Exception { if (v < 0 || v >= vexNum) throw new Exception("第" + v + "个顶点不存在"); } public int locateVex(AnyType vex) { for (int v = 0; v < vexNum; v++) if (vexs[v].data.compareTo(vex)==0) return v; return -1; } public int getVexNum() { return vexNum; } public int getArcNum() { return arcNum; } public VNode
[] getVexs() { return vexs; } public GraphKind getKind() { return kind; } public AnyType getVex(int index) throws Exception { isValid_V(index); return vexs[index].data;// 节点数组的数据 } public int firstAdjVex(int v) throws Exception { isValid_V(v); VNode
vex = vexs[v]; if (vex.firstArc != null) return vex.firstArc.adjVex;// 指向顶点1的位置 else return -1; } // 查找下一个邻接点的方法 public int nextAdjVex(int v, int w) throws Exception { isValid_V(v); VNode
vex = vexs[v]; ArcNode
arcvw = null; for (ArcNode
arc = vex.firstArc; arc != null; arc = arc.nextArc) { if (arc.adjVex == w) { arcvw = arc; break; } } if (arcvw != null && arcvw.nextArc != null) return arcvw.nextArc.adjVex; else return -1; } // 图的邻接表存储结构表示中的顶点节点类 public static class VNode
> { public AnyType data;// 顶点信息 public ArcNode
firstArc;// 指向第一条依附于该顶点的弧 public VNode() { this(null, null); } public VNode(AnyType data) { this(data, null); } public VNode(AnyType data, ArcNode
firstArc) { this.data = data; this.firstArc = firstArc; } } // 图中邻接表存储结构表示中的边节点类 public static class ArcNode
> { public int adjVex;// 该弧指向顶点的位置 public int value;// 边的权值 private ArcNode
nextArc;// 指向下一条弧 public ArcNode() { this(-1, 0, null); } public ArcNode(int adjVex) { this(adjVex, 0); } public ArcNode(int adjVex, int value) { this(adjVex, value, null); } public ArcNode(int adjVex, int value, ArcNode
nextArc) { super(); this.adjVex = adjVex; this.value = value; this.nextArc = nextArc; } } public static void main(String[] y) throws Exception { /** * v1 v2 v3 v4 v1 v2 1 v2 v4 1 v2 v3 1 v3 v4 1 //头插注意顺序 * 1 2 3 4 1 2 1 2 4 1 2 3 1 3 4 1 */ Scanner in = new Scanner(System.in); ALGraph
S = new ALGraph
(); S.createGraph(); System.out.println(S.firstAdjVex(2)); System.out.println(S.nextAdjVex(1, 2)); GraphTraverse.BFSTraverse(S); System.out.println(); GraphTraverse.DFSTraverse(S); System.out.println("请输入要查找的结点"); while (in.hasNext()) {// 0 1;1 3;2 2;3 2 String v = in.next(); //Character c = v.charAt(0); //System.out.println(S.getDegree(v)+"个"); } } } package 实验三; import java.util.LinkedList; import java.util.Queue; /** * * @author 黄良运 * time：2017.12.6 * 深度广度优先遍历 * */ public class GraphTraverse { private static boolean[] visited;// 访问标记数组 // 广度遍历 public static void BFSTraverse(ALGraph G) throws Exception { visited = new boolean[G.getVexNum()];// 访问标志数组 for(boolean v :visited) v =false;// 初始化 for (int v = 0; v < G.getVexNum(); v++) if (!visited[v])// 尚未访问 BFS(G, v); } private static void BFS(ALGraph G, int v) throws Exception { visited[v] = true; System.out.print(G.getVex(v).toString() + " ");// 返回节点的值 Queue
Q = new LinkedList<>();// 辅助队列Q Q.offer(v);// v入队 while (!Q.isEmpty()) { int u = Q.poll();// u为下标 for (int w = G.firstAdjVex(u); w >= 0; w = G.nextAdjVex(u, w))// w为u的第一个邻接点 if (!visited[w]) {// w为u的为访问邻接点 visited[w] = true; System.out.print(G.getVex(w) + " "); Q.offer(w); } } } //深度优先 public static boolean[] visited_; public static void DFSTraverse(ALGraph G) throws Exception{ visited_ = new boolean[G.getVexNum()]; for(boolean v :visited_) v = false; for(int v = 0 ;v
=0;w = G.nextAdjVex(v, w)) if(!visited_[w]) DFS(G,w); } } package 实验三; import java.util.Scanner; /** * * @author 黄良运 time:2017.12.7 邻接矩阵存储结构 * @param
*/ public class MyGraph
> { public final static int INFINITY = Integer.MAX_VALUE; private GraphKind kind;// 种类 private int vexNum, arcNum;// 顶点数和边数 private AnyType[] vexs;// 顶点 private int[][] arcs;// 邻接矩阵 Scanner in = new Scanner(System.in); public MyGraph() { this(null, 0, 0, null, null); } public MyGraph(GraphKind kind, int vexNum, int arcNum, AnyType[] vexs, int[][] arcs) { super(); this.kind = kind; this.vexNum = vexNum; this.arcNum = arcNum; this.vexs = vexs; this.arcs = arcs; } // 创建图 public void createGraph() { System.out.println("请输入图的类型"); GraphKind kind = GraphKind.valueOf(in.nextLine()); switch (kind) { case UDG: createUDG(); return; case DG: createDG(); return; case UDN: createUDN(); return; case DN: createDN(); return; } } // 创建无向图 public void createUDG() { System.out.println("请分别输入图的顶点数，图的边数"); vexNum = in.nextInt(); arcNum = in.nextInt(); vexs = (AnyType[])new Object[vexNum]; System.out.println("请分别输入图的各个顶点"); for (int v = 0; v < vexNum; v++)// 构造顶点向量 vexs[v] = (AnyType)in.next(); arcs = new int[vexNum][vexNum]; for (int v = 0; v < vexNum; v++) for (int u = 0; u < vexNum; u++) arcs[v][u] = INFINITY; System.out.println("请输入各个边的两个顶点及其权值"); for (int k = 0; k < arcNum; k++) { int v = locateVex((AnyType)in.next());// 得到顶点的下标 int u = locateVex((AnyType)in.next()); arcs[v][u] = arcs[u][v] = in.nextInt(); } } // 创建有向图 public void createDG() { System.out.println("请分别输入图的顶点数，图的边数"); vexNum = in.nextInt(); arcNum = in.nextInt(); vexs = (AnyType[]) new String[vexNum]; System.out.println("请分别输入图的各个顶点"); for (int v = 0; v < vexNum; v++)// 构造顶点向量 vexs[v] = (AnyType)in.next(); arcs = new int[vexNum][vexNum]; for (int v = 0; v < vexNum; v++) for (int u = 0; u < vexNum; u++) arcs[v][u] = INFINITY; System.out.println("请输入各个边的两个顶点及其权值"); for (int k = 0; k < arcNum; k++) { int v = locateVex((AnyType)in.next());// 得到顶点的下标 int u = locateVex((AnyType)in.next()); arcs[v][u] = in.nextInt(); } } // 创建无向网 public void createUDN() { } // 创建有向网 public void createDN() { } // 返回顶点数 public int getVexNum() { return vexNum; } // 返回边数 public int getarcNum() { return arcNum; } public void isValid_V(int v) throws Exception { if (v < 0 || v >= vexNum) throw new Exception("第" + v + "个顶点不存在"); } // 给定顶点值vex，返回在图中的位置，如果图中不包含此顶点，返回-1 public int locateVex(AnyType vex) { for (int v = 0; v < vexNum; v++){ //System.out.println("vex"+vexs[v]); if (vexs[v].equals(vex)) return v; } return -1; } // 返回v的节点的值0<=v
s = new MyGraph
(); Scanner in = new Scanner(System.in); s.createGraph(); System.out.println("输出结束"); System.out.println(s.firstAdjVex(1)); System.out.println(s.nextAdjVex(1, 2)); //GraphTraverse.BFSTraverse(s); System.out.println(); //GraphTraverse.DFSTraverse(s); System.out.println("请输入要查找的结点是"); while (in.hasNext()) {//int k = in.nextInt(); String k = in.next(); //System.out.println(s.getDegree(k)+"个"); } } }