数据结构java语言描述-图--代码
程序员文章站
2024-02-20 14:08:52
...
创建邻接矩阵表示的无向图、有向图、有向网。
网:带权的图。
package 图Graph;
import java.util.Scanner;
public class Graph<T>{
protected final int MAXSIZE=10;
protected final int MAX=999;
protected T[] V; //顶点信息
protected int[][] arcs; //邻接矩阵
protected int e; //边数
protected int n; //顶点数
public static int inf=100000; //用于表示无穷大,即无路径可到达
public Graph( ){
V =(T[]) new Object[MAXSIZE];
arcs=new int[MAXSIZE][MAXSIZE];
}
public void GreateAdj() { // 建立邻接矩阵 无向图 时间复杂度O(n^2)
int i,j,k;
T v1,v2;
Scanner sc=new Scanner(System.in);
System.out.println("请输入图的顶点数及边数");
System.out.print("顶点数n=");n=sc.nextInt();
System.out.print("边数e=");e=sc.nextInt();
System.out .print ("请输人图的顶点信息: ");
String str=sc.next();
for (i=0;i<n;i++) {
V[i]= (T) (Object)str.charAt(i);//构造顶点信息
}
// for(i=0;i<n;i++)
// for (j=0;j<n;j++)
// arcs[i][j]=0;//初始化邻接矩阵
System.out.println ("请输人图的边的信息: ");
for(k=0;k<e;k++) {
System.out .print ("请输人第"+(k+1)+"条边的两个瑞点: ");
str=sc.next();//输人一条边的两个顶点
v1=(T) (Object)str.charAt(0);
v2=(T) (Object)str.charAt(1) ;
//确定两个顶点在图G中的位置
i=LocateVex (v1);j=LocateVex(v2); //算法 6-1,51行
if(i>=0 && j>=0) { //构建无向图
arcs[i][j]=1;
arcs[j][i]=1;
}
// if(i>=0 && j>=0) { //构建有向图
// arcs[i][j]=1;
// }
}
}
public void GreateAdjW() { // 建立邻接矩阵 有向网 时间复杂度O(n^2)
int i,j,k;
T v1,v2;
Scanner sc=new Scanner(System.in);
System.out.println("请输入图的顶点数及边数");
System.out.print("顶点数n=");n=sc.nextInt();
System.out.print("边数e=");e=sc.nextInt();
System.out .print ("请输人图的顶点信息: ");
String str=sc.next();
for (i=0;i<n;i++) {
V[i]= (T) (Object)str.charAt(i);//构造顶点信息
}
for(i=0;i<n;i++) //初始化邻接矩阵
for (j=0;j<n;j++)
arcs[i][j]=inf;
System.out.println ("请输人图的边的信息: ");
for(k=0;k<e;k++) {
int weight; //定义一个权值
System.out .print ("请输人第"+(k+1)+"条边的两个瑞点: ");
str=sc.next();//输人一条边的两个顶点
v1=(T) (Object)str.charAt(0);
v2=(T) (Object)str.charAt(1) ;
System.out.println("权值:"); weight=sc.nextInt();
//确定两个顶点在图G中的位置
i=LocateVex (v1);j=LocateVex(v2); //算法 6-1,51行
if(i>=0 && j>=0) { //构建权值为weight的路径
arcs[i][j]=weight;
}
}
}
public int LocateVex(T v){ //在图G中查找顶点
int i;
for(i=0;i<n;i++) {
if(V[i]==v) {
return i;
}
}
return -1;
}
public void DisplayAdjMatrix( ){ //在屏幕上显示图G的邻接矩阵表示
int i,j;
System.out.println("图的邻接矩阵表示:");
for(i=0;i<n;i++){
for(j=0;j<n;j++){
System.out.print(" "+arcs[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Graph<Character> G=new Graph<Character>();
G.GreateAdj();
G.DisplayAdjMatrix();
}
}
效果图:
创建邻接表表示的无向图、有向图的邻接表、逆邻接表。
public class ArcNode { //边结点的类型定义
int adjVex; //存放邻接的点的序号
ArcNode nextArc; //指向Vi 下一个邻接点的边结点
int weight; //权值
public ArcNode () {
adjVex=0; weight=0; nextArc=null;
}
}
public class VNode<T> { //顶点结点类型定义
T data; //存储顶点的名称或其相关信息
ArcNode firstArc; //指向 顶点Vi的第一个邻接点的边结点
public VNode() {
data=null; firstArc=null;
}
}
import java.util.Scanner;
public class ALGraph<T> {
protected final int MAXSIZE=10;
protected VNode[] adjList; //顶点结点信息
int n,e;// 图的顶点数和弧数
public ALGraph() {
adjList=new VNode [MAXSIZE] ;
}
public void CreateLink(){ //创建无向图的邻接表 时间复杂度O(n+e)
int i,j, k;
T v1, v2;
String str;
Scanner sc=new Scanner(System.in);
System.out.println ("请输人图的顶点数及边数");
System.out.print ("顶点数n=");n=sc.nextInt();
System.out.print("边数e=") ;e=sc.nextInt() ;
System.out.println ("请输入图的顶点信息: ") ;
str=sc.next();
for(i=0; i<n; i++) {
adjList[i]=new VNode<T> () ;
adjList[i].data=str.charAt(i) ; //构造顶点信息
adjList[i].firstArc=null;
}
System.out.println("请输入图的边的信息: ");
for (k=0; k<e; k++) {
System. out.print ("请输入第"+ (k+1) +"条边的两个端点: ") ;
str=sc.next() ;//输人一条边的两个顶点
v1=(T) (Object) str.charAt(0) ;
v2= (T) (Object) str.charAt(1) ;
//确定两个顶点在图G中的位置
i=LocateVex(v1) ;j=LocateVex(v2) ;
if (i>=0&&j>=0) {
ArcNode s=new ArcNode();
s.adjVex=j ;
s.nextArc=adjList[i].firstArc;
adjList[i].firstArc=s;
s=new ArcNode () ;
s .adjVex=i;
s .nextArc=adjList[j].firstArc;
adjList[j].firstArc=s;
}
}
}
public void CreateLinkY(){ //创建有向图的邻接表 时间复杂度O(n+e)
int i,j, k;
T v1, v2;
String str;
Scanner sc=new Scanner(System.in);
System.out.println ("请输人图的顶点数及边数");
System.out.print ("顶点数n=");n=sc.nextInt();
System.out.print("边数e=") ;e=sc.nextInt() ;
System.out.println ("请输入图的顶点信息: ") ;
str=sc.next();
for(i=0; i<n; i++) {
adjList[i]=new VNode<T> () ;
adjList[i].data=str.charAt(i) ; //构造顶点信息
adjList[i].firstArc=null;
}
System.out.println("请输入图的边的信息: ");
for (k=0; k<e; k++) {
System. out.print ("请输入第"+ (k+1) +"条边的两个端点: ") ;
str=sc.next() ;//输人一条边的两个顶点
v1=(T) (Object) str.charAt(0) ;
v2= (T) (Object) str.charAt(1) ;
//确定两个顶点在图G中的位置
i=LocateVex(v1) ;j=LocateVex(v2) ;
if (i>=0&&j>=0) { //若要求逆邻接表,只需将下面的i换为j,j换为i
ArcNode s=new ArcNode();
s.adjVex=j;
s.nextArc=adjList[i].firstArc;
adjList[i].firstArc=s;
}
}
}
//在图中查找顶点v,找到后返回其在顶点数组中的索引号
public int LocateVex(T v) {
int i;
for(i=0; i<n; i++)
if (adjList[i] .data==v) return i;
return -1 ;
}
public void DisplayAdjList(){ //在屏幕上显示图的邻接表表示
int i;
ArcNode p;
System.out.println ("图的邻接表表示: ") ;
for (i=0; i<n; i++) {
System.out.print ("\n "+adjList[i] .data) ;
p=adjList[i].firstArc;
while (p!=null) {
System.out.print ("-->"+p.adjVex) ;p=p. nextArc;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ALGraph<Character> G=new ALGraph<Character> () ;
G.CreateLink() ;
G.DisplayAdjList() ;
}
}
效果图:
上一篇: 数据结构与算法-图(JAVA语言描述)
下一篇: 算法设计——数字三角形