Javaは隣接テーブルに基づく図のいくつかの応用を実現する
Javaは隣接テーブルに基づく図のいくつかの応用を実現する
図作成クラス:
適用クラス:
テストクラス:
図作成クラス:
package graph1;
import java.util.LinkedList;
import graph.Graph.edgeNode;
public class Graph {
class EdgeNode{
int adjvex;
EdgeNode nextEdge;
}
class VexNode{
int data;
EdgeNode firstEdge;
boolean isVisted;
public boolean isVisted() {
return isVisted;
}
public void setVisted(boolean isVisted) {
this.isVisted = isVisted;
}
}
VexNode[] vexsarray ;
int[] visited = new int[100];
boolean[] isVisited = new boolean[100];
public void linkLast(EdgeNode target,EdgeNode node) {
while (target.nextEdge!=null) {
target=target.nextEdge;
}
target.nextEdge=node;
}
public int getPosition(int data) {
for(int i=0;iif (data==vexsarray[i].data) {
return i;
}
}
return -1;
}
public void buildGraph(int[] vexs,int[][] edges ) {
int vLen = vexs.length;
int eLen = edges.length;
vexsarray = new VexNode[vLen];
for(int i=0;inew VexNode();
vexsarray[i].data = vexs[i];
vexsarray[i].firstEdge = null;
}
for(int i=0;iint a = edges[i][0];
int b = edges[i][1];
int start = getPosition(a);
int end = getPosition(b);
EdgeNode edgeNode = new EdgeNode();
edgeNode.adjvex = end;
if (vexsarray[start].firstEdge == null) {
vexsarray[start].firstEdge = edgeNode;
} else {
linkLast(vexsarray[start].firstEdge,edgeNode);
}
}
}
public void printGraph() {
for(int i=0;i"%d--",vexsarray[i].data);
EdgeNode node = vexsarray[i].firstEdge;
while (node!=null) {
System.out.printf("%d(%d)--",node.adjvex,vexsarray[node.adjvex].data);
node = node.nextEdge;
}
System.out.println("
");
}
}
/*
*
*/
public void DFS(int vex) {
int w;
EdgeNode node;
visited[vex] = 1;
// System.out.println(vex);
node=vexsarray[getPosition(vex)].firstEdge;
while (node!=null) {
w=node.adjvex;
if (visited[vexsarray[w].data]==0) {
DFS(vexsarray[w].data);
}
node=node.nextEdge;
}
}
/*
*
*/
public void BFS(int vex) {
VexNode start = vexsarray[getPosition(vex)];
LinkedList queue = new LinkedList<>();
start.setVisted(true);
queue.add(start);
System.out.println(start.data);
VexNode currVex;
while (!queue.isEmpty()) {
currVex=queue.remove(0);
EdgeNode node = currVex.firstEdge;
while (node!=null) {
if (vexsarray[node.adjvex].isVisted==false) {
System.out.println(vexsarray[node.adjvex].data);
vexsarray[node.adjvex].setVisted(true);
queue.add(vexsarray[node.adjvex]);
}
node=node.nextEdge;
}
}
}
}
適用クラス:
package graph1;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;
import graph.DFS;
import graph.Graph.vexNode;
import graph1.Graph.EdgeNode;
import graph1.Graph.VexNode;
public class Graph_App {
int[] index = new int[20];
LinkedList path = new LinkedList<>();
LinkedList path2 = new LinkedList<>();
boolean[] vis = new boolean[15];
// int d = -1;
/*
*
*/
public boolean connect(Graph graph) {
boolean flag=true;
graph.DFS(0);
for(int i=0;iif (!graph.vexsarray[i].isVisted) {
flag=flag;
break;
}
}
return flag;
}
/*
* v1 v2
*/
public boolean HasaPath(Graph graph,VexNode vexNode1,VexNode vexNode2) {
EdgeNode node = vexNode1.firstEdge;
int i=0;
boolean flag=false;
while (node!=null) {
index[i] = graph.vexsarray[node.adjvex].data;
i++;
node=node.nextEdge;
}
for(int j=0;jif (index[j]==vexNode2.data) {
flag=true;
}
}
return flag;
}
/*
* v1 v2
*/
public void FindPath(Graph graph,VexNode vexNode1,VexNode vexNode2) {
EdgeNode node = vexNode1.firstEdge;
int w;
VexNode vexNode ;
vexNode1.setVisted(true);
path.add(vexNode1);
while (node!=null) {
w=node.adjvex;
if (!graph.vexsarray[w].isVisted) {
FindPath(graph, graph.vexsarray[w], vexNode2);
}
node=node.nextEdge;
}
}
}
テストクラス:
package graph1;
import java.util.Iterator;
import graph1.Graph.VexNode;
public class Tset2 {
public static void main(String[] args) {
int[] vexs = {0,1,2,3,4};
int[][] edges = {
{0,1},
{0,3},
{1,0},
{1,2},
{2,1},
{2,3},
{2,4},
{3,0},
{3,2},
{3,4},
{4,2},
{4,3},
};
Graph graph = new Graph();
graph.buildGraph(vexs, edges);
graph.printGraph();
Graph_App app = new Graph_App();
System.out.println(app.connect(graph));
System.out.println(app.HasaPath(graph, graph.vexsarray[0],graph.vexsarray[3]));
app.FindPath(graph, graph.vexsarray[0],graph.vexsarray[4]);
Iterator iterator = app.path.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next().data);
}
}
}