數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(20) --圖的存儲結(jié)構(gòu)
來源：程序員人生 發(fā)布時間：2015-01-20 08:25:45 閱讀次數(shù)：4336次
圖的結(jié)構(gòu)定義
圖是由1個頂點集 V 和1個弧集 E構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。
Graph = (V , E )
其中，E ＝ {<v,w>| v,w∈V 且 P(v,w)} <v,w>表示從 v 到 w 的1條弧，并稱 v 為弧尾，w 為弧頭。謂詞 P(v,w) 定義了弧 <v,w>的意義或信息。
由頂點集和邊集構(gòu)成的圖稱作無向圖。
如果”弧”是有方向的，則稱由頂點集和弧集構(gòu)成的圖為有向圖。
鄰接矩陣 
定義:矩陣的元素為
有向圖的鄰接矩陣為非對稱矩陣, 而無向圖的鄰接矩陣為對稱矩陣;
//無向圖的鄰接矩陣
const int MAX_VERTS = 20;
//頂點
template <typename Type>
class Vertex
{
public:
Vertex(const Type &_node = Type())
: node(_node) {}
private:
Type node;
};
//圖
template <typename Type>
class Graph
{
public:
Graph();
~Graph();
void addVertex(const Type &vertex);
void addEdge(int start, int end);
void printMatrix();
private:
Vertex<Type>* vertexList[MAX_VERTS];
int nVerts;
int adjMatrix[MAX_VERTS][MAX_VERTS];
};
template <typename Type>
Graph<Type>::Graph():nVerts(0)
{
for (int i = 0; i < MAX_VERTS; ++i)
for (int j = 0; j < MAX_VERTS; ++j)
adjMatrix[i][j] = 0;
}
template <typename Type>
Graph<Type>::~Graph()
{
for (int i = 0; i < nVerts; ++i)
delete vertexList[i];
}
template <typename Type>
void Graph<Type>::addVertex(const Type &vertex)
{
vertexList[nVerts ++] = new Vertex<Type>(vertex);
}
template <typename Type>
void Graph<Type>::addEdge(int start, int end)
{
//無向圖
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
template <typename Type>
void Graph<Type>::printMatrix()
{
for (int i = 0; i < nVerts; ++i)
{
for (int j = 0; j < nVerts; ++j)
cout << adjMatrix[i][j] << ' ';
cout << endl;
}
}
//測試代碼
int main()
{
Graph<char> g;
g.addVertex('A'); //0
g.addVertex('B'); //1
g.addVertex('C'); //2
g.addVertex('D'); //3
g.addVertex('E'); //4
g.addEdge(0, 1); //A-B
g.addEdge(0, 3); //A-D
g.addEdge(1, 0); //B-A
g.addEdge(1, 4); //B-E
g.addEdge(2, 4); //C-E
g.addEdge(3, 0); //D-A
g.addEdge(3, 4); //D-E
g.addEdge(4, 1); //E-B
g.addEdge(4, 2); //E-C
g.addEdge(4, 3); //E-D
g.printMatrix();
return 0;
}
鄰接表
注意:在有向圖的鄰接表中不容易找到指向該頂點的弧。
//無向圖的鄰接表
template <typename Type>
class Graph
{
public:
Graph(int _size = 10);
~Graph();
void addVertex(const Type &vertex);
void addEdge(int start, int end);
void printVertex();
void printAdjList();
private:
Type *vertexList;
list<int> *headNode;
int size;
int nVertex;
};
template <typename Type>
Graph<Type>::Graph(int _size):size(_size), nVertex(0)
{
vertexList = new Type[size];
headNode = new list<int>[size];
}
template <typename Type>
Graph<Type>::~Graph()
{
delete []vertexList;
delete []headNode;
}
template <typename Type>
void Graph<Type>::addVertex(const Type &vertex)
{
vertexList[nVertex ++] = vertex;
}
template <typename Type>
void Graph<Type>::addEdge(int start, int end)
{
headNode[start].push_back(end);
}
template <typename Type>
void Graph<Type>::printVertex()
{
cout << vertexList[0];
for (int i = 1; i < nVertex; ++i)
cout << ' ' << vertexList[i];
cout << endl;
}
template <typename Type>
void Graph<Type>::printAdjList()
{
for (int i = 0; i < nVertex; ++i)
{
cout << i;
for (list<int>::iterator iter = headNode[i].begin();
iter != headNode[i].end();
++iter)
cout << " -> " << *iter;
cout << endl;
}
}
//測試代碼
int main()
{
Graph<char> g;
g.addVertex('A'); //0
g.addVertex('B'); //1
g.addVertex('C'); //2
g.addVertex('D'); //3
g.addVertex('E'); //4
g.printVertex();
g.addEdge(0, 1); //A-B
g.addEdge(0, 3); //A-D
g.addEdge(1, 0); //B-A
g.addEdge(1, 4); //B-E
g.addEdge(2, 4); //C-E
g.addEdge(3, 0); //D-A
g.addEdge(3, 4); //D-E
g.addEdge(4, 1); //E-B
g.addEdge(4, 2); //E-C
g.addEdge(4, 3); //E-D
g.printAdjList();
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
