java创建有向图代码,创建有向图的数据结构代码

java怎么绘制有向图

package test;

创新互联自2013年创立以来，先为安庆等服务建站，安庆等地企业，进行企业商务咨询服务。为安庆企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

import java.util.*;

public class GectorGraph {

private Point root;

private ListListString circlePath;

public GectorGraph(String pointName) {

root=new Point(pointName);

}

public GectorGraph(Point point) {

root=point;

}

public boolean hasCirclePath(){

findCirclePath();

return circlePath.size()0;

}

public void findCirclePath(){

ListPoint CirclePoints=findCirclePoint();

if(circlePath==null){circlePath=new ArrayListListString();}

for(Point tempPoint:CirclePoints){

ListString pointPath=new ArrayListString();

findPointPath(tempPoint,root,pointPath);

pointPath.add(root.pointName);

circlePath.add(pointPath);

}

}

public boolean findPointPath(Point target,Point currentPoint,ListString pointPath){

if(currentPoint.equals(target)){return true;}

if(!currentPoint.hasNext()){return false;}

ListPoint pointList= currentPoint.getNextPointList();

for(Point tempPoint:pointList){

if(tempPoint.equals(root)){continue;}

if(findPointPath(target,tempPoint,pointPath)){

pointPath.add(tempPoint.pointName);

return true;

}

}

return false;

}

private ListPoint findCirclePoint(){

if(!root.hasNext()){return null;}

ListPoint circlePoints=new ArrayListPoint();

findCirclePoint(root,root,circlePoints);

return circlePoints;

}

private void findCirclePoint(Point root,Point currentPoint,ListPoint circlePoints){

if(!currentPoint.hasNext()){return;}

ListPoint pointList= currentPoint.getNextPointList();

for(Point tempPoint:pointList){

if(tempPoint.equals(root)){circlePoints.add(currentPoint);}

else{findCirclePoint(root,tempPoint,circlePoints);}

}

}

public void showPath(){

if(circlePath==null){System.out.println("Error");}

for(ListString tempList:circlePath){

StringBuffer pathString=new StringBuffer();

int tempListIndex=tempList.size()-1;

for(;tempListIndex-1;tempListIndex--){

pathString.append(tempList.get(tempListIndex));

if(tempListIndex!=0){pathString.append("-");}

}

System.out.println(pathString.toString());

}

}

public static void main(String[] args) {

Point root=new Point("root");

ListPoint p3=new ArrayListPoint();

for(int i=0;i3;i++){

p3.add(new Point("3/1/"+i));

}

ListPoint p4=new ArrayListPoint();

for(int i=0;i3;i++){

p4.add(new Point("3/2/"+i));

}

ListPoint p2=new ArrayListPoint();

for(int i=0;i2;i++){

p2.add(new Point("2/"+i));

}

p3.add(0,root);

p3.get(2).addNextPoint(root);

p4.get(0).addNextPoint(root);

p2.get(0).addNextPointList(p3);

p2.get(1).addNextPointList(p4);

root.addNextPointList(p2);

GectorGraph gg=new GectorGraph(root);

if(gg.hasCirclePath()){

gg.showPath();

}

}

}

class Point{

public String pointName;

private ListPoint nextPointList;

public Point(String pointName) {

this.pointName=pointName;

}

public void addNextPoint(Point p){

if(nextPointList==null){nextPointList=new ArrayListPoint();}

nextPointList.add(p);

}

public void addNextPointList(ListPoint pList){

if(nextPointList==null){nextPointList=new ArrayListPoint();}

nextPointList.addAll(pList);

}

public boolean hasNext(){

return nextPointList!=null!nextPointList.isEmpty();

}

public ListPoint getNextPointList() {

return nextPointList;

}

public void setNextPointList(ListPoint nextPointList) {

this.nextPointList = nextPointList;

}

}

请编写一个完整的程序，建立有向图的邻接表存储结构，要求：

给你一个邻接表的完整程序：

#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;//返回邻接表头

}

4啊4->'>求一段java程序，求图是否存在环。该图是有向图。要求该方法输入边的序对集合，比如3->4啊4->

一个顶点a在一个环上，那么存在以它为终点的边, 假设这些边的起点集合为PreA, 考察点a能否到达点PreA中的点，如果到达就找到了一个环，否则点a不在环上。

遍历图中的顶点进行上述操作即可。

用java怎么用迪杰斯特拉算有向图有权值的最短路径

　Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式

用OPEN,CLOSE表的方式，其采用的是贪心法的算法策略，大概过程如下：

1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点

2.初始阶段，将初始节点放入close，其他所有节点放入open

3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点

代码实例如下：

Node对象用于封装节点信息，包括名字和子节点

[java] view plain copy

public class Node {

private String name;

private MapNode,Integer child=new HashMapNode,Integer();

public Node(String name){

this.name=name;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public MapNode, Integer getChild() {

return child;

}

public void setChild(MapNode, Integer child) {

this.child = child;

}

}

MapBuilder用于初始化数据源，返回图的起始节点

[java] view plain copy

public class MapBuilder {

public Node build(SetNode open, SetNode close){

Node nodeA=new Node("A");

Node nodeB=new Node("B");

Node nodeC=new Node("C");

Node nodeD=new Node("D");

Node nodeE=new Node("E");

Node nodeF=new Node("F");

Node nodeG=new Node("G");

Node nodeH=new Node("H");

nodeA.getChild().put(nodeB, 1);

nodeA.getChild().put(nodeC, 1);

nodeA.getChild().put(nodeD, 4);

nodeA.getChild().put(nodeG, 5);

nodeA.getChild().put(nodeF, 2);

nodeB.getChild().put(nodeA, 1);

nodeB.getChild().put(nodeF, 2);

nodeB.getChild().put(nodeH, 4);

nodeC.getChild().put(nodeA, 1);

nodeC.getChild().put(nodeG, 3);

nodeD.getChild().put(nodeA, 4);

nodeD.getChild().put(nodeE, 1);

nodeE.getChild().put(nodeD, 1);

nodeE.getChild().put(nodeF, 1);

nodeF.getChild().put(nodeE, 1);

nodeF.getChild().put(nodeB, 2);

nodeF.getChild().put(nodeA, 2);

nodeG.getChild().put(nodeC, 3);

nodeG.getChild().put(nodeA, 5);

nodeG.getChild().put(nodeH, 1);

nodeH.getChild().put(nodeB, 4);

nodeH.getChild().put(nodeG, 1);

open.add(nodeB);

open.add(nodeC);

open.add(nodeD);

open.add(nodeE);

open.add(nodeF);

open.add(nodeG);

open.add(nodeH);

close.add(nodeA);

return nodeA;

}

}

图的结构如下图所示：

Dijkstra对象用于计算起始节点到所有其他节点的最短路径

[java] view plain copy

public class Dijkstra {

SetNode open=new HashSetNode();

SetNode close=new HashSetNode();

MapString,Integer path=new HashMapString,Integer();//封装路径距离

MapString,String pathInfo=new HashMapString,String();//封装路径信息

public Node init(){

//初始路径,因没有A-E这条路径,所以path(E)设置为Integer.MAX_VALUE

path.put("B", 1);

pathInfo.put("B", "A-B");

path.put("C", 1);

pathInfo.put("C", "A-C");

path.put("D", 4);

pathInfo.put("D", "A-D");

path.put("E", Integer.MAX_VALUE);

pathInfo.put("E", "A");

path.put("F", 2);

pathInfo.put("F", "A-F");

path.put("G", 5);

pathInfo.put("G", "A-G");

path.put("H", Integer.MAX_VALUE);

pathInfo.put("H", "A");

//将初始节点放入close,其他节点放入open

Node start=new MapBuilder().build(open,close);

return start;

}

public void computePath(Node start){

Node nearest=getShortestPath(start);//取距离start节点最近的子节点,放入close

if(nearest==null){

return;

}

close.add(nearest);

open.remove(nearest);

MapNode,Integer childs=nearest.getChild();

for(Node child:childs.keySet()){

if(open.contains(child)){//如果子节点在open中

Integer newCompute=path.get(nearest.getName())+childs.get(child);

if(path.get(child.getName())newCompute){//之前设置的距离大于新计算出来的距离

path.put(child.getName(), newCompute);

pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"-"+child.getName());

}

}

}

computePath(start);//重复执行自己,确保所有子节点被遍历

computePath(nearest);//向外一层层递归,直至所有顶点被遍历

}

public void printPathInfo(){

SetMap.EntryString, String pathInfos=pathInfo.entrySet();

for(Map.EntryString, String pathInfo:pathInfos){

System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());

}

}

/**

* 获取与node最近的子节点

*/

private Node getShortestPath(Node node){

Node res=null;

int minDis=Integer.MAX_VALUE;

MapNode,Integer childs=node.getChild();

for(Node child:childs.keySet()){

if(open.contains(child)){

int distance=childs.get(child);

if(distanceminDis){

minDis=distance;

res=child;

}

}

}

return res;

}

}

Main用于测试Dijkstra对象

[java] view plain copy

public class Main {

public static void main(String[] args) {

Dijkstra test=new Dijkstra();

Node start=test.init();

test.computePath(start);

test.printPathInfo();

}

}

java读取txt文档并将数据当做节点构成有向图！

分少懒得写，添加一个画布组件，节点用圆形素材，有向图用箭头素材。

先添加节点， 后连线，完毕

文章名称：java创建有向图代码,创建有向图的数据结构代码
网页路径：http://6mz.cn/article/dseepdg.html