`

Graph data structure

J# 
阅读更多

1. adjacent matrix

good for border scan, bad for space O(n*n), spare matrix mostly

java 代码
  1.   
  2. public class GraphMatrix {   
  3.     private int[][] nodeMatrix;   
  4.     private int matrixSize;    
  5.        
  6.     public GraphMatrix(int matrixSize) {   
  7.         this.matrixSize = matrixSize;   
  8.         nodeMatrix = new int[matrixSize][matrixSize];   
  9.         init();   
  10.     }   
  11.        
  12.     private void init() {   
  13.         for (int i=0; i
  14.             for (int j=0; j
  15.                 nodeMatrix[i][j] = 0;   
  16.             }   
  17.         }   
  18.     }   
  19.        
  20.     public boolean addBorder(int startNode, int endNode) {   
  21.         if (hasBorder(startNode, endNode)) {   
  22.             System.err.println("already has a border!!!");   
  23.             return false;   
  24.         }   
  25.         nodeMatrix[startNode][endNode] = 1;   
  26.         return true;   
  27.     }   
  28.        
  29.     public boolean hasBorder(int startNode, int endNode) {   
  30.         if (nodeMatrix[startNode][endNode] == 1) {   
  31.             return true;   
  32.         }   
  33.         return false;   
  34.     }   
  35.            
  36.     public boolean deleteBorder(int startNode, int endNode) {   
  37.         if (!hasBorder(startNode, endNode)) {   
  38.             System.err.println("no this border!!!");   
  39.             return false;   
  40.         }   
  41.         nodeMatrix[startNode][endNode] = 0;   
  42.         return true;   
  43.     }   
  44. }  

2. adjacent table/vector

good for space, bad for border scan

java 代码
  1. import java.util.Vector;   
  2. public class GraphTable {   
  3.   
  4.     class Node {   
  5.         Vector adjacentNodes =  new Vector();   
  6.         public void add(Node node) {   
  7.             if (!hasNode(node)) {   
  8.                 adjacentNodes.add(node);   
  9.             }   
  10.         }   
  11.            
  12.         public boolean hasNode(Node node) {   
  13.             return adjacentNodes.contains(node);   
  14.         }   
  15.            
  16.         public void delete(Node node) {   
  17.             if (hasNode(node)) {   
  18.                 adjacentNodes.remove(node);   
  19.             }   
  20.         }   
  21.     }   
  22.     private Node[] nodeTable;   
  23.     private int tableSize;   
  24.        
  25.     public GraphTable(int tableSize) {   
  26.         this.tableSize = tableSize;   
  27.         nodeTable = new Node[tableSize];   
  28.         init();   
  29.     }   
  30.        
  31.     private void init() {   
  32.         for (int i=0; i
  33.             nodeTable[i] = new Node();   
  34.         }   
  35.     }   
  36.        
  37.     public void addBorder(int fromNode, int desNode) {   
  38.         nodeTable[desNode].add(nodeTable[fromNode]);   
  39.     }   
  40.        
  41.     public void deleteBorder(int desNode, int deleteNode) {   
  42.         nodeTable[desNode].delete(nodeTable[deleteNode]);   
  43.     }   
  44.        
  45.     public boolean hasBorder(int fromNode, int toNode) {   
  46.         return nodeTable[fromNode].hasNode(nodeTable[toNode]);   
  47.     }   
  48. }   

3. incident matrix

n/a

分享到：
| Functional Programming For The Rest of U ...
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics