图的邻接表实现 Adjacency List of the Graph

简介: 图的邻接表实现 Adjacency List of the Graph eryar@163.com 一、图的邻接表   邻接表(Adjacency List)是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边,对有向图是以顶点Vi为尾的弧。

图的邻接表实现

Adjacency List of the Graph

eryar@163.com

一、图的邻接表

  邻接表(Adjacency List)是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边,对有向图是以顶点Vi为尾的弧。如下图所示的图用邻接表表示如下:

image   image

根据上图来定义用邻接表表示图的数据结构。当用邻接表来表示图时,图是由顶点序列组成的,在每个顶点中,记录下与该顶点相连的顶点在顶点序列中的位置。相关的数据结构如下所示:

   1:  struct SVertexNode
   2:  {
   3:      string        data;
   4:      vector<int> vecLoc;
   5:  };
   6:   
   7:  typedef struct SEdge
   8:  {
   9:      int iInitialNode;
  10:   
  11:      int iTerminalNode;
  12:   
  13:  }Edge;
  14:   
  15:  typedef struct Graph
  16:  {
  17:      int iVertexNum;
  18:      int iEdgeNum;
  19:      vector<SVertexNode> vecVertex;
  20:  }Graph;
 
二、C++实现

 

.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; }

用C++实现上图所示的图,代码如下:

   1:  //------------------------------------------------------------------------------
   2:  //    Copyright (c) 2012 eryar All Rights Reserved.
   3:  //
   4:  //        File    : Main.cpp
   5:  //        Author  : eryar@163.com
   6:  //        Date    : 2012-8-25 17:11
   7:  //        Version : 0.1v
   8:  //
   9:  //    Description : Use Adjacency List data structure to store Digraph.
  10:  //
  11:  //==============================================================================
  12:   
  13:  #include <vector>
  14:  #include <string>
  15:  #include <iostream>
  16:  using namespace std;
  17:   
  18:  struct SVertexNode
  19:  {
  20:      string        data;
  21:      vector<int> vecLoc;
  22:  };
  23:   
  24:  typedef struct SEdge
  25:  {
  26:      int iInitialNode;
  27:   
  28:      int iTerminalNode;
  29:   
  30:  }Edge;
  31:   
  32:  typedef struct Graph
  33:  {
  34:      int iVertexNum;
  35:      int iEdgeNum;
  36:      vector<SVertexNode> vecVertex;
  37:  }Graph;
  38:   
  39:  ///////////////////////////////////////////////////////////////////////////////
  40:  // Functions of Graph
  41:  void    Initialize(Graph& g, int v);
  42:  Edge    MakeEdge(int v, int w);
  43:  void    InsertEdge(Graph& g, const Edge& e);
  44:  void    ShowGraph(const Graph& g);
  45:   
  46:  ///////////////////////////////////////////////////////////////////////////////
  47:  // Main function.
  48:   
  49:  int main(int agrc, char* argv[])
  50:  {
  51:      Graph   aGraph;
  52:   
  53:      // Initialize the graph.
  54:      Initialize(aGraph, 4);
  55:   
  56:      // Insert some edges to make graph.
  57:      InsertEdge(aGraph, MakeEdge(0, 1));
  58:      InsertEdge(aGraph, MakeEdge(0, 2));
  59:      InsertEdge(aGraph, MakeEdge(2, 3));
  60:      InsertEdge(aGraph, MakeEdge(3, 0));
  61:   
  62:      // Show the graph.
  63:      ShowGraph(aGraph);
  64:   
  65:      return 0;
  66:  }
  67:   
  68:  ///////////////////////////////////////////////////////////////////////////////
  69:   
  70:  /**
  71:  * brief    Initialize the graph.
  72:  *
  73:  *       v: vertex number of the graph.
  74:  */
  75:  void Initialize( Graph& g, int v )
  76:  {
  77:      char    szData[6];
  78:      SVertexNode node;
  79:   
  80:      g.iVertexNum    = v;
  81:      g.iEdgeNum      = 0;
  82:   
  83:      for (int i = 0; i < v; i++)
  84:      {
  85:          sprintf(szData, "V%d", i+1);
  86:          node.data   = szData;
  87:          g.vecVertex.push_back(node);
  88:      }
  89:  }
  90:   
  91:  /**
  92:  * brief    Make an edge by initial node and terminal node.
  93:  */
  94:  Edge MakeEdge( int v, int w )
  95:  {
  96:      Edge    e;
  97:   
  98:      e.iInitialNode  = v;
  99:      e.iTerminalNode = w;
 100:   
 101:      return e;
 102:  }
 103:   
 104:  /**
 105:  * brief    Insert an edge to the graph.
 106:  */
 107:  void InsertEdge( Graph& g, const Edge& e )
 108:  {
 109:      g.vecVertex.at(e.iInitialNode).vecLoc.push_back(e.iTerminalNode);
 110:   
 111:      // If the graph is Undigraph, need do something here...
 112:      //g.vecVertex.at(e.iTerminalNode).vecLoc.push_back(e.iInitialNode);
 113:   
 114:      g.iEdgeNum++;
 115:  }
 116:   
 117:  /**
 118:  * brief    Show the graph.
 119:  */
 120:  void ShowGraph( const Graph& g )
 121:  {
 122:      for (int i = 0; i < g.iVertexNum; i++)
 123:      {
 124:          cout<<"Node "<<i<<"("<<g.vecVertex.at(i).data<<")";
 125:   
 126:          for (int j = 0; j < g.vecVertex.at(i).vecLoc.size(); j++)
 127:          {
 128:              cout<<"->"<<g.vecVertex.at(i).vecLoc.at(j);
 129:          }
 130:   
 131:          cout<<endl;
 132:      }
 133:  }
 
三、输出结果
   1:  Node 0(V1)->1->2
   2:  Node 1(V2)
   3:  Node 2(V3)->3
   4:  Node 3(V4)->0
   5:  Press any key to continue
.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; }
目录
相关文章
|
存储 关系型数据库 MySQL
【MySQL疑难杂症】如何将树形结构存储在数据库中(方案一 Adjacency List)
  今天来看看一个比较头疼的问题,如何在数据库中存储树形结构呢?   像mysql这样的关系型数据库,比较适合存储一些类似表格的扁平化数据,但是遇到像树形结构这样有深度的人,就很难驾驭了。   举个栗子:现在有一个要存储一下公司的人员结构,大致层次结构如下:     (画个图真不容易。
1202 0
|
18天前
|
安全 Java
java线程之List集合并发安全问题及解决方案
java线程之List集合并发安全问题及解决方案
18 1
|
12天前
|
存储 安全 Java
详解Java中集合的List接口实现的ArrayList方法 | Set接口实现的HashSet方法
详解Java中集合的List接口实现的ArrayList方法 | Set接口实现的HashSet方法
|
24天前
|
Java API
使用 Java 来实现两个 List 的差集操作
使用 Java 来实现两个 List 的差集操作
20 3
|
4天前
|
存储 Java 索引
Java List接口实现原理与性能评估
Java List接口实现原理与性能评估
|
26天前
|
安全 Java 索引
Java List:从入门到精通,一篇文章就够了!
【6月更文挑战第17天】Java List是有序元素集合,支持索引访问、添加、删除和修改。从ArrayList、LinkedList到Vector,各种实现满足不同场景需求。使用add()添加元素,get()获取,set()修改,remove()删除。遍历可用for-each或Iterator,subList()创建子集。注意线程安全,可选synchronizedList()、Vector或CopyOnWriteArrayList。理解List的基本操作和特性,能提升编程效率。
|
26天前
|
存储 Java 索引
告别Java集合小白!一文读懂List的精髓
【6月更文挑战第17天】Java中的List接口作为有序集合,允许存储和操作有序元素,支持重复值。ArrayList和LinkedList是常见实现类:ArrayList基于数组,适合快速访问但插入删除慢;LinkedList基于链表,插入删除快但访问慢。了解其核心概念、方法及泛型使用,能提升编程效率和代码质量。示例代码展示了添加和访问元素。通过深入学习,可以更好地掌握List的高级用法。
|
11天前
|
存储 缓存 安全
Java List操作详解及常用方法
Java List操作详解及常用方法
|
11天前
|
存储 Java 索引
Java List接口实现原理与性能评估
Java List接口实现原理与性能评估