# 图的邻接矩阵数据结构（基础）

2018-02-27 11:50:10来源:oschina作者:算法之名人点击

import java.util.Scanner;
/**
* Created by Administrator on 2018-02-14.
*/
public class Graph {
static final int MaxNum = 20;
static final int MaxValue = 65535;
public void CreateGraph(GraphMatrix GM) {
int i, j, k;
int weight;
char EstartV, EendV;
Scanner input = new Scanner(System.in);
System.out.println("输入图中各顶点信息");
for (i = 0; i < GM.VertexNum; i++) {
System.out.printf("第%d个顶点:", i + 1);
GM.Vertex[i] = (input.next().toCharArray())[0];
}
System.out.printf("输入构成各条边的顶点及权值:/n");
for (k = 0; k < GM.EdgeNum; k++) {
System.out.printf("第%d条边:", k + 1);
EstartV = input.next().charAt(0);
EendV = input.next().charAt(0);
weight = input.nextInt();
for (i = 0; EstartV != GM.Vertex[i]; i++) ;
for (j = 0; EendV != GM.Vertex[j]; j++) ;
GM.EdgeWeight[i][j] = weight;
if (GM.GType == 0) {
GM.EdgeWeight[j][i] = weight;
}
}
}
public void ClearGraph(GraphMatrix GM) {
int i,j;
for (i = 0;i < GM.VertexNum;i++) {
for (j = 0;j < GM.VertexNum;j++) {
GM.EdgeWeight[i][j] = MaxValue;
}
}
}
public void OutGraph(GraphMatrix GM) {
int i,j;
for (j = 0;j < GM.VertexNum;j++) {
System.out.printf("/t%c",GM.Vertex[j]);
}
System.out.printf("/n");
for (i = 0;i < GM.VertexNum;i++) {
System.out.printf("%c",GM.Vertex[i]);
for (j = 0;j < GM.VertexNum;j++) {
if(GM.EdgeWeight[i][j] == MaxValue) {
System.out.printf("/tZ");
}else {
System.out.printf("/t%d",GM.EdgeWeight[i][j]);
}
}
System.out.printf("/n");
}
}
public void DeepTraOne(GraphMatrix GM,int n) {
int i;
GM.isTrav[n] = 1;
System.out.printf("->%c",GM.Vertex[n]);
for (i = 0;i < GM.VertexNum;i++) {
if(GM.EdgeWeight[n][i] != MaxValue && GM.isTrav[n] == 0) {
DeepTraOne(GM,i);
}
}
}
public void DeepTraGraph(GraphMatrix GM) {
int i;
for (i = 0;i < GM.VertexNum;i++) {
GM.isTrav[i] = 0;
}
System.out.printf("深度优先遍历结点:");
for (i = 0;i < GM.VertexNum;i++) {
if(GM.isTrav[i] == 0) {
DeepTraOne(GM,i);
}
}
System.out.printf("/n");
}
public static void main(String[] args) {
GraphMatrix GM = new GraphMatrix();
Graph gh = new Graph();
System.out.printf("输入生成图的类型:");
Scanner input = new Scanner(System.in);
GM.GType = input.nextInt();
System.out.printf("输入图的顶点数量:");
GM.VertexNum = input.nextInt();
System.out.printf("输入图的边数量:");
GM.EdgeNum = input.nextInt();
gh.ClearGraph(GM);
gh.CreateGraph(GM);
System.out.printf("该图的邻接矩阵数据如下:/n");
gh.OutGraph(GM);
gh.DeepTraGraph(GM);
}
}
class GraphMatrix {
char[] Vertex = new char[Graph.MaxNum];
int GType;
int VertexNum;
int EdgeNum;
int[][] EdgeWeight = new int[Graph.MaxNum][Graph.MaxNum];
int[] isTrav = new int[Graph.MaxNum];
}