由上篇 图--图论基础（1） - 可知， 邻接表适合表示稀疏图，邻接矩阵适合表示稠密图 。
创新互联公司长期为超过千家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为涵江企业提供专业的网站设计制作、成都网站制作，涵江网站改版等技术服务。拥有十多年丰富建站经验和众多成功案例,为您定制开发。
接下来我们用Java来表示邻接矩阵及邻接表
一. 用邻接矩阵表示稠密图
DenseGraph.java
二.用邻接表表示稀疏图
SparseGraph.java
如果有对称元素 aij 和 aji 分别是1和0,那么一定是有向图(有一条有向边连接两点) 但如果所有的对应元素都相同,就无法判断是有向图还是无向图
package test;
import java.util.ArrayList;
import java.util.List;
/**
* java-用邻接矩阵求图的最短路径、最长途径。弗洛伊德算法
*/
public class FloydInGraph {
private static int INF=Integer.MAX_VALUE;
private int[][] dist;
private int[][] path;
private ListInteger result=new ArrayListInteger();
public FloydInGraph(int size){
this.path=new int[size][size];
this.dist=new int[size][size];
}
public void findPath(int i,int j){
int k=path[i][j];
if(k==-1)return;
findPath(i,k);
result.add(k);
findPath(k,j);
}
public void findCheapestPath(int begin,int end,int[][] matrix){
floyd(matrix);
result.add(begin);
findPath(begin,end);
result.add(end);
}
public void floyd(int[][] matrix){
int size=matrix.length;
for(int i=0;isize;i++){
for(int j=0;jsize;j++){
path[i][j]=-1;
dist[i][j]=matrix[i][j];
}
}
for(int k=0;ksize;k++){
for(int i=0;isize;i++){
for(int j=0;jsize;j++){
if(dist[i][k]!=INF
dist[k][j]!=INF
dist[i][k]+dist[k][j]dist[i][j]){//dist[i][k]+dist[k][j]dist[i][j]--longestPath
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=k;
}
}
}
}
}
public static void main(String[] args) {
FloydInGraph graph=new FloydInGraph(5);
int[][] matrix={
{INF,30,INF,10,50},
{INF,INF,60,INF,INF},
{INF,INF,INF,INF,INF},
{INF,INF,INF,INF,30},
{50,INF,40,INF,INF},
};
int begin=0;
int end=4;
graph.findCheapestPath(begin,end,matrix);
ListInteger list=graph.result;
System.out.println(begin+" to "+end+",the cheapest path is:");
System.out.println(list.toString());
System.out.println(graph.dist[begin]);
}
}
