在linux下实现拓扑排序,数据结构——有向图（拓扑排序算法）
package zieckey.datastructure.study.graph;
/**
* 有方向圖
*
* @author zieckey
*/
public class DirectedGraph
{
private final int????MAX_VERTS????= 20;
private Vertex[]????vertexList;????????// array of vertices
private int[][]????????adjMat;????????????// adjacency matrix
private int????????????nVerts;????????????// current number of vertices
private char[]????????sortedArray;????????// sorted vert labels
/**
* 默認構造函數 初始化鄰接矩陣
*/
public DirectedGraph( )
{
vertexList = new Vertex[MAX_VERTS];
sortedArray = new char[MAX_VERTS];
// 圖的鄰接矩陣adjacency matrix
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for ( int j = 0; j < MAX_VERTS; j++ )
{
// set adjacency
for ( int k = 0; k < MAX_VERTS; k++ )
{
adjMat[j][k] = 0;
}
}
}
/**
* 對有向圖進行拓撲排序
*
* 無后繼的頂點優先拓撲排序方法
* 1、思想方法
* 該方法的每一步均是輸出當前無后繼(即出度為0)的頂點。
* 對于一個DAG，按此方法輸出的序列是逆拓撲次序。
* 因此設置一個棧(或向量)T來保存輸出的頂點序列，即可得到拓撲序列。
* 若T是棧，則每當輸出頂點時，只需做人棧操作，排序完成時將棧中頂點依次出棧即可得拓撲序列。
* 若T是向量，則將輸出的頂點從T[n-1]開始依次從后往前存放，即可保證T中存儲的頂點是拓撲序列。
*/
public void nonSuccFirstToplogicalSort()
{
int orig_nVerts = nVerts;
while(nVerts>0)
{
int delVertex = getNoSuccessorVertex();
if ( -1 == delVertex )
{
System.out.println("Error: This graph has cycles! It cannot be toplogical sorted.");
return;
}
sortedArray[nVerts-1] = vertexList[delVertex].label;
deleteVertex( delVertex );
}
System.out.print("Topologically sorted order: ");
for(int j=0; j
{
System.out.print( sortedArray[j] );
}
System.out.println("");
}
/**
* 找到沒有后繼節點的節點
* @return
*/
public int getNoSuccessorVertex()
{
boolean isEdge;
for ( int row = 0; row < nVerts; row++ )
{
isEdge = false;
for ( int column = 0; column < nVerts; column++ )
{
if ( adjMat[row][column]>0 )//大于0，表明有邊指向其他點，說明有后繼節點
{
isEdge = true;
break;????????????????????//OK，繼續下一個節點
}
}
if ( false == isEdge )//沒有邊，表明沒有后繼節點
{
return row;
}
}
return -1;
}
/**
* 刪除一個節點
* @param delVertex
*/
public void deleteVertex( int delVertex )
{
if ( delVertex != nVerts-1 )//如果不是最后一個節點
{
//在節點列表中刪除這個節點，所有后面的節點前移一格
for ( int i = delVertex; i < nVerts-1; i++ )
{
vertexList[i] = vertexList[i+1];
}
// 刪除鄰接矩陣的delVertex行和列，即所有后面的行和列都向前移動一格
// 所有delVertex行后的行，向上一個格
for ( int row = delVertex; row < nVerts - 1; row++ )
{
for ( int column = 0; column < nVerts; column++ )
{
adjMat[row][column] = adjMat[row + 1][column];
}
}
// 所有delVertex列后的列，向左一個格
for ( int column = delVertex; column < nVerts; column++ )
{
for ( int row = 0; row < nVerts - 1; row++ )
{
adjMat[row][column] = adjMat[row][column+1];
}
}
}
nVerts--;//減少一個節點
}
/**
* 添加一個節點
*
* @param lab
*/
public void addVertex( char lab ) // argument is label
{
vertexList[nVerts++ ] = new Vertex( lab );
}
/**
* 添加一條邊
*
* @param start
* 起始點
* @param end
* 終點
*/
public void addEdge( int start, int end )
{
adjMat[start][end] = 1;
}
/**
* 添加一條邊
*
* @param start
* 起始點
* @param end
* 終點
*/
public void addEdge( char startVertex, char endVertex )
{
int start = getIndexByLabel( startVertex );
int end = getIndexByLabel( endVertex );
if ( -1 != start && -1 != end )
{
adjMat[start][end] = 1;
}
}
/**
* 顯示一個節點
*
* @param v
*/
public void displayVertex( int v )
{
System.out.print( vertexList[v].label );
}
public int getIndexByLabel( char lable )
{
for ( int i = 0; i < vertexList.length; i++ )
{
if ( lable == vertexList[i].label )
{
return i;
}
}
// 沒有這個節點
return -1;
}
}
《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀總結
以上是生活随笔為你收集整理的在linux下实现拓扑排序,数据结构——有向图（拓扑排序算法）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： linux光盘安装yum,[转载]将li
- 下一篇： linux 插件 概念,服务端概念功能介