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 List<Integer> result=new ArrayList<Integer>()
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=0i<sizei++){
for(int j=0j<sizej++){
path[i][j]=-1
dist[i][j]=matrix[i][j]
}
}
for(int k=0k<sizek++){
for(int i=0i<sizei++){
for(int j=0j<sizej++){
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)
List<Integer> list=graph.result
System.out.println(begin+" to "+end+",the cheapest path is:")
System.out.println(list.toString())
System.out.println(graph.dist[begin][end])
}
}
用编程实现图的存储一般有常见的有两种方式，第一种是邻接链表、第二种就是邻接矩阵。邻接链表就是将图中的每一个点都单独作为一个单独链表的起点，为每个顶点保存一个链表。链表的每一个节点都记录了与之相邻的节点的信息。
邻接矩阵就是将图转换成一个二维数组，数组的x和y均表示图中每个节点到其他节点的连接状况，能连通用一种状态表示，不能连通用另外一中方式表示，这样就形成了一个笛卡尔积。也就是一个二维数组。
import java.util.Scanner
import java.util.Stack
public class DFS
{
// 存储节点信息
private char[] vertices
// 存储边信息（邻接矩阵）
private int[][] arcs
// 图的节点数
private int vexnum
// 记录节点是否已被遍历
private boolean[] visited
// 初始化
public DFS(int n)
{
vexnum = n
vertices = new char[n]
arcs = new int[n][n]
visited = new boolean[n]
for(int i = 0 i < vexnum i++)
{
for(int j = 0 j < vexnum j++)
{
arcs[i][j] = 0
}
}
}
// 添加边(无向图)
public void addEdge(int i, int j)
{
// 边的头尾不能为同一节点
if(i == j)
return
arcs[i - 1][j - 1] = 1
arcs[j - 1][i - 1] = 1
}
// 设置节点集
public void setVertices(char[] vertices)
{
this.vertices = vertices
}
// 设置节点访问标记
public void setVisited(boolean[] visited)
{
this.visited = visited
}
// 打印遍历节点
public void visit(int i)
{
System.out.print(vertices[i] + " ")
}
// 从第i个节点开始深度优先遍历
private void traverse(int i)
{
// 标记第i个节点已遍历
visited[i] = true
// 打印当前遍历的节点
visit(i)
// 遍历邻接矩阵中第i个节点的直接联通关系
for(int j = 0 j < vexnum j++)
{
// 目标节点与当前节点直接联通，并且该节点还没有被访问，递归
if(arcs[i][j] == 1 && visited[j] == false)
{
traverse(j)
}
}
}
// 图的深度优先遍历（递归）
public void DFSTraverse(int start)
{
// 初始化节点遍历标记
for(int i = 0 i < vexnum i++)
{
visited[i] = false
}
// 从没有被遍历的节点开始深度遍历
for(int i = start - 1 i < vexnum i++)
{
if(visited[i] == false)
{
// 若是连通图，只会执行一次
traverse(i)
}
}
}
// 图的深度优先遍历（非递归）
public void DFSTraverse2(int start)
{
// 初始化节点遍历标记
for(int i = 0 i < vexnum i++)
{
visited[i] = false
}
Stack<Integer> s = new Stack<Integer>()
for(int i = start - 1 i < vexnum i++)
{
if(!visited[i])
{
// 连通子图起始节点
s.add(i)
do
{
// 出栈
int curr = s.pop()
// 如果该节点还没有被遍历，则遍历该节点并将子节点入栈
if(visited[curr] == false)
{
// 遍历并打印
visit(curr)
visited[curr] = true
// 没遍历的子节点入栈
for(int j = vexnum - 1 j >= 0 j--)
{
if(arcs[curr][j] == 1 && visited[j] == false)
{
s.add(j)
}
}
}
} while(!s.isEmpty())
}
}
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in)
int N, M, S
while(true)
{
System.out.println("输入N M S，分别表示图G的结点数，边数，搜索的起点：")
String line = sc.nextLine()
if(!line.matches("^\\s*([1-9]\\d?|100)(\\s+([1-9]\\d?|100)){2}\\s*$"))
{
System.out.print("输入错误，")
continue
}
String[] arr = line.trim().split("\\s+")
N = Integer.parseInt(arr[0])
M = Integer.parseInt(arr[1])
S = Integer.parseInt(arr[2])
break
}
DFS g = new DFS(N)
char[] vertices = new char[N]
for(int i = 0 i < N i++)
{
vertices[i] = (i + 1 + "").charAt(0)
}
g.setVertices(vertices)
for(int m = 0 m < M m++)
{
System.out.println("输入图G的第" + (m + 1) + "条边，格式为“i j”，其中i，j为结点编号（范围是1~N）")
String line = sc.nextLine()
if(!line.matches("^\\s*([1-9]\\d?|100)\\s+([1-9]\\d?|100)\\s*$"))
{
System.out.print("输入错误，")
m--
continue
}
String[] arr = line.trim().split("\\s+")
int i = Integer.parseInt(arr[0])
int j = Integer.parseInt(arr[1])
g.addEdge(i, j)
}
sc.close()
System.out.print("深度优先遍历（递归）：")
g.DFSTraverse(S)
System.out.println()
System.out.print("深度优先遍历（非递归）：")
g.DFSTraverse2(S)
}
}
