首页 > 代码库 > 数据结构7——图形(图形的存储)

数据结构7——图形(图形的存储)

图具有的特点是:每个结点有零个或者多个前驱结点,并且有零个或者多个后驱结点。

图的存储方式分为邻接矩阵和邻接表。而邻接矩阵适合于稠密图中,邻接表适合于稀疏图形中。

同时图又分为:有向图,无向图。

结点与结点之间相连是为1,如果不想连则定义为零。

技术分享

 

1:邻接矩阵

主要是邻接矩阵存储的设计方式:图的结点信息存储在线性表中,

                 图的边权值信息存储在二维数组中。

定义一个设计图形的各种方法的类,包括对于边,结点元素的增删。

  1 package com.hone.graph;
  2 
  3 import com.hone.linearlist.SeqList;
  4 
  5 public class AdjMWGraph {
  6     
  7     //定义一个全局变量当不连接的时候定义权重值
  8     static final int maxWeight=1000;
  9     
 10     private  SeqList vertices;                    //用顺序表来存储结点
 11     private int [][] edge;                        //用二维数组来存储边
 12     private int numOfEdges;                        //边的个数
 13     
 14     //定义一个构造函数用于初始化结点的属性,对于有n个结点的无向图,有n*n个结点可以参考
 15     public AdjMWGraph(int maxV){
 16         vertices = new SeqList(maxV);                 //创建顺序表vertices
 17         edge=new int[maxV][maxV];                    //创建二维数组edge
 18         for (int i = 0; i < maxV; i++) {
 19             for (int j = 0; j < maxV; j++) {
 20                 if (i==j) {
 21                      edge[i][j]=0;                    //无向图顺序矩阵存储的时候对角为0
 22                 }else{
 23                     edge[i][j]= maxWeight;
 24                 }
 25             }
 26         }
 27         numOfEdges = 0;
 28     }
 29     
 30     
 31     //定义一个方法用于返回结点的个数
 32     public int  getNumOfVertices(){
 33         return vertices.size();
 34     }
 35     
 36     //定义一个方法用于返回边的个数
 37     public int getNumOfEdges(){
 38         return numOfEdges;
 39     }
 40     
 41     //获得结点v的数据元素
 42     public Object getValue(int v)throws Exception{
 43         return vertices.getDate(v);
 44     }
 45     
 46     //返回   边<v1,v2>之间的权值
 47     public int getWeight(int v1, int v2){
 48         if (v1<0||v1 >= vertices.size()||v2<0||v2>=vertices.size()) {
 49             System.out.println("参数越界,请输入正确的参数");
 50         }
 51         return edge[v1][v2];
 52     }
 53     
 54     //将 某个结点插入        调用顺序表中的插入函数    并且在顺序表的末端插入函数
 55     public void insetVertex(Object vertex)throws Exception{
 56         vertices.insert(vertices.size(), vertex);             
 57     }
 58     
 59     //插入边<v1,v2> 并且权值为weight
 60     public void insertEdge(int v1,int v2,int weight)throws Exception{
 61         if (v1<0||v1 >= vertices.size()||v2<0||v2>=vertices.size()) {
 62             System.out.println("参数越界,请输入正确的参数");
 63         }
 64         edge[v1][v2]= weight;                //重置边的权值
 65         numOfEdges++;                        //边的个数+1
 66     }
 67     
 68     //删除边<v1,v2>        在定义顺序矩阵的时候就规定权值为无穷大的时候边就不存在的,
 69     public void deleteEdge(int v1, int v2)throws Exception{
 70         if (v1<0||v1 >= vertices.size()||v2<0||v2>=vertices.size()) {
 71             System.out.println("参数越界,请输入正确的参数");
 72         }
 73         if (edge[v1][v2]==maxWeight||v1==v2) {
 74             System.out.println("该边不存在!");
 75         }
 76         edge[v1][v2]=maxWeight;                        //将边的权重设为无穷大
 77         numOfEdges--;
 78     }
 79     
 80     //取结点v的第一个邻结点,如果存在则返回结点的下标序号,否则返回-1
 81     public int getFirstNeighbor(int v)throws Exception{
 82         if (v <0||v >= vertices.size()) {
 83             System.out.println("参数越界,请输入正确的参数");
 84         }
 85         for (int col = 0; col <vertices.size(); col++) {
 86             if (edge[v][col]>0&&edge[v][col]<maxWeight) {
 87                 return col;
 88             }
 89         }
 90         return -1;
 91     }
 92     
 93     
 94     //取出结点v1的邻接点v2后的邻接点,如果存在该结点则返回结点的下标值,否则返回-1
 95     public int getNextNeighbor(int v1,int v2)throws Exception{
 96         if (v1 <0||v1 >= vertices.size()||v2 <0||v2 >= vertices.size()) {
 97             System.out.println("参数越界,请输入正确的参数");
 98         }
 99         for (int col = v2+1; col <vertices.size(); col++) {
100             if (edge[v1][col]>0&&edge[v1][col]<maxWeight) {
101                 return col;
102             }
103         }
104         return -1;
105     }
106     
107     //连通图的深度优先遍历
108     public void DFS(int v,boolean[] visited, Visit vs)throws Exception{
109         //其中visited中0表示未访问,1表示已经访问
110         vs.print(getValue(v));
111         visited[v]=true;
112         
113         int w=getFirstNeighbor(v);            //获得v的第一个邻接点
114         while(w!=-1){                        //判断v是否有邻接点,并且判断邻接点是否被访问过
115             if (!visited[w]) {
116                 DFS(w, visited, vs);
117             }
118             w=getNextNeighbor(v, w);        //取出下一个邻接点
119             
120         }
121     }
122     
123     //连通图的广度优先遍历    类似于层序遍历用队列来遍历
124     public void BFS(int v,boolean[] visited, Visit vs)throws Exception{
125         int u,w;
126         
127         SeqQueue queue=new SeqQueue();
128         vs.print(getValue(v));
129         visited[v]=true;
130         
131         //将结点v压入到队列queue中去
132         queue.append(new Integer(v));
133         while(queue.notEmpty()){
134             u=(Integer)queue.delete();            //出队列
135             w=getFirstNeighbor(u);                //并且取出u的第一个邻接点w
136             //判断w是否存在,并且w没有被访问过
137             while(w!=-1){
138                 if (!visited[w]) {
139                     vs.print(getValue(w));
140                     visited[w]=true;
141                     queue.append(w);             //将结点w入队列中
142                 }
143                 //获得结点u的邻接点w的一下一个邻接结点
144                 w=getNextNeighbor(u, w);
145             }
146         }
147     }
148 }

设计一个类用于存储图新的边,以及结点信息。

 1 package com.hone.graph.test;
 2 
 3 import com.hone.graph.AdjMWGraph;
 4 
 5 public class RowColWeight {
 6     int row;            //行下标
 7     int col;            //列下标
 8     int weight;            //权重
 9     
10     //定义一个构造函数用于初始化参数
11     public RowColWeight(int r, int c,int w){
12         row=r;
13         col=c;
14         weight=w;
15     }
16     
17     //static 成员函数,给参数创建AdjMWGraph类对象g,v为结点的数据元素集合,n为结点的个数,rc为边的集合,e为边的个数
18     
19     public static void createGraph(AdjMWGraph g, Object[] v,
20             int n, RowColWeight[] rc,int e) throws Exception{
21         //在图g中插入n个结点
22         for(int i=0; i<n;i++){
23             g.insetVertex(v[i]);
24         }
25         //在图g中插入e个边
26         for (int j = 0; j < e; j++) {
27             g.insertEdge(rc[j].row, rc[j].col, rc[j].weight);
28         }
29         
30     }
31 
32 }

测试图形的信息:

 1 package com.hone.graph.test;
 2 
 3 import com.hone.graph.AdjMWGraph;
 4 import com.hone.graph.Visit;
 5 
 6 public class TestSearch {
 7     
 8     
 9     public static void main(String[] args) {
10         final int maxVertices=100;
11         Visit vs=new Visit();
12         
13         AdjMWGraph graph=new AdjMWGraph(maxVertices);
14         int n=5,e=5;
15         //定义结点元素的集合
16         Character[] a={new Character(‘A‘),
17                        new Character(‘B‘),
18                        new Character(‘C‘),
19                        new Character(‘D‘),
20                        new Character(‘E‘),
21         };
22         
23         RowColWeight[] rowColWeights={new RowColWeight(0, 1, 10),
24                                     new RowColWeight(0, 4, 20),
25                                     new RowColWeight(1, 3, 30),
26                                     new RowColWeight(2, 1, 40),
27                                     new RowColWeight(3, 2, 50),
28                 
29         };
30         try {
31             RowColWeight.createGraph(graph, a, n, rowColWeights, e);
32             System.out.println("结点的个数为:"+graph.getNumOfVertices());
33             System.out.println("边的个数为:"+graph.getNumOfVertices()); 
37             
38         } catch (Exception e1) {
39             e1.printStackTrace();
40         }
41         
42         
43     }
44 
45 }

 

数据结构7——图形(图形的存储)