数据结构学习(C++)之图（上）
图的应用恐怕是所有数据结构中最宽泛的了，但这也注定了在讲“数据结构的图”的时候没什么好讲的——关于图的最重要的是算法，而且相当的一部分都是很专业的，一般的人几乎不会接触到；相对而言，结构就显得分量很轻。你可以看到关于图中元素的操作很少，远没有单链表那里列出的一大堆“接口”。——一个结构如果复杂，那么能确切定义的操作就很有限。基本储存方法
不管怎么说，还是先得把图存起来。不要看书上列出了好多方法，根本只有一个——邻接矩阵。如果矩阵是稀疏的，那就可以用十字链表来储存矩阵（见前面的《稀疏矩阵（十字链表）》）。如果我们只关系行的关系，那么就是邻接表（出边表）；反之，只关心列的关系，就是逆邻接表（入边表）。
下面给出两种储存方法的实现。
#ifndef Graphmem_H
#define Graphmem_H
#include <vector>
#include <list>
using namespace std;
template <class name, class dist, class mem> class Network;
const int maxV = 20;//最大节点数
template <class name, class dist>
class AdjMatrix
{
friend class Network<name, dist, AdjMatrix<name, dist> >;
public:
AdjMatrix() : vNum(0), eNum(0)
{
vertex = new name[maxV]; edge = new dist*[maxV];
for (int i = 0; i < maxV; i++) edge[i] = new dist[maxV];
}
~AdjMatrix()
{
for (int i = 0; i < maxV; i++) delete []edge[i];
delete []edge; delete []vertex;
}
bool insertV(name v)
{
if (find(v)) return false;
vertex[vNum] = v;
for (int i = 0; i < maxV; i++) edge[vNum][i] = NoEdge;
vNum++; return true;
}
bool insertE(name v1, name v2, dist cost)
{
int i, j;
if (v1 == v2 || !find(v1, i) || !find(v2, j)) return false;
if (edge[i][j] != NoEdge) return false;
edge[i][j] = cost; eNum++; return true;
}
name& getV(int n) { return vertex[n]; } //没有越界检查
int nextV(int m, int n)//返回m号顶点的第n号顶点后第一个邻接顶点号，无返回-1
{
for (int i = n + 1; i < vNum; i++) if (edge[m][i] != NoEdge) return i;
return -1;
}
private:
int vNum, eNum;
dist NoEdge, **edge; name *vertex;
bool find(const name& v)
{
for (int i = 0; i < vNum; i++) if (v == vertex[i]) return true;
return false;
}
bool find(const name& v, int& i)
{
for (i = 0; i < vNum; i++) if (v == vertex[i]) return true;
return false;
}
};
template <class name, class dist>
class LinkedList
{
friend class Network<name, dist, LinkedList<name, dist> >;
public:
LinkedList() : vNum(0), eNum(0) {}
~LinkedList()
{
for (int i = 0; i < vNum; i++) delete vertices[i].e;
}
bool insertV(name v)
{
if (find(v)) return false;
vertices.push_back(vertex(v, new list<edge>));
vNum++; return true;
}
bool insertE(const name& v1, const name& v2, const dist& cost)
{
int i, j;
if (v1 == v2 || !find(v1, i) || !find(v2, j)) return false;
for (list<edge>::iterator iter = vertices[i].e->begin();
iter != vertices[i].e->end() && iter->vID < j; iter++);
if (iter == vertices[i].e->end())
{
vertices[i].e->push_back(edge(j, cost)); eNum++; return true;
}
if (iter->vID == j) return false;
vertices[i].e->insert(iter, edge(j, cost)); eNum++; return true;
}
name& getV(int n) { return vertices[n].v; } //没有越界检查
int nextV(int m, int n)//返回m号顶点的第n号顶点后第一个邻接顶点号，无返回-1
{
for (list<edge>::iterator iter = vertices[m].e->begin();
iter != vertices[m].e->end(); iter++) if (iter->vID > n) return iter->vID;
return -1;
}
private:
bool find(const name& v)
{
for (int i = 0; i < vNum; i++) if (v == vertices[i].v) return true;
return false;
}
bool find(const name& v, int& i)
{
for (i = 0; i < vNum; i++) if (v == vertices[i].v) return true;
return false;
}
struct edge
{
edge() {}
edge(int vID, dist cost) : vID(vID), cost(cost) {}
int vID;
dist cost;
};
struct vertex
{
vertex() {}
vertex(name v, list<edge>* e) : v(v), e(e) {}
name v;
list<edge>* e;
};
int vNum, eNum;
vector<vertex> vertices;
};
#endif
这个实现是很简陋的，但应该能满足后面的讲解了。现在这个还什么都不能做，不要急，在下篇将讲述图的DFS和BFS。 DFS和BFS
对于非线性的结构，遍历都会首先成为一个问题。和二叉树的遍历一样，图也有深度优先搜索（DFS）和广度优先搜索（BFS）两种。不同的是，图中每个顶点没有了祖先和子孙的关系，因此，前序、中序、后序不再有意义了。仿照二叉树的遍历，很容易就能完成DFS和BFS，只是要注意图中可能有回路，因此，必须对访问过的顶点做标记。
最基本的有向带权网
#ifndef Graph_H
#define Graph_H
#include <iostream>
#include <queue>
using namespace std;
#include "Graphmem.h"
template <class name, class dist, class mem>
class Network
{
public:
Network() {}
Network(dist maxdist) { data.NoEdge = maxdist; }
~Network() {}
bool insertV(name v) { return data.insertV(v); }
bool insertE(name v1, name v2, dist cost) { return data.insertE(v1, v2, cost); }
name& getV(int n) { return data.getV(n); }
int nextV(int m, int n = -1) { return data.nextV(m, n); }
int vNum() { return data.vNum; }
int eNum() { return data.eNum; }
protected:
bool* visited;
static void print(name v) { cout << v; }
private:
mem data;
};
#endif
你可以看到，这是在以mem方式储存的data上面加了一层外壳。在图这里，逻辑上分有向、无向，带权、不带权；储存结构上有邻接矩阵和邻接表。也就是说分开来有8个类。为了最大限度的复用代码，继承关系就非常复杂了。但是，多重继承是件很讨厌的事，什么覆盖啊，还有什么虚拟继承，我可不想花大量篇幅讲语言特性。于是，我将储存方式作为第三个模板参数，这样一来就省得涉及虚拟继承了，只是这样一来这个Network的实例化就很麻烦了，不过这可以通过typedef或者外壳类来解决，我就不写了。反正只是为了让大家明白，真正要用的时候，最好是写专门的类，比如无向无权邻接矩阵图，不要搞的继承关系乱七八糟。
DFS和BFS的实现
public:
void DFS(void(*visit)(name v) = print)
{
visited = new bool[vNum()];
for (int i = 0; i < vNum(); i++) visited[i] = false;
DFS(0, visit);
delete []visited;
}
protected:
void DFS(int i, void(*visit)(name v) = print)
{
visit(getV(i)); visited[i] = true;
for (int n = nextV(i); n != -1; n = nextV(i, n))
if (!visited[n]) DFS(n, visit);
}
public:
void BFS(int i = 0, void(*visit)(name v) = print)//n没有越界检查
{
visited = new bool[vNum()]; queue<int> a; int n;
for (n = 0; n < vNum(); n++) visited[n] = false;
visited[i] = true;
while (i != -1)//这个判断可能是无用的
{
visit(getV(i));
for (n = nextV(i); n != -1; n = nextV(i, n))
if (!visited[n]) { a.push(n); visited[n] = true; }
if (a.empty()) break;
i = a.front(); a.pop();
}
delete []visited;
}
DFS和BFS函数很难写得像树的遍历方法那么通用，这在后面就会看到，虽然我们使用了DFS和BFS的思想，但是上面的函数却不能直接使用。因为树的信息主要在节点上，而图的边上还有信息。
测试程序
#include <iostream>
using namespace std;
#include "Graph.h"
int main()
{
Network<char, int, LinkedList<char, int> > a;
a.insertV('A'); a.insertV('B');
a.insertV('C'); a.insertV('D');
a.insertE('A', 'B', 1); a.insertE('A', 'C', 2);
a.insertE('B', 'D', 3);
cout << "DFS: "; a.DFS(); cout << endl;
cout << "BFS: "; a.BFS(); cout << endl;
return 0;
}
老实说，这个类用起来真的不是很方便。不过能说明问题就好。 无向图
要是在纸上随便画画，或者只是对图做点示范性的说明，大多数人都会选择无向图。然而在计算机中，无向图却是按照有向图的方法来储存的——存两条有向边。实际上，当我们说到无向的时候，只是忽略方向——在纸上画一条线，难不成那线“嗖”的就出现了，不是从一头到另一头画出来的？ 无向图有几个特有的概念，连通分量、关节点、最小生成树。下面将分别介绍，在此之前，先完成无向图类的基本操作。
无向图类
template <class name, class dist, class mem>
class Graph : public Network<name, dist, mem>
{
public:
Graph() {}
Graph(dist maxdist) : Network<name, dist, mem> (maxdist) {}
bool insertE(name v1, name v2, dist cost)
{
if (Network<name, dist, mem>::insertE(v1, v2, cost))
return Network<name, dist, mem>::insertE(v2, v1, cost);
return false;
}
};
仅仅是添加边的时候，再添加一条反向边，很简单。
连通分量
这是无向图特有的，有向图可要复杂多了（强、单、弱连通），原因就是无向图的边怎么走都行，有向图的边好像掉下无底深渊就再也爬不上来了。有了DFS，求连通分量的算法就变得非常简单了——对每个没有访问的顶点调用DFS就可以了。
void components()
{
visited = new bool[vNum()]; int i, j = 0;
for (i = 0; i < vNum(); i++) visited[i] = false;
cout << "Components:" << endl;
for (i = 0; i < vNum(); i++)
{
if (!visited[i]) { cout << '(' << ++j << ')'; DFS(i); cout << endl; }
}
delete []visited;
}
关节点
下定义是人们认识事物的一个方法，因为概念使得人们能够区分事物——关于这个还有个绝对的运动和相对的静止的哲学观点（河水总在流，但是长江还叫长江，记得那个著名的“不可能踏进同一条河里”吗？）因此，能否有个准确的概念往往是一门学科发展程度的标志，而能否下一个准确的定义反映了一个人的思维能力。说这么多废话，原因只有一个，我没搞清楚什么叫“关节点”——参考书有限，不能仔细的考究了，如有误解，还望指正。
严版是这么说的：如果删除某个顶点，将图的一个连通分量分割成两个或两个以上的连通分量，称该顶点为关节点。——虽然没有提到图必须是无向的，但是提到了连通分量已经默认是无向图了。
殷版是这么说的：在一个无向连通图中，……（余下同严版）。
问题出来了，非连通图是否可以讨论含有关节点？我们是否可以说某个连通分量中含有关节点？遗憾的是，严版留下这个问题之后，在后面给出的算法是按照连通图给的，这样当图非连通时结果就是错的。殷版更是滑头，只输出重连通分量，不输出关节点，自己虽然假定图是连通的，同样没有连通判断。
翻翻离散数学吧，结果没找到什么“关节点”，只有“割点”，是这样的：一个无向连通图，如果删除某个顶点后，变为非连通图，该顶点称为割点。权当“割点”就是“关节点”，那么算法至少也要先判断是否连通吧？可是书上都直接当连通的了……
关于算法不再细说，书上都有。下面的示例，能输出每个连通分量的“关节点”（是不是可以这样叫，我也不清楚）。dfn储存的是每个顶点的访问序号，low是深度优先生成树上每个非叶子顶点的子女通过回边所能到达的顶点最小的访问序号。把指向双亲的边也当成回边并不影响判断，因此不必特意区分，殷版显式区分了，属于画蛇添足。这样一来，if (low[n] >= dfn[i]) cout << getV(i);这个输出关节点的判断中的>=就显得很尴尬了，因为只能等于不可能大于。还要注意的是，生成树的根（DFS的起始点）是单独判断的。
void articul()
{
dfn = new int[vNum()]; low = new int[vNum()]; int i, j = 0, n;
for(i = 0; i < vNum(); i++) dfn[i] = low[i] = 0;//初始化
for (i = 0; i < vNum(); i++)
{
if (!dfn[i])
{
cout << '(' << ++j << ')'; dfn[i] = low[i] = count = 1;
if ((n = nextV(i)) != -1) articul(n); bool out = false;//访问树根
while ((n = nextV(i, n)) != -1)
{
if (dfn[n]) continue;
if (!out) { cout << getV(i); out = true; }//树根有不只一个子女
articul(n);//访问其他子女
}
cout << endl;
}
}
delete []dfn; delete []low;
}
private:
void articul(int i)
{
dfn[i] = low[i] = ++count;
for (int n = nextV(i); n != -1; n = nextV(i, n))
{
if (!dfn[n])
{
articul(n);
if (low[n] < low[i]) low[i] = low[n];
if (low[n] >= dfn[i]) cout << getV(i);//这里只可能＝
}
else if (dfn[n] < low[i]) low[i] = dfn[n];//回边判断
}
}
int *dfn, *low, count;
没有完，请看下。
页:
[1]