Graph-基本知识
Graph: 图。
图是由一些点V和一些边E组成的数据结构E。对于任一一条边(v, w)，v,w 都属于V。
图分有向图和无向图。比如这样：
graph
根据图的边是否带权重，我们还可以把图分为有权图和无权图。
图的存储
图的存储一般有两类：邻接矩阵和邻接表。邻接表用的比较多，因为比较节省空间。
下面分别是简单的抽象：
//
// Created on 3/22/18.
//
#ifndef AGORITHM_GRAPH_H
#define AGORITHM_GRAPH_H
#include <functional>
class Graph {
public:
static void test();
enum Kind {
UNDIRECTED = 0,
DIRECTED,
};
using VisitFunc = std::function<void(int)>;
struct Edge {
public:
Edge() : Edge(0, 0, 0) {}
Edge(int x, int y) : Edge(x, y, 0) {}
Edge(int x, int y, int w) {
this->x = x;
this->y = y;
this->weight = w;
}
int x = 0;
int y = 0;
int weight = 0;
};
class NodeIterator {
public:
virtual bool HasNext() = 0;
virtual Edge Next() = 0;
};
explicit Graph(Kind kind, int numberOfNodes);;
virtual ~Graph() = default;
Kind GetKind() const { return mKind; }
int GetNumberOfNodes() const { return mNumberOfNodes; }
virtual void AddEdge(int x, int y, int weight) = 0;
virtual void AddEdge(const Edge &e);
virtual void DFS(const VisitFunc &fn, int start) const = 0;
virtual void BFS(const VisitFunc &fn, int start) const = 0;
std::shared_ptr<NodeIterator> CreateSpIteratorForNode(int x) const;
virtual int GetWeightForEdge(int x, int y) const = 0;
protected:
virtual NodeIterator *CreateIteratorForNode(int x) const = 0;
private:
Kind mKind = UNDIRECTED;
int mNumberOfNodes = 0;
};
#endif //AGORITHM_GRAPH_H
邻接矩阵：
// .h
//
// Created on 3/22/18.
//
#ifndef AGORITHM_MATRIXGRAPH_H
#define AGORITHM_MATRIXGRAPH_H
#include <vector>
#include "Graph.h"
class MatrixGraph : public Graph {
public:
explicit MatrixGraph(Kind kind, int nNode = MAX_NODE);
static const int MAX_NODE = 100;
void AddEdge(int x, int y, int weight) override;
void DFS(const VisitFunc &fn, int start) const override;
void BFS(const VisitFunc &fn, int start) const override;
int GetWeightForEdge(int x, int y) const override;
protected:
NodeIterator *CreateIteratorForNode(int x) const override;
class MatrixNodeIterator : public NodeIterator {
public:
explicit MatrixNodeIterator(const MatrixGraph *graph, int x);
bool HasNext() override;
Edge Next() override;
private:
int next(int start);
private:
const MatrixGraph *mGraph = nullptr;
int mNodeX = 0;
int mCurrentX = 0;
};
protected:
virtual void doDfs(int x, std::vector<int> &vis, const VisitFunc &fn) const;
private:
std::vector<std::vector<int>> mMatrix;
};
#endif //AGORITHM_MATRIXGRAPH_H
// .cpp
//
// Created on 3/22/18.
//
#include <cassert>
#include <queue>
#include <string>
#include "MatrixGraph.h"
MatrixGraph::MatrixGraph(Graph::Kind kind, int nNode) : Graph(kind, nNode) {
assert(nNode > 0);
mMatrix.resize(nNode, std::vector<int>(nNode, 0));
}
void MatrixGraph::AddEdge(int x, int y, int weight) {
mMatrix[x][y] = weight;
if (GetKind() == UNDIRECTED) {
mMatrix[y][x] = weight;
}
}
void MatrixGraph::DFS(const VisitFunc &fn, int start) const {
int n = GetNumberOfNodes();
std::vector<int> vis(n, 0);
doDfs(start, vis, fn);
for (int i = 0; i < n; i++) { // remaining if any
doDfs(i, vis, fn);
}
}
void MatrixGraph::doDfs(int x, std::vector<int> &vis, const Graph::VisitFunc &fn) const {
if (!vis[x]) {
vis[x] = 1;
fn(x);
int n = GetNumberOfNodes();
for (int i = 0; i < n; i++) {
if (mMatrix[x][i] > 0) {
if (!vis[i]) {
doDfs(i, vis, fn);
}
}
}
}
}
void MatrixGraph::BFS(const VisitFunc &fn, int start) const {
int n = GetNumberOfNodes();
std::vector<int> vis(n, 0);
std::queue<int> queue;
auto run = [&](int i) {
if (!vis[i]) {
queue.push(i);
while (!queue.empty()) {
int x = queue.front();
queue.pop();
if (!vis[x]) {
vis[x] = 1;
fn(x);
for (int j = 0; j < n; j++) {
if (!vis[j]) {
queue.push(j);
}
}
}
}
}
};
run(start);
for (int i = 0; i < n; i++) { // remaining
run(i);
}
}
Graph::NodeIterator *MatrixGraph::CreateIteratorForNode(int x) const {
return new MatrixNodeIterator(this, x);
}
int MatrixGraph::GetWeightForEdge(int x, int y) const {
return mMatrix[x][y];
}
bool MatrixGraph::MatrixNodeIterator::HasNext() {
return mCurrentX < mGraph->GetNumberOfNodes();
}
Graph::Edge MatrixGraph::MatrixNodeIterator::Next() {
if (mCurrentX >= mGraph->GetNumberOfNodes()) {
throw std::range_error("mCurrentX: " + std::to_string(mCurrentX));
}
int oldX = mCurrentX;
mCurrentX = next(mCurrentX + 1);
return {mNodeX, oldX, mGraph->mMatrix[mNodeX][oldX]};
}
MatrixGraph::MatrixNodeIterator::MatrixNodeIterator(const MatrixGraph *graph, int x) {
mGraph = graph;
mNodeX = x;
mCurrentX = next(0);
}
int MatrixGraph::MatrixNodeIterator::next(int start) {
int i = start;
for (; i < mGraph->GetNumberOfNodes(); i++) {
if (mGraph->mMatrix[mNodeX][i]) {
break;
}
}
return i;
}
邻接表：
//.h
//
// Created on 3/22/18.
//
#ifndef AGORITHM_LISTGRAPH_H
#define AGORITHM_LISTGRAPH_H
#include <vector>
#include "Graph.h"
class ListGraph : public Graph {
public:
ListGraph(Kind kind, int numberOfNodes);
void AddEdge(int x, int y, int weight) override;
virtual void AddEdge(int x, int y, int weight, Kind kind, bool append);
void DFS(const VisitFunc &fn, int start) const override;
void BFS(const VisitFunc &fn, int start) const override;
int GetWeightForEdge(int x, int y) const override;
protected:
NodeIterator *CreateIteratorForNode(int x) const override;
struct ListEdge;
using SpEdge = std::shared_ptr<ListEdge>;
struct ListEdge {
public:
SpEdge next = nullptr;
int y = 0;
int weight = 0;
};
class ListNodeIterator : public NodeIterator {
public:
ListNodeIterator(const ListGraph *g, int x);
bool HasNext() override;
Edge Next() override;
private:
const ListGraph *mGraph = nullptr;
int mNodeX = 0;
SpEdge mCurrentEdge = nullptr;
};
private:
void doDfs(int x, std::vector<int> &vis, const VisitFunc &fn) const;
public:
std::vector<std::shared_ptr<ListEdge>> mEdges;
// std::vector<ListEdge *> mEdges;
};
#endif //AGORITHM_LISTGRAPH_H
// .cpp
//
// Created on 3/22/18.
//
#include <queue>
#include "ListGraph.h"
using namespace std;
ListGraph::ListGraph(Graph::Kind kind, int numberOfNodes) : Graph(kind, numberOfNodes) {
mEdges.resize(numberOfNodes, nullptr);
}
void ListGraph::AddEdge(int x, int y, int weight) {
AddEdge(x, y, weight, GetKind(), true);
}
void ListGraph::AddEdge(int x, int y, int weight, Kind kind, bool append) {
auto edge = std::make_shared<ListEdge>();
edge->y = y;
edge->weight = weight;
if (append) {
if (mEdges[x]) {
auto p = mEdges[x];
while (p->next) {
p = p->next;
}
p->next = edge;
} else {
mEdges[x] = edge;
}
} else {
auto p = mEdges[x];
edge->next = p;
mEdges[x] = edge;
}
if (kind == UNDIRECTED) {
AddEdge(y, x, weight, DIRECTED, append);
}
}
void ListGraph::DFS(const VisitFunc &fn, int start) const {
const int n = GetNumberOfNodes();
vector<int> vis(n, 0);
doDfs(start, vis, fn);
for (int i = 0; i < n; i++) { // remaining
if (!vis[i]) {
doDfs(i, vis, fn);
}
}
}
void ListGraph::doDfs(int x, std::vector<int> &vis, const Graph::VisitFunc &fn) const {
if (!vis[x]) {
vis[x] = 1;
fn(x);
auto p = mEdges[x];
while (p) {
if (!vis[p->y]) {
doDfs(p->y, vis, fn);
}
p = p->next;
}
}
}
void ListGraph::BFS(const VisitFunc &fn, int start) const {
std::queue<int> q;
const int N = GetNumberOfNodes();
vector<int> vis(N, 0);
auto run = [&](int i) {
if (!vis[i]) {
q.push(i);
}
while (!q.empty()) {
int x = q.front();
q.pop();
if (!vis[x]) {
vis[x] = 1;
fn(x);
auto p = mEdges[x];
while (p) {
if (!vis[p->y]) {
q.push(p->y);
}
p = p->next;
}
}
}
};
run(start);
for (int i = 0; i < N; i++) {
run(i);
}
}
Graph::NodeIterator *ListGraph::CreateIteratorForNode(int x) const {
return new ListNodeIterator(this, x);
}
int ListGraph::GetWeightForEdge(int x, int y) const {
auto p = mEdges[x];
while (p) {
if (p->y == y) {
return p->weight;
}
p = p->next;
}
return 0;
}
bool ListGraph::ListNodeIterator::HasNext() {
return mCurrentEdge != nullptr;
}
Graph::Edge ListGraph::ListNodeIterator::Next() {
if (!mCurrentEdge) {
throw std::range_error("out of range");
}
auto p = mCurrentEdge;
mCurrentEdge = mCurrentEdge->next;
return {mNodeX, p->y, p->weight};
}
ListGraph::ListNodeIterator::ListNodeIterator(const ListGraph *g, int x) {
mGraph = g;
mNodeX = x;
mCurrentEdge = mGraph->mEdges[mNodeX];
}
其中NodeIterator的意思是，和某个点直接相连的所有点。上面都用了一个shared_ptr来包括iterator，以防内存泄露。
访问图所有点的方法，有DFS（深度优先）和BFS（广度优先）。
