# 图论

### 无权图

0表示不相连，0表示相连，当然了也可以表示成是True或者false，因为是一个无向图，所以这个邻接矩阵是对称的；同时也可以用邻接矩阵来表示有向图：

```namespace Matrix {
class DenseGraph {
private:
int n, m;
bool directed;
vector<vector<bool>> g;
public:
DenseGraph(int n, bool directed) {
this->n = n;
this->m = 0;
this->directed = directed;
for (int i = 0; i < n; ++i) {
g.emplace_back(vector<bool>(n, false));
}
}

~DenseGraph() = default;

int V() {
return n;
}

int E() {
return m;
}

void addEdge(int v, int w) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
if (haveEdge(v, w)) {
return;
}
g[v][w] = true;
if (!this->directed) {
g[w][v] = true;
}
this->m++;
}

bool haveEdge(int v, int w) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
return g[v][w];
}
};
}```

```namespace list {
class SparseGraph {
private:
int n, m;
bool directed;
vector<vector<int>> g;
public:
SparseGraph(int n, bool directed) {
this->n = n;
this->directed = directed;
this->m = 0;
for (int i = 0; i < n; ++i) {
g.emplace_back(vector<int>());
}
}

~SparseGraph() = default;

int V() {
return n;
}

int E() {
return m;
}

void addEdge(int v, int w) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
if (haveEdge(v, w)) {
return;
}
g[v].emplace_back(w);
if (v != w && !this->directed) {
g[w].emplace_back(v);
}
this->m++;
}

bool haveEdge(int v, int w) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
for (auto var : g[v]) {
if (var == w) {
return true;
}
}
return false;
}
};
}```

### 广度深度遍历

``` //interator
private:
SparseGraph &G;
int v;
int index;
public:
adjIterator(SparseGraph &graph, int v) : G(graph) {
assert(v < graph.n);
this->v = v;
this->index = 0;
}
int begin(){
if (!G.g[v].empty()){
return G.g[v][this->index];
}
return -1;
}
int next(){
index ++;
if (index < G.g[v].size()){
return G.g[v][index];
}
return -1;
}
bool end(){
return index >= G.g[v].size();
}
};```

```        class adjIterator{
private:
DenseGraph &G;
int v;
int index;
public:
this->v = v;
this->index = -1;
}

int begin(){
index = -1;
return next();
}

int next(){
for (index += 1; index < G.V(); index ++){
if (G.g[v][index]){
return index;
}
}
return -1;
}

bool end(){
return index >= G.V();
}
};```

```template <typename Graph>
public:
ifstream file(filename);
string line;
int V, E;
assert(file.is_open());
assert(getline(file, line));
stringstream ss(line);
ss >> V >> E;
assert(V == graph.V());
for (int i = 0; i < E; ++i) {
assert(getline(file, line));
stringstream ss(line);
int a, b;
ss >> a >> b;
}
}
};```

```using namespace std;

template<typename Graph>
class Component {
private:
int *id;
Graph &G;
bool *visited;
int Ccount;

void dfs(int v) {
visited[v] = true;
id[v] = Ccount;
cout << v << " ";
if (!visited[i]){
dfs(i);
}
}
}

public:
Component(Graph &graph) : G(graph) {
visited = new bool[G.V()];
id = new int[G.V()];
Ccount = 0;
for (int i = 0; i < G.V(); ++i) {
visited[i] = false;
id[i] = -1;
}
for (int i = 0; i < G.V(); ++i) {
if (!visited[i]) {
dfs(i);
Ccount++;
}
}
}

int count(){
return Ccount;
}

bool isConnected(int v, int w){
return id[v] == id[w];
}

~Component() {
delete [] visited;
}
};```

count用来计算连通分量的个数，id用来计算这些点是属于哪一个连通分量的，遍历这个点的所有点，这里就用迭代器很好的屏蔽了不同数据结构实现的区别，如果没有访问过那就从这个点开始深度优先，然后递归下去。既然id就是连通分量的代号，那么直接等于count即可。判断是不是在一个连通分量里面的就直接对比id即可。

```template<typename Graph>
class Path {
private:
bool *visited;
int *from;
Graph &G;
int s;

void dfs(int v) {
visited[v] = true;
if (!visited[i]) {
from[i] = v;
dfs(i);
}
}
}

public:
Path(Graph graph, int s) : G(graph) {
assert(s >= 0 && s < G.V());
visited = new bool[G.V()];
from = new int[G.V()];
for (int i = 0; i < G.V(); ++i) {
visited[i] = false;
from[i] = -1;
}
this->s = s;
dfs(s);
}

~Path() {
delete[] from;
delete[] visited;
}

void path(int w, vector<int> &vec) {
stack<int> s;
int p = w;
while (p != -1) {
s.push(p);
p = from[p];
}
vec.clear();
while (!s.empty()) {
vec.push_back(s.top());
s.pop();
}
}

bool hasPath(int w) {
assert(w >= 0 && w < G.V());
return visited[w];
}

void showPath(int w) {
for (int i = 0; i < G.V(); ++i) {
cout << visited[i] << " ";
}
vector<int> vec;
path(w, vec);
for (auto v: vec) {
cout << v << " ";
}
cout << endl;
}
};```

visited查看这些节点有没有被访问过，from查看这个节点是哪里来的，DFS遍历如果这个节点是没有被访问过的，那就赋值看看他是从哪个节点过来的，最后显示即可。最后需要反向查找。

，遍历的次数一定是平方。 图的广度优先遍历也需要用到队列。首先把这个节点周围的放入队列，如果队列不为空，那就直接出来一个把出来的那个周围的节点也塞进去，以此类推。广度优先遍历在图里面也叫层序遍历，一层一层的来，所以，先遍历到的肯定比后遍历到的距离原点要短，所以如果这个图是无权图，是可以使用这种方法来找到最短路径。每一层都加上1即可。

```template <typename Graph>
class bfs{
private:
Graph &G;
int s;
bool *visited;
int *from;
int *ord;
public:
bfs(Graph &graph, int s): G(graph){
assert(s >= 0 && s < graph.V());
from = new int[graph.V()];
ord = new int[graph.V()];
visited = new bool[graph.V()];
for (int i = 0; i < graph.V(); ++i) {
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this->s = s;
queue<int> q;
q.push(s);
ord[s] = 0;
visited[s] = true;
while (!q.empty()){
int w = q.front();
cout << w << " ";
q.pop();
if (!visited[i] ){
q.push(i);
visited[i] = true;
from[i] = w;
ord[i] = ord[w] + 1;
}
}
}
}

void showShortPath(int w){
stack<int> s;
if (visited[w]){
int p = w;
while (p != -1){
s.push(p);
p = from[p];
}
}
vector<int> vec;
while (!s.empty()){
vec.push_back(s.top());
s.pop();
}
for (auto v: vec) {
cout << v << " ";
}
cout << endl;
}
};```

from就是存储上一个节点，ord存储距离起始点的距离是多少。

BFS找到的就是最短路径。DFS其实也可以找到最短路径，但是是随机的，它和你存储图的顺序有不同，和图的结构也有关系，但是BFS是一定的，而且BFS的最短路径是不止一条。

# 带权图

```class Edge {
private:
int a, b;
Weight weight;
public:
Edge() {}

Edge(int a, int b, Weight weight) {
this->a = a;
this->b = b;
this->weight = weight;
}

~Edge() = default;

Weight wt(){
return weight;
}

int Other(int v) {
assert(v == a || v == b);
return v == a ? b : a;
}

friend ostream& operator<<(ostream &os, const Edge &e){
os << e.a << "->" << e.b << " : " << e.weight;
return os;
}

bool operator<(Edge<Weight>& e){
return weight < e.wt();
}

bool operator<=(Edge<Weight>& e){
return weight <= e.wt();
}

bool operator>(Edge<Weight>& e){
return weight < e.wt();
}

bool operator>=(Edge<Weight>& e){
return weight < e.wt();
}

bool operator==(Edge<Weight>& e){
return weight < e.wt();
}
};```

Edge类存储了起始点和终点和权值。重载了一些比较和输出符号，等一下的输出和比较都要用到。邻接矩阵需要修改的不多：

```using namespace std;
namespace Span {
template<typename Weight>

class DenseGraph {
private:
int n, m;
bool directed;
vector<vector<Edge<Weight> *>> g;
public:
DenseGraph(int n, bool directed) {
this->n = n;
this->m = 0;
this->directed = directed;
for (int i = 0; i < n; ++i) {
g.emplace_back(vector<Edge<Weight> *>(n, NULL));
}
}

~DenseGraph() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][j] != NULL) {
delete g[i][j];
}
}
}
}

int V() {
return n;
}

int E() {
return m;
}

void addEdge(int v, int w, Weight weight) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
if (haveEdge(v, w)) {
delete g[v][w];
if (!this->directed) {
delete g[w][v];
}
m--;
}
g[v][w] = new Edge<Weight>(v, w, weight);
if (!this->directed) {
g[w][v] = new Edge<Weight>(w, v, weight);
}
this->m++;
}

bool haveEdge(int v, int w) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
return g[v][w] != NULL;
}

void show() {
for (int i = 0; i < g.size(); ++i) {
for (int j = 0; j < g[i].size(); ++j) {
if (g[i][j] != NULL){
cout << g[i][j]->wt() << " ";
} else{
cout << "NULL" << " ";
}
}
cout << endl;
}
}

private:
DenseGraph &G;
int v;
int index;
public:
adjIterator(DenseGraph &graph, int v) : G(graph) {
this->v = v;
this->index = -1;
}

Edge<Weight> begin() {
index = -1;
return next();
}

Edge<Weight> next() {
for (index += 1; index < G.V(); index++) {
if (G.g[v][index]) {
return G.g[v][index];
}
}
return NULL;
}

bool end() {
return index >= G.V();
}
};
};
}```

```using namespace std;
namespace Sparse {
template<typename Weight>
class SparseGraph {
private:
int n, m;
bool directed;
vector<vector<Edge<Weight> *>> g;
public:
void show() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < g[i].size(); ++j) {
cout << g[i][j]->wt() << " ";
}
cout << endl;
}
}
SparseGraph(int n, bool directed) {
this->n = n;
this->directed = directed;
this->m = 0;
for (int i = 0; i < n; ++i) {
g.emplace_back(vector<Edge<Weight> *>());
}
}

~SparseGraph() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < g[i].size(); ++j) {
delete g[i][j];
}
}
}

int V() {
return n;
}

int E() {
return m;
}

void addEdge(int v, int w, Weight weight) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
if (haveEdge(v, w)) {
return;
}
g[v].emplace_back(new Edge<Weight>(v, w, weight));
if (v != w && !this->directed) {
g[w].emplace_back(new Edge<Weight>(w, v, weight));
}
this->m++;
}

bool haveEdge(int v, int w) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
for (auto var : g[v]) {
if (var->Other(v) == w) {
return true;
}
}
return false;
}

//interator
private:
SparseGraph &G;
int v;
int index;
public:

adjIterator(SparseGraph &graph, int v) : G(graph) {
assert(v < graph.n);
this->v = v;
this->index = 0;
}

int begin() {
if (!G.g[v].empty()) {
return G.g[v][this->index];
}
return -1;
}

int next() {
index++;
if (index < G.g[v].size()) {
return G.g[v][index];
}
return -1;
}

bool end() {
return index >= G.g[v].size();
}
};
};
}```

### Prim Algorithm

prim算法就是根据这个思想来完成最小生成树的构建。首先一开始所有点都是同一个阵营，首先遍历第一个点，也就是第0号点，那么这个点就出了这个阵营，把它相邻的边都扔进一个最小堆进行维护，如果当前的堆不是空的，那么就出第一个最小的边，但是出的时候需要判断这个边的两个顶点是不是不同阵营的，因为在遍历的过程中每一个点的阵营的改变的全局的，会影响到其他边本来的状态，所以取出来的时候需要判断一下，然后从取出来处理的那条边做突破口，看它两边的那个点是没有被访问的，继续上述步骤。准备一个marked boolean数组，false一边true一边，true表示被访问了，也就是被访问的一边没有被访问的一边。

```namespace MinimumSpanTree_Prim {
template<typename Graph, typename Weight>
class Prim {
private:
Graph &G;
MinHeap<Edge<Weight>> pq;
bool *marked;
vector<Edge<Weight>> MinimumEdge;
Weight mstWeight;

void visit(int v){
assert( !marked[v] );
marked[v] = true;
if (!marked[e->Other(v)]){
cout << e->wt() << " ";
pq.insert(*e);
}
}
cout << endl;
pq.show();
}
public:
Prim(Graph &graph) : G(graph), pq(MinHeap<Edge<Weight>>(G.E())){
marked = new bool[ G.V() ];
for (int i = 0; i < G.V(); ++i) {
marked[i] = false;
}
MinimumEdge.clear();
visit(0);
while ( !pq.isEmpty() ){
Edge<Weight> e = pq.extractMin();
cout << e.wt() << endl;
if (marked[e.v()] == marked[e.w()]){
continue;
}
MinimumEdge.push_back(e);
if ( !marked[e.v()] ){
visit(e.v());
} else{
visit(e.w());
}
}
mstWeight = MinimumEdge[0].wt();
for (int j = 1; j < MinimumEdge.size(); ++j) {
mstWeight += MinimumEdge[j].wt();
}
}

~Prim(){
delete [] marked;
}

vector<Edge<Weight>> mstEdges(){
return MinimumEdge;
}

Weight result(){
return mstWeight;
}
};
}```

，visit中遍历的复杂度也是E，所以综上Lazy Prim的复杂度就是

。其实是可以改进算法实现

### Kruskal Algorithm

```namespace MinimumSpanTree_Kruskal{
template <typename Graph, typename Weight>
class Kruskal{
private:
vector<Edge<Weight>> mst;
Weight mstWeight;
public:
Kruskal(Graph &graph){
MinHeap<Edge<Weight>> pg(graph.E());
for (int i = 0; i < graph.V(); ++i) {
if (e->v() < e->w()){
pg.insert(*e);
}
}
}
UF_version3::unionFind unionFind(graph.E());
while (!pg.isEmpty() && mst.size() < graph.V() - 1){
Edge<Weight> e = pg.extractMin();
if (unionFind.isConnected(e.v(), e.w())){
continue;
}
mst.push_back(e);
unionFind.unionElements(e.v(), e.w());
}
mstWeight =mst[0].wt();
for (int j = 1; j < mst.size(); ++j) {
mstWeight += mst[j].wt();
}
}

vector<Edge<Weight>> mstEdges(){
return mst;
}

Weight result(){
return mstWeight;
}
};
}```

### dijkstra算法

，这个时候0-2就是最小的了，因为这个再经过松弛操作只能是变大不会变小，这也是为什么不能负权边的原因。确定新的节点的最短路径之后开始松弛操作，从2开始，这个时候到1更小，于是替换，到4还没有被访问，于是就是7，到三明显还是短的，所以就是5，于是更新：

```template <typename Graph, typename Weight>
class Dijkstra{
private:
Graph &G;
int s;
Weight *distTo;
bool *marked;
vector<Edge<Weight> *> from;
public:
Dijkstra(Graph &graph, int s) : G(graph){
this->s = s;
distTo = new Weight[G.V()];
marked = new bool[G.V()];
for (int i = 0; i < G.V(); ++i) {
distTo[i] = Weight();
marked[i] = false;
from.push_back(NULL);
}
IndexMinHeap<Weight> pq(G.V());
distTo[s] = Weight();
marked[s] = true;
pq.insert(s, distTo[s]);
while (!pq.isEmpty()){
int v = pq.extractMinIndex();
marked[v] = true;
int w = e->Other(v);
if (!marked[w]){
if (from[w] == NULL || distTo[v] + e->wt() < distTo[w] ){
distTo[w] = distTo[v] + e->wt();
from[w] = e;
if (pq.contain(w)){
pq.change(w, distTo[w]);
} else{
pq.insert(w, distTo[w]);
}
}
}
}
}
}

void show(){
stack<Edge<Weight> *> ss;
for (int i = 1; i < G.V(); ++i) {
vector<Edge<Weight>> vec;
cout << i << " :" << endl;
Edge<Weight> * e = from[i];
while (e->v() != this->s){
ss.push(e);
e = from[e->v()];
}
ss.push(e);

while( !ss.empty() ){
e = ss.top();
vec.push_back( *e );
ss.pop();
}

for (int j = 0; j < vec.size(); ++j) {
cout << vec[j].v() << " ";
if( j == vec.size()-1 )
cout<<vec[j].w()<<endl;
}
//cout << distTo[i] << endl;
}
}

~Dijkstra(){
delete [] distTo;
delete [] marked;
}
};```

s就是开始遍历的节点，首先起始点肯定是要被访问的，所以自然marked就是true了，代表被访问过，起始点的距离直接就是0，因为起始点是到自己没有路径。压进堆里面，如果堆不为空，遍历最小边的原点，这个时候就是属于松弛的过程了，看看有没有过当前最小的节点可以得到更小的边，如果有，那么看看当前堆里面有没有包含了节点的最小路径，包含了就替换。

### Bellman-Ford算法

。处理的问题越多，那么复杂度就越大。同时如果存在的顶点经过了两次，那么就存在负权边。从一个顶点到另一个顶点最多只要经过v个顶点，有v01条边，如果违反了那么就证明是有负权环。一开始的思路其实差不多的，但是并不是只是找到最短的一条就停止，松弛操作的本质是绕道看看是不是更小的，所以自然的，遍历所有的点，看看是不是更小。对一个点的一次松弛操作，就是找到经过这个点的另外一条路径，多一条边权值更小。如果一个图没有负权环，从一个点到另外一个点的最短路径，最多经过所有的v个顶点，有v-1条边，所以就是对所有的点进行v-1词松弛操作。事实上对所有的点进行v-1次松弛操作理论上就找到了从源点到其它所有点的最短路径。如果还可以进行松弛，那么就证明是有负权边了。 实现起来其实很简单：

```namespace Ford{
template <typename Graph, typename Weight>
class BellmanFord{
private:
Graph &G;
int s;
Weight* distTo;
vector<Edge<Weight>*> from;
bool hasNegativeCycle;
public:

bool detectNegativeCycle(){
for (int i = 0; i < G.V(); ++i) {
if (!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]){
return true;
}
}
}
return false;
}

BellmanFord(Graph &graph, int s):G(graph){
this->s = s;
distTo = new Weight[G.V()];
for (int i = 0; i < G.V(); ++i) {
from.push_back(NULL);
}

distTo[s] = Weight();
for (int pass = 1; pass < G.V(); ++pass) {
for (int i = 0; i < G.V(); ++i) {
if (!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]){
distTo[e->w()] = distTo[e->v()] + e->wt();
from[e->w()] = e;
}
}
}
}
hasNegativeCycle = detectNegativeCycle();
}

void show(){
stack<Edge<Weight> *> ss;
for (int i = 1; i < G.V(); ++i) {
vector<Edge<Weight>> vec;
cout << i << " :" << endl;
Edge<Weight> * e = from[i];
while (e->v() != this->s){
ss.push(e);
e = from[e->v()];
}
ss.push(e);

while( !ss.empty() ){
e = ss.top();
vec.push_back( *e );
ss.pop();
}

for (int j = 0; j < vec.size(); ++j) {
cout << vec[j].v() << " ";
if( j == vec.size()-1 )
cout<<vec[j].w()<<endl;
}
//cout << distTo[i] << endl;
}
}
};
}```

68 篇文章14 人订阅

0 条评论

## 相关文章

3615

4566

### 写给开发者的机器学习指南（十）

An attempt at rank prediction for topselling books using text regression

923

### hust Dating With Girls

http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=573#problem/B 题意：求最大权...

2834

1043

### Codeforces Round #412 (rated, Div. 2, base on VK Cup 2017 Round 3)(A.B.C，3道暴力题，C可二分求解)

A. Is it rated? time limit per test：2 seconds memory limit per test：256 megabyte...

3697

541

1.6K8

871

### 1893. [国家集训队2011]等差子序列(bitset)

★★   输入文件：nt2011_sequence.in   输出文件：nt2011_sequence.out 简单对比 时间限制：0.3 s   内存限制：5...

35210