图的邻接表实现
Adjacency List of the Graph
eryar@163.com
一、图的邻接表
邻接表(Adjacency List)是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边，对有向图是以顶点Vi为尾的弧。如下图所示的图用邻接表表示如下：
根据上图来定义用邻接表表示图的数据结构。当用邻接表来表示图时，图是由顶点序列组成的，在每个顶点中，记录下与该顶点相连的顶点在顶点序列中的位置。相关的数据结构如下所示：
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; }