java邻接矩阵

① java中如何遍历最短路径长度邻接矩阵

packagetest;
importjava.util.ArrayList;
importjava.util.List;
/**
*java-用邻接矩阵求图的最短路径、最长途径。弗洛伊德算法
*/
publicclassFloydInGraph{
privatestaticintINF=Integer.MAX_VALUE;
privateint[][]dist;
privateint[][]path;
privateList<Integer>result=newArrayList<Integer>();
publicFloydInGraph(intsize){
this.path=newint[size][size];
this.dist=newint[size][size];
}
publicvoidfindPath(inti,intj){
intk=path[i][j];
if(k==-1)return;
findPath(i,k);
result.add(k);
findPath(k,j);
}
publicvoidfindCheapestPath(intbegin,intend,int[][]matrix){
floyd(matrix);
result.add(begin);
findPath(begin,end);
result.add(end);
}
publicvoidfloyd(int[][]matrix){
intsize=matrix.length;
for(inti=0;i<size;i++){
for(intj=0;j<size;j++){
path[i][j]=-1;
dist[i][j]=matrix[i][j];
}
}
for(intk=0;k<size;k++){
for(inti=0;i<size;i++){
for(intj=0;j<size;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;
}
}
}
}

}
publicstaticvoidmain(String[]args){
FloydInGraphgraph=newFloydInGraph(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},
};
intbegin=0;
intend=4;
graph.findCheapestPath(begin,end,matrix);
List<Integer>list=graph.result;
System.out.println(begin+"to"+end+",thecheapestpathis:");
System.out.println(list.toString());
System.out.println(graph.dist[begin][end]);
}
}

② java中的单向链表，栈，串，有哪些对象使用的这些数据结构，还有树，图，广义表这些在JAVA有哪些对象

JAVA把数据结构简化了，提供了不少集合类（collection），用的最多的就是LIST和MAP这个两个接口。LIST和MAP各自对应了多个实现它们的类，比如ArrayList，HashMap等等。其中List就很像C里的链表，它有顺序存放和无序存放的对象。好像没有几个类能严格符合你说的几种数据结构，你可以自己写类来实现相同的功能。没有这么多复杂的数据结构，JAVA才体现出简单易学的特点啊。

③ 如何实时更新邻接表边的权值java

本系列文章主要学习如何使用JAVA语言以邻接表的方式实现了数据结构---图（Graph），这是第一篇文章，学习如何用JAVA来表示图的顶点。从数据的表示方法来说，有二种表示图的方式：一种是邻接矩阵，其实是一个二维数组；一种是邻接表，其实是一个顶点表，每个顶点又拥有一个边列表。下图是图的邻接表表示。

从图中可以看出，图的实现需要能够表示顶点表，能够表示边表。邻接表指是的哪部分呢？每个顶点都有一个邻接表，一个指定顶点的邻接表中，起始顶点表示边的起点，其他顶点表示边的终点。这样，就可以用邻接表来实现边的表示了。如顶点V0的邻接表如下：

与V0关联的边有三条，因为V0的邻接表中有三个顶点(不考虑V0)。

④ 数据结构：画出下图的邻接矩阵存储结构

我定义一个int型二维数组 G[5][5].
点a，b,c,d分别定义编号为1,2,3,4

G[u][v]的值为零 则有向边(u,v)不联通
若值为1则有向边(u,v)联通
又因为在c,c ,java中 数组的范围是从0开始的
为了使用方便 我们不使用下标为0的数组元素
因为有四个点 所以我们定义一个5x5的二维数组
矩阵数据如下
00000
00110
00000
00001
01000
其中 G[1][2] G[1][3]G[3][4]G[4][1]的值为一

⑤ Java生成树中的从根到叶子节点的所有路径

方法是在dfs的过程中维护dfs的路径，到达叶子结点时将路径加入到答案中，具体见代码的注释。

输入格式为：

7A
AB
CA
DB
EB
CF
CG

其中，第一行表示结点数量n和根结点编号，第[2..n + 1]行每行两个字符u和v，表示树边。

importjava.io.File;
importjava.io.FileNotFoundException;
importjava.util.ArrayList;
importjava.util.List;
importjava.util.Scanner;

publicclassMain{
staticfinalintmaxn=1000;

intn;//树的结点个数
charroot;//树的根
List<List<Character>>ans=newArrayList<List<Character>>();//结果，存放所有路径
boolean[][]G=newboolean[maxn][maxn];//邻接矩阵

/**
*dfs
*@paramu当前到达的结点
*@paramfa当前结点的父节点
*@parampath根到fa的路径
*/
voiddfs(charu,charfa,List<Character>path){
path.add(u);
booleanleaf=true;//u为叶子结点
for(charv='A';v<='Z';++v){
if(G[u][v]&&v!=fa){//邻接矩阵中有别的边
leaf=false;//u不是叶子结点
dfs(v,u,path);
}
}
if(leaf){//u为叶子结点，将路径加入到答案
List<Character>pt=newArrayList<Character>();
for(Characterc:path)pt.add(c);
ans.add(pt);
}

path.remove(path.size()-1);
}

publicvoidgo()throwsFileNotFoundException
{
Scannerin=newScanner(newFile("data.in"));

Strings;//进行输入的处理时的临时变量
n=in.nextInt();//获取结点个数
s=in.next();root=s.charAt(0);//获取根
for(inti=0;i<n-1;++i){
charu,v;
s=in.next();u=s.charAt(0);//获取边，并在邻接矩阵中做标记
s=in.next();v=s.charAt(0);
G[u][v]=G[v][u]=true;
}
List<Character>path=newArrayList<Character>();
dfs(root,'0',path);
for(inti=0;i<ans.size();++i){//输出答案
for(Characterc:ans.get(i))
System.out.print(c);
System.out.println();
}

in.close();
}

publicstaticvoidmain(String[]args)throwsFileNotFoundException{
newMain().go();
}
}

⑥ java怎么实现一个完全图的邻接矩阵的特征值计算

如果有对称元素 aij 和 aji 分别是1和0,那么一定是有向图(有一条有向边连接两点) 但如果所有的对应元素都相同,就无法判断是有向图还是无向图

⑦ java 根据邻接矩阵求两点间长度小于3的路径

public class GetSum { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[][] nums = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int sum = 0; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (i == j || (i + j) == 2) { sum += nums[i][j]; } } } System.out.println(sum); } }

⑧ Java，Python中没有指针，怎么实现链表，图等数据结构

用编程实现图的存储一般有常见的有两种方式，第一种是邻接链表、第二种就是邻接矩阵。

⑨ 如何用java构建网络节点的入度和出度的结构

入度就是有多少条边指向这个点，出度就是从这个点出发有多少条边，这个不难吧 点 入度 出度 1 2 1 2 2 2 3 1 3 4 3 0 5 2 3 6 1 2 邻接矩阵就是一个二维数组，行列都是顶点，行表示开始，列表示结束，这是一个无权图，如果行到列有指向的边

⑩ 怎么用java实现图中的数据结构

用编程实现图的存储一般有常见的有两种方式，第一种是邻接链表、第二种就是邻接矩阵。

邻接链表就是将图中的每一个点都单独作为一个单独链表的起点，为每个顶点保存一个链表。链表的每一个节点都记录了与之相邻的节点的信息。
邻接矩阵就是将图转换成一个二维数组，数组的x和y均表示图中每个节点到其他节点的连接状况，能连通用一种状态表示，不能连通用另外一中方式表示，这样就形成了一个笛卡尔积。也就是一个二维数组。