图的存储结构(Java)

我会带着你远行 2021-12-24 17:35 166阅读 0赞

1 //1 无向图的邻接矩阵实现 时间复杂度:O(n^2) 空间复杂度:O(n^2)
     2 class Graph
     3 {
     4     public int[][] adjacencyMatrix;  //邻接矩阵
     5     public int vexnum;  //边数
     6     public int arcnum;  //顶点数
     7     public char[] vexs;  //顶点数组
     8     
     9     public Graph(int vexnum, int arcnum)
    10     {
    11         this.vexnum = vexnum;
    12         this.arcnum = arcnum;
    13         this.adjacencyMatrix = new int[vexnum][vexnum];
    14         this.vexs = new char[vexnum];
    15     }
    16     
    17     public void createUDG()  
    18     {
    19         //1 创建顶点数组
    20         Scanner input = new Scanner(System.in);
    21         for(int i = 0; i < this.vexnum; i++)
    22             this.vexs[i] = input.next().charAt(0);
    23         
    24         //2 初始化邻接矩阵
    25         for(int j = 0; j < this.vexnum; j++)
    26             for(int k = 0; k < this.vexnum; k++)
    27                 this.adjacencyMatrix[j][k] = 0;
    28         
    29         //3 根据顶点创建邻接矩阵
    30         for(int p = 0; p < this.arcnum; p++)
    31         {
    32             char a = input.next().charAt(0);
    33             char b = input.next().charAt(0);
    34             int i = this.locateVex(a);
    35             int j = this.locateVex(b);
    36             this.adjacencyMatrix[i][j] = this.adjacencyMatrix[j][i] = 1; //对称阵
    37         }
    38     }
    39     
    40     public int locateVex(char vex)
    41     {
    42         int i;
    43         for(i = 0; i < this.vexs.length && vex != this.vexs[i]; i++);
    44         return i;
    45     }
    46 }
    47 
    48 //2 有向图的邻接矩阵实现 时间复杂度:O(n^2) 空间复杂度:O(n^2)
    49 class Graph  
    50 {
    51     public int[][] adjacencyMatrix;
    52     public int vexnum;
    53     public int arcnum;
    54     public char[] vexs;
    55     
    56     public Graph(int vexnum, int arcnum)
    57     {
    58         this.vexnum = vexnum;
    59         this.arcnum = arcnum;
    60         this.adjacencyMatrix = new int[vexnum][vexnum];
    61         this.vexs = new char[vexnum];
    62     }
    63     
    64     public void createDG()
    65     {
    66         Scanner input = new Scanner(System.in);
    67         for(int i = 0; i < this.vexnum; i++)
    68             this.vexs[i] = input.next().charAt(0);
    69         for(int j = 0; j < this.vexnum; j++)
    70             for(int k = 0; k < this.vexnum; k++)
    71                 this.adjacencyMatrix[j][k] = 0;
    72         for(int p = 0; p < this.arcnum; p++)
    73         {
    74             char a = input.next().charAt(0);
    75             char b = input.next().charAt(0);
    76             int i = this.locateVex(a);
    77             int j = this.locateVex(b);
    78             this.adjacencyMatrix[i][j] = 1;
    79         }
    80     }
    81     
    82     public int locateVex(char vex)
    83     {
    84         int i;
    85         for(i = 0; i < this.vexs.length && vex != this.vexs[i]; i++);
    86         return i;
    87     }
    88 }

1 //1 无向图的邻接表实现 时间复杂度: O(n+e) 空间复杂度: O(n+e)
      2 class ArcNode  //边结点
      3 {
      4     //public int info;
      5     public int adjvex;
      6     public ArcNode nextarc;
      7     
      8     public ArcNode(int adjvex)
      9     {
     10         this.adjvex = adjvex;
     11         this.nextarc = null;
     12     }
     13 }
     14 
     15 class VexNode  //顶点结点
     16 {
     17     public char data;
     18     public ArcNode firstarc;
     19     
     20     public VexNode(char data)
     21     {
     22         this.data = data;
     23         this.firstarc = null;
     24     }
     25 }
     26 
     27 class Graph 
     28 {
     29     public VexNode[] vexs;  //顶点数组
     30     public int vexnum;  //顶点数
     31     public int arcnum;  //边数
     32     
     33     public Graph(int vexnum, int arcnum)
     34     {
     35         this.vexnum = vexnum;
     36         this.arcnum = arcnum;
     37         this.vexs = new VexNode[vexnum];
     38     }
     39     
     40     public void createUDG()
     41     {
     42         //1 创建顶点数组(顶点结点表)
     43         Scanner input = new Scanner(System.in);
     44         for(int i = 0; i < this.vexnum; i++)
     45             this.vexs[i] = new VexNode(input.next().charAt(0));
     46         
     47         //2 根据结点创建邻接表
     48         for(int k = 0; k < this.arcnum; k++)
     49         {
     50             char a = input.next().charAt(0);
     51             char b = input.next().charAt(0);
     52             int i = this.locateVex(a);
     53             int j = this.locateVex(b);
     54             ArcNode a1 = new ArcNode(j);
     55             //使用前插法插入边结点
     56             a1.nextarc = this.vexs[i].firstarc;
     57             this.vexs[i].firstarc = a1;
     58             ArcNode a2 = new ArcNode(i);
     59             a2.nextarc = this.vexs[j].firstarc;
     60             this.vexs[j].firstarc = a2;
     61         }
     62     }
     63     
     64     public int locateVex(char vex)
     65     {
     66         int i;
     67         for(i = 0; i < this.vexs.length && vex != this.vexs[i].data; i++);
     68         return i;
     69     }
     70 }
     71 
     72 //2 有向图的邻接表实现 时间复杂度: O(n+e) 空间复杂度: O(n+e)
     73 class ArcNode
     74 {
     75     //public int info;
     76     public int adjvex;
     77     public ArcNode nextarc;
     78     
     79     public ArcNode(int adjvex)
     80     {
     81         this.adjvex = adjvex;
     82         this.nextarc = null;
     83     }
     84 }
     85 
     86 class VexNode
     87 {
     88     public char data;
     89     public ArcNode firstarc;
     90     
     91     public VexNode(char data)
     92     {
     93         this.data = data;
     94         this.firstarc = null;
     95     }
     96 }
     97 
     98 class Graph  
     99 {
    100     public VexNode[] vexs;
    101     public int vexnum;
    102     public int arcnum;
    103     
    104     public Graph(int vexnum, int arcnum)
    105     {
    106         this.arcnum = arcnum;
    107         this.vexnum = vexnum;
    108         this.vexs = new VexNode[vexnum];
    109     }
    110     
    111     public void createDG()
    112     {
    113         Scanner input = new Scanner(System.in);
    114         for(int i = 0; i < this.vexs.length; i++)
    115             this.vexs[i] = new VexNode(input.next().charAt(0));
    116         for(int k = 0; k < this.arcnum; k++)
    117         {
    118             char a = input.next().charAt(0);
    119             char b = input.next().charAt(0);
    120             int i = this.locateVex(a);
    121             int j = this.locateVex(b);
    122             ArcNode a1 = new ArcNode(j);
    123             a1.nextarc = this.vexs[i].firstarc;
    124             this.vexs[i].firstarc = a1;
    125         }
    126     }
    127     
    128     public int locateVex(char vex)
    129     {
    130         int i;
    131         for(i = 0; i < this.vexs.length && vex != this.vexs[i].data; i++);
    132         return i;
    133     }
    134 }

转载于:https://www.cnblogs.com/Huayra/p/10811201.html