java鄰接表
❶ java編程的數據結構編程！急！！圖鏈表的建立與輸出。 實驗內容：輸入有向圖的頂點和邊，建立圖的鄰
public synchronized void method(){
method body
}
❷ java中如何把圖用鄰接表表示出來
package my.graph;
import java.util.ArrayList;
import java.util.Iterator;
import my.queue.*;
import my.stack.StackX;
/**
* 鄰接表表示
* @author xiayi
*
*/
public class Graph {
private int MAX_VERTS = 20;
private Vertex vertexList[];
private boolean is = false;//是否為有向圖
private int nVerts = 0;
private StackX stackX;
private Vertex dfs[];
private Vertex bfs[];
private Queue queue;
public Graph(){
vertexList = new Vertex[MAX_VERTS];
dfs = new Vertex[MAX_VERTS];
bfs = new Vertex[MAX_VERTS];
}
public Graph(int n){
vertexList = new Vertex[n];
dfs = new Vertex[n];
bfs = new Vertex[n];
}
public Graph(int n, boolean is){
this.is = is;
vertexList = new Vertex[n];
dfs = new Vertex[n];
bfs = new Vertex[n];
}
//////////////////////////////////////////////
public boolean isIs() {
return is;
}
public void setIs(boolean is) {
this.is = is;
}
public Vertex[] getVertexList() {
return vertexList;
}
public Vertex[] getDfs() {
return dfs;
}
public Vertex[] getBfs() {
return bfs;
}
////////////////////////////////////////////////////
/**
* 添加頂點
*/
public void addVertex(Vertex vertex){
vertex.setIndex(nVerts);
vertexList[nVerts] = vertex;
nVerts++;
}
/**
* 添加邊
*/
public void addEdge(int start, int end){
vertexList[start].addAdj(vertexList[end]);
if (!is) {vertexList[end].addAdj(vertexList[start]);}
}
/**
* 返回節點個數
* @return
*/
public int getVertsCount(){
return vertexList.length;
}
/**
* 深度優先迭代器
* @return
*/
public Iterator dfsIterator(){
dfs();
return new DfsIterator();
}
/**
* 廣度優先迭代器
* @return
*/
public Iterator bfsIterator(){
bfs();
return new BfsIterator();
}
////////////////////////////////////////////////////////
public void displayGraph(){
ArrayList<Vertex> next = null;
for (int i = 0; i < vertexList.length; i++) {
printVertx(vertexList[i]);
}
}
public void printVertx(Vertex vertex){
ArrayList<Vertex> next = vertex.getAdj();
if(next == null){ System.out.println(vertex.toString()+" 無連接點");}
else{
System.out.print(vertex.toString()+"有鄰接點:");
for (int i = 0; i < next.size(); i++) {
System.out.print("頂點"+next.get(i).label+", ");
}
System.out.println();
}
}
///////////////////////////////////////////////////////////
public void dfs(){
stackX = new StackX(MAX_VERTS);
vertexList[0].isVisted = true;
dfs[0] = vertexList[0];
stackX.push(vertexList[0]);
int dfsIndex = 0;
Vertex vertex;
while(!stackX.isEmpty()){
vertex = getAdjVertex((Vertex)stackX.peek());
if(vertex == null){
stackX.pop();
}else{
vertex.isVisted = true;
dfs[++dfsIndex]=vertex;
stackX.push(vertex);
}
}
for (int i = 0; i < getVertsCount(); i++) {
vertexList[i].isVisted = false;
}
}
public void bfs() {
queue = new Queue(MAX_VERTS);
vertexList[0].isVisted = true;
bfs[0] = vertexList[0];
queue.insert(vertexList[0]);
int bfsIndex = 0;
Vertex vertex;
while(!queue.isEmpty()){
Vertex vertex2 = (Vertex)queue.remove();
while((vertex = getAdjVertex(vertex2))!=null){
vertex.isVisted = true;
bfs[++bfsIndex] = vertex;
queue.insert(vertex);
}
}
for (int i = 0; i < getVertsCount(); i++) {
vertexList[i].isVisted = false;
}
}
/**
* 得到一個鄰接點
* @param vertex
* @return
*/
public Vertex getAdjVertex(Vertex vertex){
ArrayList<Vertex> adjVertexs = vertex.getAdj();
for (int i = 0; i < adjVertexs.size(); i++) {
if(!adjVertexs.get(i).isVisted){
return adjVertexs.get(i);
}
}
return null;
}
/////////////////////////////////////////////////////////////
private abstract class GraphIterator implements Iterator{
int count = 0;
public GraphIterator(){
}
public boolean hasNext() {
return count != getVertsCount()-1;
}
public Object next() {
// TODO Auto-generated method stub
return null;
}
public void remove() {
// TODO Auto-generated method stub
}
}
//深度優先迭代
private class DfsIterator extends GraphIterator{
public DfsIterator(){
super();
}
public Vertex next() {
return dfs[count++];
}
}
//廣度優先迭代
private class BfsIterator extends GraphIterator{
public BfsIterator(){
super();
}
public Object next() {
return bfs[count++];
}
}
/////////////////////////////////////////////////////////
public static void main(String[] args) {
int nVerts = 10;
int c = 'A'-1;
Vertex vertex;
Graph myGraph = new Graph(nVerts, false);
for (int i = 0; i < nVerts; i++) {
c++;
vertex = new Vertex((char)(c));
myGraph.addVertex(vertex);
}
myGraph.addEdge(0, 1);
myGraph.addEdge(0, 4);
myGraph.addEdge(1, 2);
myGraph.addEdge(2, 3);
myGraph.addEdge(4, 5);
myGraph.addEdge(4, 6);
myGraph.addEdge(5, 8);
myGraph.addEdge(6, 7);
myGraph.addEdge(7, 8);
myGraph.addEdge(8, 9);
System.out.println("深度優先迭代遍歷：");
for (Iterator iterator = myGraph.dfsIterator(); iterator.hasNext();) {
vertex = (Vertex) iterator.next();
System.out.println(vertex.toString());
}
System.out.println("/n廣度優先迭代遍歷：");
for (Iterator iterator = myGraph.bfsIterator(); iterator.hasNext();) {
vertex = (Vertex) iterator.next();
System.out.println(vertex.toString());
}
}
}
class Vertex{
public char label;
public boolean isVisted;
public int index;
private ArrayList<Vertex> next = null;
public Vertex(char lab) // constructor
{
label = lab;
isVisted = false;
}
//為節點添加鄰接點
public void addAdj(Vertex ver){
if(next == null) next = new ArrayList<Vertex>();
next.add(ver);
}
public ArrayList<Vertex> getAdj(){
return next;
}
public void setIndex(int index){
this.index = index;
}
public String toString(){
return "頂點 "+label+",下標："+index+".";
}
}
代碼來自：http://blog.csdn.net/Java2King/article/details/5683429
❸ 用JAVA寫圖的操作與實現
...
這不是數據結構么
書上應該有演算法, 好好看看書吧
圖應該是鄰接表存儲方式, 存儲方式弄好了, 就是演算法的事情了, 書上都有
不過畢業這么多年了, 除了遍歷, 其他都記不清了...
❹ 如何實時更新鄰接表邊的權值java
本系列文章主要學習如何使用JAVA語言以鄰接表的方式實現了數據結構---圖（Graph），這是第一篇文章，學習如何用JAVA來表示圖的頂點。從數據的表示方法來說，有二種表示圖的方式：一種是鄰接矩陣，其實是一個二維數組；一種是鄰接表，其實是一個頂點表，每個頂點又擁有一個邊列表。下圖是圖的鄰接表表示。
從圖中可以看出，圖的實現需要能夠表示頂點表，能夠表示邊表。鄰接表指是的哪部分呢？每個頂點都有一個鄰接表，一個指定頂點的鄰接表中，起始頂點表示邊的起點，其他頂點表示邊的終點。這樣，就可以用鄰接表來實現邊的表示了。如頂點V0的鄰接表如下：
與V0關聯的邊有三條，因為V0的鄰接表中有三個頂點(不考慮V0)。
❺ 拓撲排序 鄰接表java
建議去 CSDN 上面搜搜 或者 提問。還有www.javaeye.com
很多大牛
❻ java程序打包的問題
首先選定圖的類別(有向圖、無向圖)，再選定圖的存儲結構，根據輸入的頂點或者邊建立圖;並把相應的鄰接表或者鄰接矩陣輸出;
根據已有的鄰接矩陣或鄰接表用遞歸方法編寫深度優先搜索遍歷演算法，並輸出遍歷結果;
圖的深度遍歷原則:
1 如果有可能，訪問一個領接的未訪問的節點，標記它，並把它放入棧中。
2 當不能執行規則 1 時，如果棧不為空，則從棧中彈出一個元素。
3 如果不能執行規則 1 和規則 2 時，則完成了遍歷。
代碼中的圖使用的是Graph 圖-鄰接矩陣法 來表示，其他的表示法請見:Graph 圖-鄰接表法
代碼中的Stack為輔助結構，用來記載訪問過的節點。棧的詳細描述可以見:ArrayStack 棧 ，LinkedStack 棧 。
Vertex表示圖中的節點，其中包含訪問，是否訪問，清除訪問標志的方法。 Graph.main:提供簡單測試。代碼可以以指定下標的節點開始作深度遍歷。 代碼比較簡單，除了Graph.dsf(int i)深度優先遍歷演算法外沒有過多注釋。
❼ java中的單向鏈表，棧，串，有哪些對象使用的這些數據結構，還有樹，圖，廣義表這些在JAVA有哪些對象
java的我不太清楚，不過像樹和圖這些東西一般要自己寫的，可以用到基本的數據結構，雖然提供了類似tree的數據結構，不過感覺沒有自己寫的用起來方便。就比如二叉樹，一般會用到鏈表，而鏈表在java裡面則有提供List；圖從存儲結構上講有鄰接表和鄰接矩陣兩種，其實也就對應了鏈表和數組，數組在java裡面則有ArrayList等數據結構。廣義表則是鏈表的推廣，本質數據結構還是鏈表。
❽ 求java大神！下面是一個用java表示圖的程序（鄰接表表示法）；在運行的時候提示NullPointerException。
graphHead[] ADTGraph=new graphHead[N];
可是你數組裡面 每一個graphHead都沒有初始化！！每一個graphHead[i]=new graphHead();
❾ 實現圖的鄰接矩陣和圖的鄰接表的完整代碼
給你一個鄰接表的完整程序：
#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)
{
cout<<current->data<<" ";
current=current->next;
}
cout<<endl;
}
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!=NULL&&p->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(i<n&&i>1)//先找到第i個結點，用p存第i個結點，用q存i後的結點，用h存要插入的結點
{
for(int j=1;j<i;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!=a&&p->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!=x&&p->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(i<n&&i>1)//i結點在中間的時候
{
for(int j=1;j<i;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;i<10;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;
cin>>m;
}while(m<1||m>6);//當輸入的序號不在包括中，讓他重新輸入
switch(m)
{
case 1:
{
A.Display ();
goto menu;
};break;
case 2:
{
cout<<"請輸入你想要找到的結點："<<endl;
int c;
cin>>c;//輸入你想要找到的結點
if(A.Find (c)==1)
{
cout<<"可以找到"<<c<<endl;
A.Display ();//重新顯示出鏈表A
}
else
{
cout<<"鏈表中不存在"<<c<<endl;
A.Display ();//重新顯示出鏈表A
}
goto menu;
};break;
case 3:
{
cout<<"請選擇你要插入的方式(選擇前面的序號進行選擇）"<<endl;
cout<<"1.將特定的結點加入到特定的結點前"<<'\t'<<"2.將特定的結點加到特定的位置後"<<endl;
int b1;
do
{
cout<<"請輸入你想要插入的方式（選擇前面的序號進行選擇）："<<endl;
cin>>b1;
}while(b1<1||b1>2);//當輸入的序號不在包括中，讓他重新輸入
if(b1==1)
{
cout<<"請輸入你想要插入的數和想要插入的結點（為此結點之前插入）："<<endl;
int a1,a2;
cin>>a1>>a2;
A.Insertlist (a1,a2);//將a1插入到結點為a2結點之前
cout<<"此時鏈表為："<<endl;
A.Display ();//重新顯示出鏈表A
}
else
{
cout<<"請輸入你想要插入的數和想要插入的位置（為此結點之後插入）："<<endl;
int a1,a2;
cin>>a1>>a2;
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;
cin>>b1;
}while(b1<1||b1>2);//當輸入的序號不在包括中，讓他重新輸入
if(b1==1)
{
cout<<"請輸入你想要刪除的結點："<<endl;
int a;
cin>>a;//輸入你想要刪除的結點
if(A.Delete (a)==1)
{
cout<<"成功刪除"<<a<<endl;
cout<<"刪除後的鏈表為："<<endl;
A.Display ();
}
else
{
cout<<"此鏈表為："<<endl;
A.Display ();//重新顯示出鏈表A
cout<<"鏈表中不存在"<<a<<endl;
}
}
else
{
cout<<"請輸入你想要刪除的結點位置："<<endl;
int b;
cin>>b;//輸入你想要刪除的結點的位置
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;i<mapsize;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!=0&&y!=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;//返回鄰接表頭
}