package Graph;
import java.util.ArrayList;
import java.util.LinkedList;
import DataStruct.Union;
import Sort.Sort;
/**
图类
构造函数封装了将邻接矩阵转化临接表的方法，提供了拓扑排序，无权最短路径算法等
所有算法都是基于临接表（拓扑排序 基于入度数组，入度数组也是基于临接表求得）
*/
public class Graph {
public static final int INFINITY=-
1;
/**
图的顶点
*/
class Vertex{
int topnum;
Edge edge=
null;
int dis=INFINITY;
boolean arrived=
false;
Vertex path=
null;
public Vertex(
int topnum) {
this.topnum = topnum;
}
public Vertex(
int topnum,Edge edge) {
this.topnum = topnum;
this.edge=edge;
}
}
/**
图的边(用于临接表)
*/
class Edge{
int adjacentTop;
int weight =
1;
Edge next;
public Edge(
int adjacentTop,
int weight) {
this.adjacentTop = adjacentTop;
this.next =
null;
this.weight=weight;
}
}
class Side implements Comparable<Side>{
int from;
int to;
int weight;
public Side(
int from,
int to,
int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
public int compareTo(Side arg0) {
return weight>((Side)arg0).weight?
1:weight==((Side)arg0).weight?
0:-
1;
}
}
private int numVertexs;
private int numEdges=
0;
private Vertex[] NodeTable=
null;
private int[] InDegreeList;
/**
* 边的集合 初始化Graph对象时 自动初始化
*/
private ArrayList<Side> sides=
new ArrayList<Graph.Side>();
public Graph(
int[][] AdjacencyMatrix) {
this.numVertexs = AdjacencyMatrix.length;
NodeTableInit(numVertexs);
InDegreeList=
new int[numVertexs];
MatrixToList(AdjacencyMatrix);
}
/**
* @param length
* 邻接表初始化 边暂时都为空
*/
private void NodeTableInit(
int length){
NodeTable=
new Vertex[length];
for (
int i =
0; i < length; i++) {
NodeTable[i]=
new Vertex(i);
}
}
/**
* @param matrix 邻接矩阵
* 将邻接矩阵转换为邻接表
*/
private void MatrixToList(
int[][] matrix){
for (
int i =
0; i < matrix.length; i++) {
for (
int j =
0; j < matrix.length; j++) {
if (matrix[i][j]!=
0)
{
addEdge(i, j,matrix[i][j]);
}
}
}
}
/**
* 构建边的集合 添加一条边到 sides中
* @param from 弧头顶点下标
* @param to 弧尾顶点下标
* @param weight
*/
private void addSide(
int from,
int to,
int weight){
if (sides!=
null) {
sides.add(
new Side(from, to, weight));
}
}
/**
* @param from 弧头顶点下标
* @param to 弧尾顶点下标
* 填充好 邻接表 因为初始化邻接表 edge都为空
*/
private void addEdge(
int from,
int to,
int weight) {
addSide(from, to, weight);
numEdges++;
Edge edge=NodeTable[from].edge;
if (edge==
null)
{
NodeTable[from].edge=
new Edge(to,weight);
}
else
{
while (edge.next!=
null)
{
edge=edge.next;
}
edge.next=
new Edge(to,weight);
}
}
public int getNumVertexs() {
return numVertexs;
}
public int getNumEdges()
{
return numEdges;
}
public Vertex[]
getNodeTable()
{
return NodeTable;
}
public boolean isHasEdge(
int topNum)
{
return NodeTable[topNum].edge==
null?
false:
true;
}
/**
* @return 入度数组
*/
public int[]
getIndegreeList()
{
for (
int i =
0; i < numVertexs; i++)
{
Edge edge=NodeTable[i].edge;
while (edge!=
null)
{
InDegreeList[edge.adjacentTop]+=
1;
edge=edge.next;
}
}
return InDegreeList;
}
/**
*
* @param 顶点x
* @return 返回所有由邻接顶点x的顶点所组成的list
*/
public ArrayList<Vertex>
getAdjacentVertexs(Vertex x){
ArrayList<Vertex> list=
new ArrayList<Graph.Vertex>();
Edge edge=x.edge;
if (edge!=
null)
{
do
{
list.add(NodeTable[edge.adjacentTop]);
}
while ((edge=edge.next)!=
null);
}
else
{
return null;
}
return list;
}
/**
* 拓扑排序
* 先找出任意一个没有入度的顶点，然后显示出该顶点，并将它及其边一起从图中删除。然后，对于图的其余部分采用同样方法处理。
* 这里我们构造了一个入度数组
* @throws Exception
*/
public void topSort()
throws Exception{
getIndegreeList();
LinkedList<Vertex> queue=
new LinkedList<Vertex>();
int counter=
0;
for (
int i =
0; i < InDegreeList.length; i++)
{
if (InDegreeList[i]==
0)
{
queue.add(NodeTable[i]);
}
}
System.out.print(
"\n");
while (!queue.isEmpty())
{
Vertex vertex=queue.poll();
counter++;
System.out.print(vertex.topnum+
" ");
Edge edge=vertex.edge;
if (edge!=
null)
{
do
{
if(--InDegreeList[edge.adjacentTop]==
0)
{
queue.add(NodeTable[edge.adjacentTop]);
}
}
while ((edge=edge.next)!=
null);
}
}
if (counter!=numVertexs) {
throw new Exception(
"CycleFoundException");
}
}
/**
* 打印输出最短路径
*/
private void printMinDisPath(){
Vertex vertex=NodeTable[numVertexs-
1];
System.out.println();
System.out.print(NodeTable[numVertexs-
1].topnum+
"");
while (vertex.path!=
null)
{
vertex=vertex.path;
System.out.print(
"<="+vertex.topnum);
}
}
/**
* 优化无权最短路径 利用队列
* @param topNum 初始顶点数组下标
*/
public void unweightedMinDisHandleByQueue(
int topNum){
LinkedList<Vertex> queue=
new LinkedList<Vertex>();
Vertex s=NodeTable[topNum];
s.dis=
0;
queue.add(s);
while (!queue.isEmpty())
{
Vertex v=queue.poll();
ArrayList<Vertex> vertexs=getAdjacentVertexs(v);
if (vertexs!=
null)
{
for (Vertex w : vertexs)
{
if (w.dis==INFINITY)
{
w.dis=v.dis+
1;
w.path=v;
queue.add(w);
}
}
}
}
printMinDisPath();
}
/**
* 无权最短路径
* @param topNum 初始顶点数组下标
*/
public void unweightedMinDis(
int topNum){
NodeTable[topNum].dis=
0;
for (
int currDist =
0; currDist < numVertexs; currDist++)
{
for (
int j =
0; j < numVertexs; j++)
{
Vertex v=NodeTable[j];
if (!v.arrived&&v.dis==currDist)
{
v.arrived=
true;
Edge edge=v.edge;
if (edge!=
null)
{
Vertex m;
do {
m=NodeTable[edge.adjacentTop];
if (m.dis==INFINITY)
{
m.dis=currDist+
1;
m.path=v;
}
}
while ((edge=edge.next)!=
null);
}
}
}
}
printMinDisPath();
}
/**
* @return 返回所有顶点中dis最小的顶点
*/
private Vertex
find_UnArrived_Vertex_Min_Distance(){
Vertex minVertex=
null;
for (
int i =
0; i < numVertexs; i++)
{
if (!NodeTable[i].arrived)
{
if (minVertex==
null)
{
minVertex=NodeTable[i];
}
else
{
if (NodeTable[i].dis<minVertex.dis)
{
minVertex=NodeTable[i];
}
}
break;
}
}
return minVertex;
}
/**
* 从临接表中获取相邻接点间的边的权重
* @param from
* @param to
* @return weight 权重
*/
private int getEdgeWeight(Vertex from,Vertex to) {
Vertex fromVertex=NodeTable[from.topnum];
Edge edge=fromVertex.edge;
while (edge.adjacentTop!=to.topnum) {
edge=edge.next;
}
return edge.weight;
}
/**
* 迪杰斯特拉算法 求最短路径
* @param topNum 初始顶点的下标（从零开始）
*/
public void dijkstra(
int topNum){
Vertex s=NodeTable[topNum];
s.dis=
0;
Vertex v;
while ((v=find_UnArrived_Vertex_Min_Distance())!=
null)
{
v.arrived=
true;
ArrayList<Vertex> vertexs=getAdjacentVertexs(v);
if (vertexs!=
null)
{
for (Vertex w : vertexs)
{
if (!w.arrived)
{
int cvw=getEdgeWeight(v,w);
if (v.dis+cvw<w.dis)
{
w.dis=v.dis+cvw;
w.path=v;
}
}
}
}
}
printMinDisPath();
}
/**
* @return 是否还有没有标记的顶点
*/
private boolean isHasVertexUnknown(){
for (
int i =
0; i < numVertexs; i++)
{
if (NodeTable[i].arrived==
false)
{
return true;
}
}
return false;
}
/**
* @param list 已经到达顶点的集合
* @return 距离由已经到达顶点集合组成的临时树的最小边
*/
private Side
get_MinSide_TO_CurTree_From_UnknownVertex(ArrayList<Vertex> list){
Side minSide=
null;
for (Vertex v : list)
{
for (Side side : sides)
{
if (v.topnum==side.from&&!NodeTable[side.to].arrived)
{
if (minSide==
null)
{
minSide=side;
}
else
{
if (minSide.compareTo(side)>
0)
{
minSide=side;
}
}
}
}
}
return minSide;
}
/**
* Prim 普利姆最小生成树算法
*/
public void prim(){
Vertex s=NodeTable[
0];
s.arrived=
true;
ArrayList<Side> sides=
new ArrayList<Graph.Side>();
ArrayList<Vertex> arrivedVertexs=
new ArrayList<Graph.Vertex>();
while (isHasVertexUnknown()) {
arrivedVertexs.add(s);
Side side=get_MinSide_TO_CurTree_From_UnknownVertex(arrivedVertexs);
sides.add(side);
s=NodeTable[side.to];
s.arrived=
true;
}
for (Side side : sides) {
System.out.println(
"from "+side.from+
" to "+side.to);
}
}
/**
* 克鲁斯卡尔算法 最小生成树
*/
public void kruskal(){
Side[] sideUnion=
new Side[numEdges];
ArrayList<Side> resultSides=
new ArrayList<Graph.Side>();
for (
int i =
0; i < sideUnion.length; i++)
{
sideUnion[i]=sides.get(i);
}
Sort.heapSort(sideUnion);
Union union=
new Union(numVertexs);
for (
int i =
0; i < sideUnion.length; i++)
{
int root1=union.find(sideUnion[i].from);
int root2=union.find(sideUnion[i].to);
if (root1!=root2)
{
resultSides.add(sideUnion[i]);
union.setUnion(root1, root2);
}
}
for (Side side : resultSides) {
System.out.println(
"from "+side.from+
" to "+side.to);
}
}
}
