eryar

PipeCAD - Plant Piping Design Software.
RvmTranslator - Translate AVEVA RVM to OBJ, glTF, etc.
posts - 603, comments - 590, trackbacks - 0, articles - 0

图的邻接表实现

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; }

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理