鄰接表(Adjacency List)是圖的一種鏈式存儲結構。在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結點表示依附于頂點Vi的邊，對有向圖是以頂點Vi為尾的弧。如下圖所示的圖用鄰接表表示如下：
根據上圖來定義用鄰接表表示圖的數據結構。當用鄰接表來表示圖時，圖是由頂點序列組成的，在每個頂點中，記錄下與該頂點相連的頂點在頂點序列中的位置。相關的數據結構如下所示：
.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; }
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: }
.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; }