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;//返回邻接表头
}
一个顶点a在一个环上，那么存在以它为终点的边, 假设这些边的起点集合为PreA, 考察点a能否到达点PreA中的点，如果到达就找到了一个环，否则点a不在环上。
遍历图中的顶点进行上述操作即可。
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();
}
}
分少懒得写，添加一个画布组件，节点用圆形素材，有向图用箭头素材。
先添加节点， 后连线，完毕
