`

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 ...
评论
发表评论

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

相关推荐

    Data.Structures.and.Algorithms.USING.C

    GRAPH DATA STRUCTURE 27. Graphs 28. Depth First Traversal 29. Breadth First Traversal TREE DATA STRUCTURE 30. Tree 31. Tree Traversal 32. Binary Search Tree 33. AVL Trees 34. Spanning Tree 35. Heaps ...

    graph-data-structure:具有拓扑排序和最短路径算法的图数据结构

    图数据结构 具有。 该库提供了有向图数据结构的... var Graph = require ( "graph-data-structure" ) ; 例子 美国广播公司 要创建图实例，请调用Graph作为构造函数。 var graph = Graph ( ) ; 使用addNode和addE

    Learning GraphQL: Declarative Data Fetching for Modern Web Apps

    You’ll explore graph theory, the graph data structure, and GraphQL types before learning hands-on how to build a schema for a photo-sharing application. This book also introduces you to Apollo Client...

    Learning GraphQL--2018

    You’ll explore graph theory, the graph data structure, and GraphQL types before learning hands-on how to build a schema for a photo-sharing application. This book also introduces you to Apollo Client...

    Data Structure Visualizations.zip

    "Data Structure Visualizations.zip" 文件提供了一个离线版的数据结构可视化学习资源，让你无需网络连接即可在本地探索和理解各种数据结构。 1. **数组（Array）**：数组是最基础的数据结构，它将元素按照特定顺序...

    3d-force-graph.rar

    A web component to represent a graph data structure in a 3-dimensional space using a force-directed iterative layout. Uses ThreeJS/WebGL for 3D rendering and either d3-force-3d or ngraph for the ...

    数据结构常用算法c++实现

    Graph data structure Strongly Connected Components(SCC) Prim's minimum spanning tree Kruskal MST Directed/Undirected graph ops Breadth First Search Depth First Search Dijkstra's algorithm Bellman-Ford...

    图ADT_seeingf6u_图ADT_

    在IT领域，图数据结构（Graph Data Structure）是一种非常重要的抽象数据类型（ADT，Abstract Data Type）。图是由节点（也称为顶点）和边组成的集合，用于表示对象之间的关系。在C语言中实现图的ADT可以帮助我们...

    Python-Implementation-of-Algorithms-and-Data-Structures-and-Leetcode-Solutions:算法和数据结构

    在Python-Implementation-of-Algorithms-and-Data-Structures-and-Leetcode-Solutions-master这个项目中，你可以找到作者对这些算法和数据结构的实际代码实现，这对于学习和实践是非常宝贵的资源。通过阅读和理解...

    Data Structure Summary PDF 2pages include core elements

    Data Structure Summary: Time Complexity & Space Complexity O(1) O(n) O(log(n)) o(n log(n))... Data Structures Performance Sorting Algorithms Performance Graph Operations Performance Heap Operations ...

    A*， Astar算法实现，tiebreaker规则优化

    2. **图数据结构（Graph Data Structure）**：用于存储地图的信息，包括节点间的连接和代价。 3. **A*搜索算法（Astar Search）**：主要包含主循环，用于从开放列表中选择下一个节点，更新节点状态，并将相邻节点...

    metis安装包和manual手册.rar

    5.5 Graph data structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.6 Mesh data structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...

    刘知远-Introduction to Graph Neural Networks.pdf

    Graph neural networks (GNNs) are proposed to combine the feature information and the graph structure to learn better representations on graphs via feature propagation and aggregation. Due to its ...

    MANAGING AND MINING GRAPH DATA

    - **其他静态图模式**：如社团结构（community structure），指的是图中的节点倾向于形成密集连接的小群体。 - **动态图中的模式**：随着时间和环境的变化，图的结构也会发生变化，研究这些变化对于理解社会网络、...

    Data_Structure_with_Python-master.zip

    "Data_Structure_with_Python-master.zip"这个压缩包显然包含了关于如何使用Python实现各种数据结构和算法的教程或代码库。现在，我们将深入探讨这些核心概念。 数据结构是组织、存储和处理数据的方式。它们提供了...

    python-data-structure-cn python数据结构中文版

    Python数据结构中文版是针对想要深入理解数据结构的Python程序员所设计的一份宝贵资源。它以Python语言为载体，...阅读《python-data-structure-cn》这本书，将有助于读者更好地掌握这些概念，并将其应用到实际编程中。

    data-structure--Graph.zip_site:www.pudn.com

    在这个“data-structure--Graph.zip”压缩包中，我们可以期待找到关于图的各种算法和实现的代码示例。 图是由顶点（Vertex）和边（Edge）构成的非线性数据结构，可以用来表示对象之间的关系。在图中，顶点可以代表...

    Data Structures and Algorithm Analysis in C, Second Edition.ppt.rar

    数据结构与算法，C描述。第二版，英文讲义PPT。...chapter6 General trees，chapter7 Sorting，chapter8 Primary & Secondary Storage，Chapter-9 Search，chapter11 Graph，chapter13 Advanced Trees Structures

    Swift.Data.Structure.and.Algorithms

    Master the most common algorithms and data structures, and learn how to implement them ... Graph Algorithms Chapter 8. Performance and Algorithm Efficiency Chapter 9. Choosing the Perfect Algorithm

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