当前位置:首页 > 开发 > 编程语言 > Java > 正文

java 图论二 有向图 拓扑排序

发表于: 2012-11-21   作者:blackproof   来源:转载   浏览次数:
摘要: 有向图的拓扑排序,能够获得访问到某一节点的提前条件。 拓扑排序时不可以实现环和图的拓扑排序。   写一下拓扑排序的实现: 是在联通矩阵上实现的,拓扑排序的算法是: 1.查看连通矩阵是否还有剩余节点,如果有继续2,3操作,如果没有结束拓扑排序 2.找到没有后继的节点 3.如果找到了,从联通矩阵中删除;如果没找到,则此联通矩阵不是DAG,不能进行拓扑排序 package

有向图的拓扑排序,能够获得访问到某一节点的提前条件。

拓扑排序时不可以实现环和图的拓扑排序。

 

写一下拓扑排序的实现:

是在联通矩阵上实现的,拓扑排序的算法是:

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];
		}
	}
	
	
	
}
 

java 图论二 有向图 拓扑排序

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
拓扑排序是对有向无圈图的顶点的一种排序。如果存在一条vi到vj的路径,则vi排在vj前面。如果图含有
当每个任务有前后置关系时,需要找到一种满足前后置关系的路线,将任务完成。 如果将每个任务看成一
// 有向无回路图拓扑排序.cpp : Defines the entry point for the console application. // #includ
拓扑排序虽是一种排序,但是它跟平时所接触的sort或者qsort不同,排序的意义不同。拓扑排序针对有向
拓扑排序虽是一种排序,但是它跟平时所接触的sort或者qsort不同,排序的意义不同。拓扑排序针对有向
相关: 基于java的图的实现 基于java的图的实现(二) 图的两种遍历 方法一: (1)在又向图中选一个没有
今天心情不错,公司终于签下了一个综合业务监控系统的大单。到底有多大我也不知道,反正连软件带硬
本章是通过C++实现邻接表有向图。 目录 1. 邻接表有向图的介绍 2. 邻接表有向图的代码说明 3. 邻接
  本文介绍使用深度先搜索对向无环图(DAG)进行拓扑排序。   对于一个有向无环图G=(V,E)来说
前面分别介绍了邻接矩阵有向图的C和C++实现,本文通过Java实现邻接矩阵有向图。 目录 1. 邻接矩阵有
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号