有向图
1.有向图的定义
有向图：由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点。
有向路径：由一系列顶点组成，对于其中的每个顶点都存在一条有向边从它指向序列的下一个顶点。
有向环：一条至少含有一条边且起点终点都相同的有向路径
可达性：存在从顶点v到顶点w的路径，使顶点w能从顶点v到达
2.有向图的数据结构
与无向图一样，也用邻接表表示有向图
代码实现：
class Digraph //有向图
{
private:
int vertax; //顶点
int edge; //边数
vector<vector<int>> adjList; //邻接表
public:
Digraph(int V) //创建V个顶点，无连接关系的有向图
{
vertax = V;
edge = 0;
adjList.resize(V, vector<int>());
}
Digraph(string in) //根据文件读入一幅有向图
{
ifstream infile(in);
string temp;
int i = 0;
while (getline(infile, temp))
{
istringstream iss(temp);
int v, w;
if (i == 0)
{
iss >> vertax;
adjList.resize(vertax, vector<int>());
}
else if (i == 1)
iss >> edge;
else
{
iss >> v >> w;
adjList[v].push_back(w);
}
i++;
}
}
void addEdge(int v, int w) //添加一条边
{
adjList[v].push_back(w);
edge++;
}
int V() { return vertax; } //返回顶点数
int E() { return edge; } //返回边数
vector<int> adj(int v) { return adjList[v]; } //返回顶点V指向的所有节点
Digraph &reverse() //返回反向图
{
Digraph R(vertax);
for (int v = 0; v < vertax; v++)
for (auto w : adjList[v])
R.addEdge(w, v);
return R;
}
string toString() //字符串输出图
{
string s = to_string(vertax) + " vertices, " + to_string(edge) + " egdes\n";
for (int v = 0; v < vertax; v++)
{
s += to_string(v) + ": ";
for (int w : adjList[v])
s += to_string(w) + " ";
s += "\n";
}
return s;
}
};
3.有向图中的可达性和寻路
单点可达性：给定一幅有向图和一个起点s，求出是否存在一条从s到给定顶点v 的路径
多点可达性：给定一幅图和顶点的集合，求出是否存在一条从集合中的任意顶点到达给顶点的v的有向路径
在有向图中，深度优先搜索标记由一个集合的顶点可达的所有顶点所需的时间与被标记的顶点的出度之和成正比。
代码实现：
class DirectedDFS //有向图的可达性
{
private:
vector<bool> marked;
public:
DirectedDFS(Digraph DG, int s) //单点可达性
{
marked.resize(DG.V(), false);
dfs(DG, s);
}
DirectedDFS(Digraph DG, vector<int> sources) //多点可达性
{
marked.resize(DG.V(), false);
for (int s : sources)
if (!marked[s])
dfs(DG, s);
}
void dfs(Digraph DG, int v)
{
marked[v] = true;
for (auto w : DG.adj(v))
if (!marked[w])
dfs(DG, w);
}
bool isMarked(int v)
{
return marked[v];
}
};
寻路算法
代码实现(DFS)：
class DepthFirstDirectedPaths //DFS寻路
{
private:
vector<bool> marked;
vector<int> edgeTo;
int start;
public:
DepthFirstDirectedPaths(Digraph G, int s) //构造函数
{
marked.resize(G.V(), false);
edgeTo.resize(G.V(), 0);
start = s;
dfs(G, s);
}
void dfs(Digraph G, int v)
{
marked[v] = true;
for (int w : G.adj(v))
if (!marked[w])
{
edgeTo[w] = v;
dfs(G, w);
}
}
bool hasPathTo(int v)
{
return marked[v];
}
void pathTo(vector<int> &path, int v) //返回路径
{
if (!hasPathTo(v))
return;
stack<int> p;
for (int x = v; x != start; x = edgeTo[x])
p.push(x);
p.push(start);
while (!p.empty())
{
path.push_back(p.top());
p.pop();
}
}
};
代码实现(BFS)：
class BreadthFirstDirectedPaths //BFS寻路
{
private:
vector<bool> marked;
vector<int> edgeTo;
vector<int> distTo; //最短路径的长度
public:
BreadthFirstDirectedPaths(Digraph G, int s)
{
marked.resize(G.V(), false);
edgeTo.resize(G.V(), 0);
distTo.resize(G.V(), INT_MAX);
bfs(G, s);
}
void bfs(Digraph G, int s)
{
queue<int> q;
marked[s] = true;
distTo[s] = 0;
q.push(s);
while (!q.empty())
{
int v = q.front();
q.pop();
for (int w : G.adj(v))
if (!marked[w])
{
edgeTo[w] = v;
distTo[w] = distTo[v] + 1;
marked[w] = true;
q.push(w);
}
}
}
bool hasPathTo(int v)
{
return marked[v];
}
int dist(int v) //返回顶点v距离原点的最近距离
{
return distTo[v];
}
void pathTo(vector<int> &path, int v) //返回路径
{
if (!hasPathTo(v))
return;
stack<int> p;
int x;
for (x = v; distTo[x] != 0; x = edgeTo[x])
p.push(x);
p.push(x);
while (!p.empty())
{
path.push_back(p.top());
p.pop();
}
}
};
4.有向图的环
如果有向图中存在还，即存在一条从某个顶点出发并返回自己的路径。
有向图中环的数量可能是图的大小的指数级别，并且很多时候我们只需要知道有向图中是否存在有向环(例如任务调度问题需要有向图为DAG图)。因此寻找有向环的时候，我们只需要找出一个环即可。
通过深度优先搜索我们就可以解决这个问题，我们假设找到了一条有向边v->w并且w已经在调用栈里，就找到了一个有向环。因为调用栈表示的是一条w->v的有向路径，整好形成了这个环。
代码实现：
class DirectedCycle //寻找有向环
{
private:
vector<bool> marked;
vector<int> edgeTo;
vector<bool> onStack; //调用栈
stack<int> cycle; //环的路径
public:
DirectedCycle(Digraph G) //构造函数
{
marked.resize(G.V(), false);
onStack.resize(G.V(), false);
edgeTo.resize(G.V(), 0);
for (int v = 0; v < G.V(); v++)
if (!marked[v] && cycle.empty())
dfs(G, v);
}
void dfs(Digraph G, int v)
{
marked[v] = true;
onStack[v] = true; //将v压入递归栈
for (int w : G.adj(v))
{
if (!cycle.empty()) //已经存在环 则退出
return;
else if (!marked[w])
{
edgeTo[w] = v;
dfs(G, w);
}
else if (onStack[w]) //在v->w路径时，w在递归栈里
{
for (int x = v; x != w; x = edgeTo[x])
cycle.push(x);
cycle.push(w);
cycle.push(v);
}
}
onStack[v] = false; //循环结束，将v压出递归栈
}
bool hasCycle()
{
return !cycle.empty();
}
void cyclePath(vector<int> &path) //环的路径
{
stack<int> temp = cycle;
while (!temp.empty())
{
path.push_back(temp.top());
temp.pop();
}
}
};
5.拓扑排序
拓扑排序是对一个有向图构造拓扑序列，是对所有结点的一个线性排序。该排序满足这样的条件——对于图中的任意两个结点u和v，若存在一条有向边从u指向v，则在拓扑排序中u一定出现在v前面。
拓扑排序的前提是有向图为有向无环图(DAG)。
实现方法1：基于深度优先搜索的拓扑排序，一幅DAG图的拓扑排序为所有顶点的逆后序排列。
证明：对任意的边v->w，在调用dfs(v)时，一定会有三种情况
dfs(w)已经被调用过并且已经返回了
dfs(w)还没被调用，因此v->w会直接或间接的调用并返回dfs(w)，且dfs(w)会在dfs(v)返回前返回
dfs(w)已经被调用但还没有返回
在DAG图中，第三种情况不可能出现，因为dfs(w)若还在调用栈里，意味着存在一条w->v的路径，与v->w形成一个环。
而前两种情况下，dfs(w)都会在dfs(v)之前完成，因此在逆后序排列中w排在v之后。
代码实现：
class Topological
{
private:
vector<int> order;
public:
Topological(Digraph G)
{
DirectedCycle cycleFinder(G); //寻找有向环
if (!cycleFinder.hasCycle())
{
DepthFirstOrder dfs(G); //G所有顶点的逆后序
dfs.reversePostOrder(order);
}
}
vector<int> &Order()
{
return order;
}
bool isDAG()
{
return !order.empty();
}
};
实现方法2：从DAG图中选择一个入度为0的顶点，删除该顶点和所有以它为起点的有向边，重复上述步骤知道DAG图为空或者图中无入度为0的顶点。如果此时DAG图不为空，则有向图中必有环。
代码实现：
Topological_Sort(Digraph G)
{
vector<int> indegree(G.V(),0);
for (int v = 0; v < G.V(); v++) //初始化入度数组
{
for (int w : G.adj(v))
indegree[w]++;
}
queue<int> q; //入度为0的节点集合
for (int v = 0; v < G.V(); v++) //入队
if (indegree[v] == 0)
q.push(v);
int count = 0;
while (!q.empty())
{
int v = q.front();
q.pop();
cout << v << " ";
count++;
vector<int> temp = G.adj(v);
for (int w : temp)
if (!(--indegree[w]))
q.push(w);
}
if (count < G.V())
cout << "It is not DAG" << endl;
}
6.强连通分量
强连通：如果顶点v和顶点w是互相可达的，则称他们为强连通的。如果一幅有向图的任意两个顶点都是强连通的，那称这幅有向图也是强连通的。
强连通分量：强连通性将一幅有向图的顶点分成一些等价类，每个等价类都是由互相强连通的顶点的最大子集构成的，我们称这些子集为强连通分量。
Kosaraju算法能够在线性时间内计算出强连通分量，下面是算法的描述
- 在给定一幅有向图G中，获取其反向图的逆后序
- 在G中进行深度优先搜索，但是要按刚才得到的逆后序来搜索
- 所以在同一个递归dfs()调用中被访问的顶点都在同一个强连通分量中
代码实现：
class KosarajuSCC //Kosaraju算法获取强连通分量
{
private:
vector<bool> marked;
vector<int> id;
int count;
public:
KosarajuSCC(Digraph G)
{
marked.resize(G.V(), false);
id.resize(G.V(), 0);
count = 0;
DepthFirstOrder order(G.reverse()); //获取反向图的逆后序
vector<int> RPO;
order.reversePostOrder(RPO);
for (int s : RPO) //按逆后序进行DFS
if (!marked[s])
{
dfs(G, s);
count++;
}
}
void dfs(Digraph G, int v)
{
marked[v] = true;
id[v] = count;
for (int w : G.adj(v))
if (!marked[w])
dfs(G, w);
}
bool stronglyConnected(int v, int w) //强连通关系
{
return id[v] == id[w];
}
int ID(int v)
{
return id[v];
}
int COUNT() //强连通分量数量
{
return count;
}
};