「邻接矩阵java」邻接矩阵怎么求
本篇文章给大家谈谈邻接矩阵java，以及邻接矩阵怎么求对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
java中如何遍历最短路径长度邻接矩阵
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]
关于邻接矩阵java和邻接矩阵怎么求的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
);}
}
求代码，java实验，题目如图
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;
}
StackInteger s = new StackInteger();
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);
}
}
java怎么实现一个完全图的邻接矩阵的特征值计算
如果有对称元素 aij 和 aji 分别是1和0,那么一定是有向图(有一条有向边连接两点) 但如果所有的对应元素都相同,就无法判断是有向图还是无向图
关于邻接矩阵java和邻接矩阵怎么求的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。