rambo

图论（一）图的邻接表存储

2015年5月31日 BLOG, Data Strcuture 0 Comments

图(graph) G=(V,E)是由顶点(vertex)的集合V和边(edge，也称弧(arc))的集合E组成的。每一条边就是一个点对(v,w)。如果点对是有序的，则称为有向图(digraph)。顶点v和w邻接(adjacent)当且仅当(v,w)\in E。

wuxiang

邻接矩阵：用二维数组表示，对于每条边(v,w)，置A[v][w]=true，否则数组的项为false。如果边有一个权，则可以置A[v][w]为该权。而使用一个很大或者很小的权作为标记表示不存在的边。空间需求为\Theta(\lvert V \rvert^{2})。如果图的边不是很多，那么这种表示方法代价比较大。若图是稠密的(dense)，\lvert E \rvert=\Theta(\lvert V \rvert^{2})，则邻接矩阵是合适的表示方法。

邻接链表：一般的应用中，边的条数\lvert E \rvert远远小于\lvert V \rvert^{2}，称为稀疏图，这种情况下可以使用邻接链表。对于每一个顶点，使用一个表存放所有邻接的顶点VexNode<ArcType, VexType> *VexTable;，每个结点有一条链表。所需的空间需求为\Theta(\lvert V \rvert)+\Theta(\lvert E \rvert)。对于有向图来说，对于边(v,w)，结点w将出现在链表Vextable[v]中，所有邻接链表的长度之和等于\lvert E \rvert 。对于无向图来说，对于边(v,w)，结点w将出现在链表Vextable[v]中，结点v将出现在链表Vextable[w]中，所有邻接链表的长度之和等于2\lvert E \rvert 。

邻接链表的C++实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include "stdafx.h"
#include <iostream>
using namespace std;
 
const int MaxVexs = 20;//最大顶点数
 
template <typename ArcType, typename VexType> class Graph;
template <typename ArcType, typename VexType> class VexNode;
 
//邻接表中表对应的链表的弧类
template<typename ArcType>
class ArcNode{
template<typename Type1, typename Type2> friend class VexNode;
template<typename Type1, typename Type2>friend class Graph;
private:
int adjvex;//邻结点序号,该边所指向的顶点的位置
ArcType weight;//权值
ArcNode* nextarc;//指向下一条弧的指针
ArcNode() :nextarc(NULL){}
ArcNode(int v, const ArcType&w) :adjvex(v), weight(w), nextarc(NULL){  }
};
 
//邻接表中头结点
template<typename ArcType,typename VexType>
class VexNode{
friend class Graph<ArcType,VexType>;
private:
VexType data;          //顶点名
ArcNode<ArcType> *firstarc; //指向第一条依附该顶点的弧
VexNode() :firstarc(NULL){}
};
 
//邻接表图
template <typename ArcType, typename VexType>
class Graph{
private:
VexNode<ArcType, VexType> *VexTable;//使用一个表存放所有邻接的顶点，实际上是一个数组
int currentNumVexs;//图的顶点的数目
int currentNumArcs;//图的边的数目
public:
Graph() :VexTable(NULL), currentNumArcs(0), currentNumVexs(0){}
Graph(VexType *v, int num = MaxVexs);
~Graph();
bool empty(){ return currentNumVexs == 0; }
int GetNumVexs(){ return currentNumVexs; }
int GetNumArcs(){ return currentNumArcs; }
 
bool GetVexValue(VexType& result, int v);
bool GetWeight(ArcType& result, int v1, int v2);
int GetAdjvexPosition(int v);
int GetNextAdjvexPosition(int v, int w);
bool InsertVex(const VexType&p);
bool InsertArc(const ArcType&weight, int v, int w);
void Show();
 
};
 
template <typename ArcType, typename VexType>
Graph<ArcType, VexType>::Graph(VexType *v, int num){
currentNumVexs = 0;
currentNumArcs = 0;
 
VexTable = new VexNode<ArcType, VexType>[num];
for (int i = 0; i != num; ++i)
InsertVex(v[i]);
}
 
template <typename ArcType, typename VexType>
bool Graph<ArcType, VexType>::InsertVex(const VexType& vex){
if (currentNumVexs >= MaxVexs){
cerr << "Exceed max vex limit!" << endl;
return false;
}
 
VexTable[currentNumVexs].data = vex;
VexTable[currentNumVexs].firstarc = NULL;
++currentNumVexs;
return true;
}
 
 
/// <summary>  </summary>
/// <param name="weight">弧对应的权重</param>
/// <param name="v1">顶点</param>
/// <param name="v2">邻接点</param>
template <typename ArcType, typename VexType>
bool Graph<ArcType, VexType>::InsertArc(const ArcType&weight, int v1, int v2){
ArcNode<ArcType>*p, *q;
if (v1 >= 0 && v1 < currentNumVexs&&v2 >= 0 && v2 < currentNumVexs){
p = q = VexTable[v1].firstarc;
if (p == NULL){
VexTable[v1].firstarc = new ArcNode<ArcType>(v2, weight);
return true;
}
while (p != NULL){
if (p->adjvex == v2){
cerr << "Arc exists,cannot insert!" << endl;
return false;
}
q = p;
p = p->nextarc;//找到尾结点
}
if (q->nextarc == NULL){
//等同于VexTable[v1].firstarc->nextarc=new ArcNode<ArcType>(v2, weight);
q->nextarc = new ArcNode<ArcType>(v2, weight);
}
return true;
}
return false;
}
 
template <typename ArcType, typename VexType>
Graph<ArcType, VexType>::~Graph(){
ArcNode<ArcType>*p;
for (int i = 0; i < currentNumVexs; ++i){
p = VexTable[i].firstarc;
while (p != NULL){
VexTable[i].firstarc = p->nextarc;
delete p;
p = VexTable[i].firstarc;
}
}
delete[]VexTable;
}
 
template <typename ArcType, typename VexType>
void Graph<ArcType, VexType>::Show(){
ArcNode<ArcType>*p;
for (int i = 0; i < currentNumVexs; ++i){
p = VexTable[i].firstarc;
cout << "[" << i << ":" << VexTable[i].data << "]";
while (p != NULL){
cout << "--" << p->weight << "-->" << "[" << p->adjvex << "]";
p = p->nextarc;
}
cout << endl;
}
}
 
int _tmain(int argc, _TCHAR* argv[])
{
char vex[] = { 'A', 'B', 'C', 'D', 'E' };
int num = sizeof(vex) / sizeof(vex[0]);
 
Graph<double, char>g(vex, num);
 
g.InsertArc(0.1, 0, 1);
g.InsertArc(0.45, 1, 3);
g.InsertArc(0.03, 0, 4);
g.InsertArc(0.11, 0, 3);
        g.InsertArc(0.11, 0, 2);
g.InsertArc(0.44, 4, 2);
g.InsertArc(0.78, 4, 1);
g.InsertArc(0.92, 3, 2);
g.InsertArc(0.11, 3, 0);
g.InsertArc(0.03, 3, 4);
g.InsertArc(0.39, 2, 3);
        g.Show();
system("pause");
return 0;
}

guancha

SHow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/// <summary> 获取数组中对应顶点存储的值</summary>
template <typename ArcType, typename VexType>
bool Graph<ArcType, VexType>::GetVexValue(VexType& result, int v){
if (v >= 0 && v < currentNumVexs){
result = VexTable[v].data;
return true;
}
return false;
}
 
/// <summary> 获取（v,w）边的权值 </summary>
template <typename ArcType, typename VexType>
bool Graph<ArcType, VexType>::GetWeight(ArcType& result, int v, int w){
ArcNode<ArcType> *p;
if (v1 >= 0 && v1 < currentNumVexs&&v2 >= 0 && v2 < currentNumVexs){
p = VexTable[v].firstarc;
while (p != NULL){
if (p->adjvex == w){
result = p->weight;
return true;
}
p = p->nextarc;
}
}
return false;
}