数据结构-->图

package 图;

import java.util.Scanner;

public class GraphType { static Scanner sc=new Scanner(System.in);

static void CreateGraph(Graph g) { //创建邻接矩阵图 int i,j,k; int weight;//权 char EstartV,EendV;//边的起始顶点 System.out.printf("输入 各顶点的 信息\n");//输入各顶点的信息 for(i=0;i<g.VertexNUM;i++) { System.out.printf("第%d个顶点 ",i+1); g.Vertex[i]=(sc.next().toCharArray())[0];//保存到各顶点数组元素中 } System.out.printf("输出构成各边的顶点以及权值：\n"); for(k=0;k<g.EdgeNum;k++) { System.out.printf("第%d个边 ",k+1); EstartV=sc.next().charAt(0); EendV=sc.next().charAt(0); weight=sc.nextInt(); for(i=0;EstartV<g.VertexNUM;i++);//在已有节点中 查找开始节点 for(j=0;EendV<g.VertexNUM;j++);//在已有节点中 查找结束节点 g.EdgeWeight[i][j]=weight;//对应位置保存权值，表示有一条边 if(g.Type==1) { //如果是无向图 } } } /*清空矩阵*/ static void GraphicClear(Graph g) { int i,j; for(i=0;i<g.VertexNUM;i++) { for(j=0;i<g.VertexNUM;j++) { g.EdgeWeight[i][j]=Graph.MAXValue;//设置各元素的值为MAXValue } } } /*显示矩阵*/ static void outGraph(Graph g) { int i,j; for(i=0;i<g.VertexNUM;i++) { System.out.printf("\t%c",g.Vertex[i]);//输出顶点信息 } System.out.println(); for(i=0;i<g.VertexNUM;i++) { System.out.printf("\t%c",g.Vertex[i]); for(j=0;j<g.VertexNUM;j++) { if(g.EdgeWeight[i][j]==Graph.MAXValue) { System.out.printf("\t%Z"); }else { System.out.printf("\t%d",g.EdgeWeight[i][j]);//输出边的全值 } } System.out.println(); } } /*遍历图 * （1）从数组中选择一个未被访问的定点，将其标记为1，表示访问过 * （2）从只给你一个未被访问的临节点出发，进行深度优选遍历 * （3）重复（2）之到图中所有和他相通的顶点都被访问过 * （4）重复 步骤（1）（2）（3）直到图中的顶点都被访问过 * */ static void TraverGraph(Graph g,int n) {//从n 开始深度遍历这这个图 int i; g.flag[n]=1;//白哦及该定点已经 处理过 System.out.printf("->%c",g.Vertex[n]);//输出节点数据 //添加处理节点的操 做 for(i=0;i<g.VertexNUM;i++) { if(g.EdgeWeight[n][i]!=Graph.MAXValue&&g.flag[n]==0) { TraverGraph(g,i);//递归遍历 } } } /*深度优先遍历*/ static void TraverG(Graph g) { int i; for(i=0;i<g.VertexNUM;i++) {//清除各顶点遍历标志 g.flag[i]=0; } System.out.printf("深度优先遍历节点:"); for(i=0;i<g.VertexNUM;i++) { if(g.flag[i]==0) { //调用函数遍历 TraverGraph(g,i); } } System.out.printf("\n"); } public static void main(String []args) { Graph g=new Graph();//定义保存邻接表结构的图 System.out.printf("输入生成 图的类型\n"); g.Type=sc.nextInt(); System.out.printf("输入图定点数量\n"); g.VertexNUM=sc.nextInt(); System.out.printf("输入图的边数量\n"); g.EdgeNum=sc.nextInt(); GraphicClear(g);//清空图 CreateGraph(g);//生成邻接表结构的图 System.out.printf("该图的邻接矩阵数据如下\n"); outGraph(g);//输出邻接矩阵 TraverG(g);//深度优先遍历图 } }

class Graph{ static final int MAXNUM=20; static final int MAXValue=65535; char[]Vertex=new char[MAXNUM];//保存顶点信息（序号或字母） int Type;//图的类型 int VertexNUM;//顶i但的数量 int EdgeNum;//边的数量 int [][]EdgeWeight=new int[MAXNUM][MAXNUM];//保存边的权 int []flag=new int [MAXNUM];//遍历标志 }