打印结束时完成的任务
原文:
给定表单的 n 依赖项 x y ，其中 x & y 代表两个不同的任务。依赖关系 x y 表示形式的依赖关系 y - > x ，即如果任务 y 发生，那么任务 x 将发生，换句话说，任务 y 必须首先完成才能启动任务 x。任务是按照字典顺序打印最后要完成的所有任务。注意任务只用大写英文字母表示。
输入: dep[][] = {{a，b}，{c，b}，{d，a}，{d，c}，{b，e}}，tasks[] = {b，c} 输出: a b c d 任务 a 发生在任务 b 之后，任务 d 只能发生在任务 a 或 c 完成后
所以，需要的顺序是 a b c d
输入: dep[][] = {{q，p}，{s，q}，{q，r}}，tasks[]= { r } t3】输出: q r s
进场: 可以用来解决问题。形式 x y (y - > x) 的依赖关系可以表示为图中从节点 y 到节点 x 的边。从每个 m 初始节点启动 dfs，并使用布尔数组将遇到的节点标记为已访问。最后，按照字典顺序打印使用 dfs 覆盖的节点/任务。该方法之所以有效，是因为 dfs 将以顺序方式覆盖从初始节点开始的所有节点。
考虑下面代表上面第一个例子的图表: 该图表用 颜色将初始任务 b 和 c 的 dfs 期间覆盖的边显示为红色。这样访问的节点是 a、b、c 和 d
下面是上述方法的实现:
c
// c implementation of the approach
#include
#include
#include
using namespace std;
// graph class represents a directed graph
// using adjacency list representation
class graph {
// number of vertices
int v;
// pointer to an array containing
// adjacency lists
vector* adj;
// boolean array to mark tasks as visited
bool visited[26];
// a recursive function used by dfs
void dfsutil(int v);
public:
// constructor
graph()
{
// there are only 26 english
// upper case letters
this->v = 26;
adj = new vector[26];
}
// function to add an edge to the graph
void addedge(char v, char w);
// dfs traversal of the vertices
// reachable from v
void dfs(char start[], int m);
void printtasks();
};
// function to add an edge to the graph
void graph::addedge(char v, char w)
{
// add w to v's list
adj[v - 65].push_back(w - 65);
}
void graph::dfsutil(int v)
{
// mark the current node as visited and
// print it
visited[v] = true;
// recur for all the vertices adjacent
// to this vertex
vector::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); i)
if (!visited[*i])
dfsutil(*i);
}
// dfs traversal of the vertices reachable
// from start nodes
// it uses recursive dfsutil()
void graph::dfs(char start[], int m)
{
// mark all the vertices as not visited
for (int i = 0; i < v; i )
visited[i] = false;
// call the recursive helper function
// to print dfs traversal
for (int i = 0; i < m; i )
dfsutil(start[i] - 65);
}
// helper function to print the tasks in
// lexicographical order that are completed
// at the end of the dfs
void graph::printtasks()
{
for (int i = 0; i < 26; i ) {
if (visited[i])
cout << char(i 65) << " ";
}
cout << endl;
}
// driver code
int main()
{
// create the graph
graph g;
g.addedge('b', 'a');
g.addedge('b', 'c');
g.addedge('a', 'd');
g.addedge('c', 'd');
g.addedge('e', 'b');
// initial tasks to be run
char start[] = { 'b', 'c' };
int n = sizeof(start) / sizeof(char);
// start the dfs
g.dfs(start, n);
// print the tasks that will get finished
g.printtasks();
return 0;
}
python 3
# python3 implementation of the approach
from collections import defaultdict
# this class represents a directed graph
# using adjacency list representation
class graph:
# constructor
def __init__(self):
# default dictionary to store the graph
self.graph = defaultdict(list)
self.visited = [false]*26
# function to add an edge to the graph
def addedge(self, u, v):
self.graph[ord(u)-65].append(ord(v)-65)
# a function used by dfs
def dfsutil(self, v):
# mark the current node as visited
# and print it
self.visited[v]= true
# recur for all the vertices adjacent
# to this vertex
for i in self.graph[v]:
if self.visited[i] == false:
self.dfsutil(i)
# function to perform the dfs traversal
# it uses recursive dfsutil()
def dfs(self, start, m):
# total vertices
v = len(self.graph)
# call the recursive helper function
# to print the dfs traversal starting
# from all vertices one by one
for i in range(m):
self.dfsutil(ord(start[i])-65)
def printorder(self):
for i in range(26):
if self.visited[i] == true:
print(chr(i 65), end =" ")
print("\n")
# driver code
g = graph()
g.addedge('b', 'a')
g.addedge('b', 'c')
g.addedge('a', 'd')
g.addedge('c', 'd')
g.addedge('e', 'b')
g.dfs(['b', 'c'], 2)
g.printorder()
output:
a b c d
时间复杂度: o(v e)，其中 v 为图中节点数，e 为边数或依赖数。在这种情况下，由于 v 总是 26，所以时间复杂度是 o(26 e)或者最坏情况下只是 o(e) 。 空间复杂度: o(v e)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
