欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构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();
	}
}

效果图:

数据结构java语言描述-图--代码

创建邻接表表示的无向图、有向图的邻接表、逆邻接表。

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语言描述-图--代码