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均表示圖中每個節點到其他節點的連接狀況，能連通用一種狀態表示，不能連通用另外一中方式表示，這樣就形成了一個笛卡爾積。也就是一個二維數組。