189 8069 5689
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;//返回邻接表头
}
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);
}
}
用编程实现图的存储一般有常见的有两种方式，第一种是邻接链表、第二种就是邻接矩阵。
邻接链表就是将图中的每一个点都单独作为一个单独链表的起点，为每个顶点保存一个链表。链表的每一个节点都记录了与之相邻的节点的信息。
邻接矩阵就是将图转换成一个二维数组，数组的x和y均表示图中每个节点到其他节点的连接状况，能连通用一种状态表示，不能连通用另外一中方式表示，这样就形成了一个笛卡尔积。也就是一个二维数组。