现在的位置: 首页 > 综合 > 正文

图1—————图的表示和遍历算法

2013年02月20日 ⁄ 综合 ⁄ 共 7223字 ⁄ 字号 小 中 大 ⁄ 评论关闭

图的表示方法：

邻接矩阵法（太浪费空间，但确实把所有信息都表示了出来，计算度或者各种操作的话很方便，当然用无向图的对称性、只存放非0结点可以优化）

邻接表（算比较好的一种方法，但是对于有向图计算入度必须遍历，用逆邻接表、十字链表优化）

十字链表（和邻接表太类似）

遍历算法：

图是标准的多对多结构，因此不构成环并且不重复访问vertex需要一个标志数组visited，循环这个保证全部都访问，遍历过程中可以有DFS和BFS

DFS:递归方式，首先访问vertex，循环找邻接节点，找到并且该vertex没有被访问过，将顶点当成参数进入下一层。

BFS：需要堆栈配合，找到自己邻接的顶点如果没有被访问过则访问并将其入栈，然后用stack非空控制循环直到全部访问过。

还有一些计算连通分量个数、度的问题，就是遍历算法的应用。

代码（结构写的有点乱，回头看的时候可以优化下）：

[java]
view plaincopy
  1. package nuaa.ds;  
  2.   
  3. public class Graph {  
  4.     private String[] vertexes;//邻接矩阵法所  
  5.     private int[][] vr;       //使用的成员变量  
  6.     private CreateGraph g;  
  7.       
  8.     private VertexNode[] vertexNodes;//邻接表所使用的成员变量  
  9.   
  10.       
  11.     /** 
  12.      * 图的构成实在太多，写个标准无向图熟悉算法 
  13.      * 顶点ABCD（其中BC不连）彼此互连，EF彼此互连 
  14.      */  
  15.     public Graph(CreateGraph c){  
  16.         this.g = c;  
  17.         switch(c){  
  18.         case AdjacencyMatrix://邻接矩阵  
  19.             vertexes = new String[]{"A","B","C","D","E","F"};//ABCDEF6个顶点  
  20.             vr = new int[6][6];  
  21.             vr[0] = new int[]{0,1,1,1,0,0};//邻接矩阵法表示边,相连值为1，不连值为0  
  22.             vr[1] = new int[]{1,0,0,1,0,0};//优点是所有信息全部显示出来  
  23.             vr[2] = new int[]{1,0,0,1,0,0};//这样顶点的度等计算或者对图的所有操作都比较容易  
  24.             vr[3] = new int[]{1,1,1,0,0,0};//缺点也很明显  
  25.             vr[4] = new int[]{0,0,0,0,0,1};//存储空间极大的浪费  
  26.             vr[5] = new int[]{0,0,0,0,1,0};//当然通过使用对称或者只存储非0元素可以优化  
  27.             break;  
  28.         case AdjacencyTable://邻接表表示，省了很多存储空间，  
  29.                             //但有时会带来不便，比如求有向图的某个节点的入度  
  30.               
  31.             //结点数组的初始化  
  32.             vertexNodes = new VertexNode[6];  
  33.             String[] temp = new String[]{"A","B","C","D","E","F"};  
  34.             for(int i=0;i<vertexNodes.length;i++){  
  35.                 vertexNodes[i] = new VertexNode(temp[i]);  
  36.             }  
  37.             //结点数组连接的边结点的初始化  
  38.             //写de好麻烦，还不如由输入流输进来循环构造。但每次测试重新输入图结构也很烦。  
  39.             //顶点A的初始化  
  40.             vertexNodes[0].arcNode = new ArcNode(1);  
  41.             vertexNodes[0].arcNode.arcNode = new ArcNode(2);  
  42.             vertexNodes[0].arcNode.arcNode.arcNode = new ArcNode(3);  
  43.             //顶点B的初始化  
  44.             vertexNodes[1].arcNode = new ArcNode(0);  
  45.             vertexNodes[1].arcNode.arcNode = new ArcNode(3);  
  46.             //顶点C的初始化  
  47.             vertexNodes[2].arcNode = new ArcNode(0);  
  48.             vertexNodes[2].arcNode.arcNode = new ArcNode(3);  
  49.             //顶点D的初始化  
  50.             vertexNodes[3].arcNode = new ArcNode(0);  
  51.             vertexNodes[3].arcNode.arcNode = new ArcNode(1);  
  52.             vertexNodes[3].arcNode.arcNode.arcNode = new ArcNode(2);  
  53.             //顶点E的初始化  
  54.             vertexNodes[4].arcNode = new ArcNode(5);  
  55.             //顶点F的初始化  
  56.             vertexNodes[5].arcNode = new ArcNode(4);  
  57.         }  
  58.               
  59.     }  
  60.       
  61.     //求连通分量个数或者连通生成树也是遍历算法  
  62.     public void traversalByDFS(){  
  63.         this.traversalByDFS(this.g);  
  64.     }  
  65.     private void traversalByDFS(CreateGraph c){//深度优先算法访问图  
  66.         boolean[] visited;  
  67.         if(c==CreateGraph.AdjacencyTable){  
  68.             visited = new boolean[vertexNodes.length];//java默认都为false  
  69.         }else{  
  70.             visited = new boolean[vertexes.length];//java默认都为false  
  71.         }  
  72.         switch(c){  
  73.         case AdjacencyMatrix://图是用邻接表表示的深度优先遍历算法  
  74.               
  75.             for(int i=0;i<vertexes.length;i++){  
  76.                 if(!visited[i]){  
  77.                     mTraversalByDFS(visited,i);  
  78.                 }  
  79.             }  
  80.             break;  
  81.         case AdjacencyTable:  
  82.             for(int i=0;i<vertexNodes.length;i++){  
  83.                 if(!visited[i]){  
  84.                     tTraversalByDFS(visited,i);  
  85.                 }  
  86.             }  
  87.         }  
  88.     }  
  89.       
  90.       
  91.     private void mTraversalByDFS(boolean[] visited,int index){  
  92.         visit(vertexes[index]);//和二叉树一样的问题，访问图结点可能会做些其他操作  
  93.                                 //还是从外部当成函子传入进来比较合适  
  94.                                 //对应的vertexes数组也要改成Object[],这样的封装更好  
  95.         visited[index] = true;  
  96.         for(int i=0;i<vr[index].length;i++){//循环找到下一个结点  
  97.             if(vr[index][i]==1&&!visited[i]){//有连接的未访问的结点  
  98.                 mTraversalByDFS(visited,i);//访问该结点  
  99.             }  
  100.         }  
  101.     }  
  102.       
  103.     private void tTraversalByDFS(boolean[] visited,int index){  
  104.         visit(vertexNodes[index]);  
  105.         visited[index] = true;  
  106.         ArcNode p = vertexNodes[index].arcNode;  
  107.         while(null!=p){  
  108.             if(!visited[p.serialNumber]){  
  109.                 tTraversalByDFS(visited,p.serialNumber);  
  110.             }  
  111.             p = p.arcNode;  
  112.         }  
  113.     }  
  114.       
  115.     public void traversalByBFS(){  
  116.         this.traversalByBFS(g);  
  117.     }  
  118.     private void traversalByBFS(CreateGraph c){  
  119.         boolean[] visited;  
  120.         if(c==CreateGraph.AdjacencyTable){  
  121.             visited = new boolean[vertexNodes.length];//java默认都为false  
  122.         }else{  
  123.             visited = new boolean[vertexes.length];//java默认都为false  
  124.         }  
  125.           
  126.         Stack<VertexNode> stack = new Stack<VertexNode>();  
  127.           
  128.         switch(c){  
  129.         case AdjacencyMatrix://图是用邻接表表示的深度优先遍历算法  
  130.             for(int i=0;i<vertexes.length;i++){  
  131.                 if(!visited[i]){  
  132.                     mTraversalByBFS(visited,i);  
  133.                 }  
  134.             }  
  135.         break;  
  136.         case AdjacencyTable:  
  137.             for(int i=0;i<vertexNodes.length;i++){  
  138.                 if(!visited[i]){  
  139.                     tTraversalByBFS(stack,visited,i);  
  140.                 }  
  141.             }  
  142.         }  
  143.     }  
  144.     private void tTraversalByBFS(Stack<VertexNode> stack,  
  145.                                         boolean[] visited,int index){  
  146.         stack.push(vertexNodes[index]);  
  147.         visit(vertexNodes[index]);  
  148.         visited[index] = true;  
  149.         ArcNode p ;  
  150.         while(!stack.isEmpty()){  
  151.             p = stack.pop().arcNode;  
  152.             while(p!=null){  
  153.                 if(!visited[p.serialNumber]){  
  154.                     stack.push(vertexNodes[p.serialNumber]);  
  155.                     visit(vertexNodes[p.serialNumber]);  
  156.                     visited[p.serialNumber] = true;  
  157.                 }  
  158.                 p = p.arcNode;  
  159.             }  
  160.               
  161.         }  
  162.            
  163.     }  
  164.       
  165.     private void mTraversalByBFS(boolean[] visited,int index){  
  166.         Stack<Integer> stack = new Stack<Integer>();  
  167.         stack.push(index);  
  168.         visit(vertexes[index]);  
  169.         visited[index] = true;  
  170.         while(!stack.isEmpty()){  
  171.             for(int i=0;i<vr[index].length;i++){  
  172.                 if(vr[index][i]==1&&!visited[i]){  
  173.                     stack.push(i);  
  174.                     visit(vertexes[i]);  
  175.                     visited[i] = true;  
  176.                 }  
  177.             }  
  178.             index = stack.pop();  
  179.         }  
  180.           
  181.     }  
  182.     private void visit(String vertex){  
  183.         System.out.print(vertex+" ");  
  184.     }  
  185.       
  186.     private void visit(VertexNode node){  
  187.         System.out.println(node.vertex);  
  188.     }  
  189.       
  190.     class VertexNode{  
  191.         String vertex;  
  192.         ArcNode arcNode;  
  193.         public VertexNode(String vertex){  
  194.             this.vertex = vertex;  
  195.         }  
  196.     }  
  197.   
  198.     class ArcNode{  
  199.         int serialNumber;//存放边连着的节点在vertexNode数组里面的位置  
  200.         ArcNode arcNode;  
  201.         public ArcNode(int serialNumber){  
  202.             this.serialNumber = serialNumber;  
  203.         }  
  204.     }  
  205. }  

一些盲点： 十字链表表示法太相似没有写，邻接矩阵法用广义表的方式对空间进行优化，然后计算连通分量、度可以用来复习下遍历算法。

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞