JAva図論二有向図トポロジ並べ替え
図へのトポロジーソートがあり、あるノードへのアクセスの事前条件を得ることができる.
トポロジーソート時にループと図のトポロジーソートを実現することはできません.
トポロジーソートの実装を書きます.
結合マトリクス上で実装され、トポロジーソートのアルゴリズムは次のとおりです.
1.接続マトリクスに残りのノードがあるかどうかを確認し、2,3操作を続行した場合、トポロジーソートが終了していない場合
2.後続ノードがないノードを見つける
3.見つかったら、ユニオンマトリクスから削除します.見つからない場合は、この接続マトリクスはDAGではなく、トポロジーソートはできません.
トポロジーソート時にループと図のトポロジーソートを実現することはできません.
トポロジーソートの実装を書きます.
結合マトリクス上で実装され、トポロジーソートのアルゴリズムは次のとおりです.
1.接続マトリクスに残りのノードがあるかどうかを確認し、2,3操作を続行した場合、トポロジーソートが終了していない場合
2.後続ノードがないノードを見つける
3.見つかったら、ユニオンマトリクスから削除します.見つからない場合は、この接続マトリクスはDAGではなく、トポロジーソートはできません.
package com.Construction;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class GraphSimpleExample {
private final int MAX_VERTS = 20;
private GraphNodeBean nodeList[];
private int adjMat[][];
private int nVerts;
public GraphSimpleExample(){
nodeList = new GraphNodeBean[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for (int i = 0; i < MAX_VERTS; i++) {
for (int j = 0; j < MAX_VERTS; j++) {
adjMat[i][j] = 0;
}
}
}
public void addNode(char label){
nodeList[nVerts++] = new GraphNodeBean(label);
}
public void addEdge(int start,int end){
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
public void displayGraphNode(int v){
System.out.println(nodeList[v].label);
}
/**
*
* @param v
* @return
*/
public int getAdjUnvisitedVertex(int v){
for (int i = 0; i < nVerts; i++) {
if(adjMat[v][i]==1 && nodeList[i].isVisited == false)
return i;
}
return -1;
}
/**
* deft first
*/
public void dfs(){
@SuppressWarnings("rawtypes")
Stack<Integer> theStack = new Stack<Integer>();
nodeList[0].isVisited = true;
displayGraphNode(0);
theStack.push(0);
while(!theStack.isEmpty()){
int v = getAdjUnvisitedVertex(theStack.peek());
if(v == -1)
theStack.pop();
else{
nodeList[v].isVisited = true;
displayGraphNode(v);
theStack.push(v);
}
}
// for (int i = 0; i < nVerts; i++) {
// nodeList[i].isVisited = false;
// }
}
public void bds(){
Queue<Integer> theQueue = new LinkedList<Integer>();
nodeList[0].isVisited = true;
displayGraphNode(0);
theQueue.offer(0);
int v2;
while(!theQueue.isEmpty()){
int v1 = theQueue.poll();
while((v2 = getAdjUnvisitedVertex(v1)) != -1){
nodeList[v2].isVisited = true;
displayGraphNode(v2);
theQueue.add(v2);
}
}
// for (int i = 0; i < nVerts; i++) {
// nodeList[i].isVisited = false;
// }
}
/**
* topologically output all the node
* , , 。
* ,
* note: the graph only be DAG - including , can't has cycles
*/
public void topo(){
int orig_nVerts = nVerts;
GraphNodeBean[] sortedArray = new GraphNodeBean[nVerts];
while(nVerts > 0){
int currentVertex = noSuccessor();
if(currentVertex == -1){
System.out.println("Error : Graph has cycles");
return;
}
sortedArray[nVerts - 1] = nodeList[currentVertex];
deleteVertex(currentVertex);
}
System.out.println("TOPOlogically sorted order:");
for (int i = 0; i < orig_nVerts; i++) {
System.out.println(sortedArray[i].label);
}
}
/**
* within topology graph add a edge
* @param start
* @param end
*/
public void addTopoEdge(int start,int end){
adjMat[start][end] = 1;
}
/**
*
* @return
*/
public int noSuccessor(){
boolean isEdge;
for (int i = 0; i < nVerts; i++) {
isEdge = false;
for (int j = 0; j < nVerts; j++) {
if(adjMat[i][j] > 0){
isEdge = true;
break;
}
}
if(!isEdge)
return i;
}
return -1;
}
/**
* delete certain node on the graph
* @param delVert
*/
public void deleteVertex(int delVert){
if(delVert != nVerts - 1){
movingVertexData(delVert);
for (int i = delVert; i < nVerts; i++)
this.moveRowUp(i, nVerts);
for (int i = delVert; i < nVerts; i++)
this.moveColLeft(i, nVerts-1);
}
nVerts --;
}
/**
* delete data from graph
* @param index the number of data start with 0
*/
public void movingVertexData(int index){
for (int i = index; i < nVerts -1; i++) {
nodeList[i] = nodeList[i+1];
}
}
/**
* row move up
* @param row moving row number that start with 0
* @param length table column length
*/
public void moveRowUp(int row,int length){
for (int i = 0; i < length; i++) {
adjMat[row][i] = adjMat[row+1][i];
}
}
/**
* col move left
* @param col moving column number that start with 0
* @param length table row lenglth;
*/
public void moveColLeft(int col,int length){
for (int i = 0; i < length; i++) {
adjMat[i][col] = adjMat[i][col+1];
}
}
}