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]);

}

}

實現圖的鄰接矩陣和圖的鄰接表的完整代碼

給你一個鄰接表的完整程序：

#include iostream.h

struct node

{

int data;

node *next;

};

class list

{

public:

list(){head=NULL;};

void MakeEmpty();

int Length();

void Insert(int x,int i);//將x插入到第i個結點（不含頭結點）的之后

void Insertlist(int a,int b);//將節點b插入a之前

int Delete(int x);

int Remove(int i);

int Find(int x);

void Display();

private:

node *head;

};

void list::Display()

{

node *current=head;

while (current!=NULL)

{

coutcurrent-data" ";

current=current-next;

}

coutendl;

}

void list::MakeEmpty()

{

head=NULL;

}

int list::Length()

{int n=1;

node *q=head;

if(q==NULL)

n=1;

else

while(q!=NULL)

{

n++;

q=q-next;

}

return n;

}

int list::Find(int x)//在鏈表中查找數值為x的結點，成功返回1，否則返回0

{

node *p=head;

while(p!=NULLp-data!=x)

p=p-next;

if(p-data==x)

return 1;

else

return 0;

}

void list::Insert (int x,int i)//將x插入到第i個結點（不含頭結點）的之后；

{

node *p;//p中放第i個結點

node *q;//q中放i后的結點

node *h;//h中存要插入的結點

h=new node;

h-data =x;

p=head;

if(p-next !=NULL) //鏈表不是只有一個結點或者空鏈表時候

{

int n=1;

while(p-next !=NULL)

{

n++;

p=p-next ;

}// 得到鏈表的結點的個數

p=head;//使p重新等于鏈首

if(i==n)//i=n時，直接加在最后面就行了

{

while(p-next !=NULL)

p=p-next;

p-next=h;

h-next =NULL;

}

else if(ini1)//先找到第i個結點，用p存第i個結點，用q存i后的結點，用h存要插入的結點

{

for(int j=1;ji;j++)

p=p-next;//找到第i個結點，用p存第i個結點

q=p-next;//q存i后的結點

p-next=h;

h-next=q;

}

else

cout"超出鏈表結點個數的范圍"endl;

}

else

cout"這個鏈表是空鏈表或者結點位置在首位"endl;

}

void list::Insertlist(int a,int b)//將b插入到結點為a之前

{

node *p,*q,*s;//p所指向的結點為a,s所指為要插入的數b,q所指向的是a前的結點

s=new node;

s-data=b;

p=head;

if(head==NULL)//空鏈表的時候

{

head=s;

s-next=NULL;

}

else

if(p-data==a)//a在鏈首時候

{

s-next=p;

head=s;

}

else

{

while(p-data!=ap-next!=NULL)//使p指向結點a,q指向a之前的結點

{

q=p;

p=p-next;

}

if(p-data==a)//若有結點a時候

{

q-next=s;

s-next=p;

}

else//沒有a的時候

{

p-next=s;

s-next=NULL;

}

}

}

int list::Delete(int x)//刪除鏈表中值為x的結點，成功返回1，否則返回0；

{

node *p,*q;

p=head;

if(p==NULL)

return 0;

if(p-data==x)

{

head=p-next;

delete p;

return 1;

}

else

{

while(p-data!=xp-next!=NULL)

{ q=p;

p=p-next;

}

if(p-data==x)

{

q-next =p-next;

delete p;

return 1;

}

else

return 0;

}

}

int list::Remove(int i)

{

node *p,*q;

p=head;

if(p!=NULL)

{ int n=1;

while(p-next !=NULL)

{

n++;

p=p-next ;

}//得到鏈表結點的個數

p=head;

if(i==n)//i結點在結尾的時候

{

while(p-next!=NULL)

{

q=p;

p=p-next;

}

q-next=NULL;

delete p;

return 1;

}

else if(ini1)//i結點在中間的時候

{

for(int j=1;ji;j++)

{

q=p;//q中放i前的結點

p=p-next ;//p中放第i個結點

}

q-next=p-next;

delete p;

return 1;

}

else if(i==1)//i結點在首位的時候

{

q=p-next;

head=q;

delete p;

return 1;

}

else

return 0;

}

else

return 0;

}

void main()

{

list A;

int data[10]={1,2,3,4,5,6,7,8,9,10};

A.Insertlist(0,data[0]);

for(int i=1;i10;i++)

A.Insertlist(0,data[i]);

A.Display();

menu:cout"1.遍歷鏈表"'\t'"2.查找鏈表"'\t'"3.插入鏈表"endl;

cout"4.刪除鏈表"'\t'"5.鏈表長度"'\t'"6.置空鏈表"endl;

int m;

do

{

cout"請輸入你想要進行的操作（選擇對應操作前面的序號）："endl;

cinm;

}while(m1||m6);//當輸入的序號不在包括中，讓他重新輸入

switch(m)

{

case 1:

{

A.Display ();

goto menu;

};break;

case 2:

{

cout"請輸入你想要找到的結點："endl;

int c;

cinc;//輸入你想要找到的結點

if(A.Find (c)==1)

{

cout"可以找到"cendl;

A.Display ();//重新顯示出鏈表A

}

else

{

cout"鏈表中不存在"cendl;

A.Display ();//重新顯示出鏈表A

}

goto menu;

};break;

case 3:

{

cout"請選擇你要插入的方式(選擇前面的序號進行選擇）"endl;

cout"1.將特定的結點加入到特定的結點前"'\t'"2.將特定的結點加到特定的位置后"endl;

int b1;

do

{

cout"請輸入你想要插入的方式（選擇前面的序號進行選擇）："endl;

cinb1;

}while(b11||b12);//當輸入的序號不在包括中，讓他重新輸入

if(b1==1)

{

cout"請輸入你想要插入的數和想要插入的結點（為此結點之前插入）："endl;

int a1,a2;

cina1a2;

A.Insertlist (a1,a2);//將a1插入到結點為a2結點之前

cout"此時鏈表為："endl;

A.Display ();//重新顯示出鏈表A

}

else

{

cout"請輸入你想要插入的數和想要插入的位置（為此結點之后插入）："endl;

int a1,a2;

cina1a2;

A.Insert (a1,a2);//將a1插入到結點位置為a2的結點之后

cout"此時鏈表為："endl;

A.Display ();//重新顯示出鏈表A

}

goto menu;

};break;

case 4:

{

cout"請選擇你要刪除的方式(選擇前面的序號進行選擇）"endl;

cout"1.刪除特定的結點"'\t'"2.刪除特定位置的結點"endl;

int b1;

do

{

cout"請輸入你想要插入的方式（選擇前面的序號進行選擇）："endl;

cinb1;

}while(b11||b12);//當輸入的序號不在包括中，讓他重新輸入

if(b1==1)

{

cout"請輸入你想要刪除的結點："endl;

int a;

cina;//輸入你想要刪除的結點

if(A.Delete (a)==1)

{

cout"成功刪除"aendl;

cout"刪除后的鏈表為："endl;

A.Display ();

}

else

{

cout"此鏈表為："endl;

A.Display ();//重新顯示出鏈表A

cout"鏈表中不存在"aendl;

}

}

else

{

cout"請輸入你想要刪除的結點位置："endl;

int b;

cinb;//輸入你想要刪除的結點的位置

if(A.Remove(b)==1)

{

cout"成功刪除第"b"個結點"endl;

cout"刪除后的鏈表為："endl;

A.Display ();//重新顯示出鏈表A

}

else

{

cout"當前鏈表的結點個數為："A.Length ()endl;

cout"您輸入的結點位置越界"endl;

}

}

goto menu;

};break;

case 5:

{

cout"這個鏈表的結點數為:"A.Length ()endl;

goto menu;

};break;

case 6:

{

A.MakeEmpty ();

cout"這個鏈表已經被置空"endl;

goto menu;

};break;

}

}

評論(3)|1

sunnyfulin |六級采納率46%

擅長：C/C++JAVA相關Windows數據結構及算法百度其它產品

按默認排序|按時間排序

其他1條回答

2012-04-23 17:41121446881|六級

我寫了一個C語言的，只給你兩個結構體和一個初始化函數：

#include "stdio.h"

#include "malloc.h"

struct adjacentnext//鄰接表項結構體

{

int element;

int quanvalue;

struct adjacentnext *next;

};

struct adjacenthead//鄰接表頭結構體

{

char flag;

int curvalue;

int element;

struct adjacenthead *previous;

struct adjacentnext *son;

};

//初始化圖，用鄰接表實現

struct adjacenthead *mapinitialnize(int mapsize)

{

struct adjacenthead *ahlists=NULL;

struct adjacentnext *newnode=NULL;

int i;

int x,y,z;

ahlists=malloc(sizeof(struct adjacenthead)*mapsize);

if(ahlists==NULL)

return NULL;

for(i=0;imapsize;i++)

{

ahlists[i].curvalue=0;

ahlists[i].flag=0;

ahlists[i].previous=NULL;

ahlists[i].son=NULL;

ahlists[i].element=i+1;

}

scanf("%d%d%d",x,y,z);//輸入源結點，目的結點，以及源結點到目的結點的路權值

while(x!=0y!=0)//x,y至少有一個零就結束

{

newnode=malloc(sizeof(struct adjacentnext));

newnode-element=y;

newnode-quanvalue=z;

newnode-next=ahlists[x-1].son;

ahlists[x-1].son=newnode;

scanf("%d%d%d",x,y,z);

}

return ahlists;//返回鄰接表頭

}

求代碼，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實現圖中的數據結構

用編程實現圖的存儲一般有常見的有兩種方式，第一種是鄰接鏈表、第二種就是鄰接矩陣。

鄰接鏈表就是將圖中的每一個點都單獨作為一個單獨鏈表的起點，為每個頂點保存一個鏈表。鏈表的每一個節點都記錄了與之相鄰的節點的信息。

鄰接矩陣就是將圖轉換成一個二維數組，數組的x和y均表示圖中每個節點到其他節點的連接狀況，能連通用一種狀態表示，不能連通用另外一中方式表示，這樣就形成了一個笛卡爾積。也就是一個二維數組。

新聞標題：java鄰接矩陣圖代碼 鄰接矩陣的代碼
鏈接URL：http://vcdvsql.cn/article30/dopjhso.html

成都網站建設公司_創新互聯，為您提供云服務器、網站建設、關鍵詞優化、電子商務、外貿網站建設、靜態網站

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯