图这种数据结构,在实际场景中被经常使用,也是笔者在上学时最不愿意”触摸”的并觉得特别高深莫测的理论,这里让我们一步步去剖析图这种数据结构。
图的几种表示方法
Edge List(弧表示法)
这种方法就是将图表示成为|E|edge的List或array,这里的list或array我们称之为edge list。为了表示一个edge,我们可以采用只具备两个参数的array,例如下面的表示方法:
[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
[3,8], [4,5], [4,9], [7,8], [7,9] ]
如果edge是有权重的,我们只需要为每个array添加上一个参数作为权重即可。
这种表示方法简单,但是如果我们想要去知道图中是否包含特定的edge的时候,我们需要去搜索整个edge list。
Adjacency Matrices(邻接矩阵法)
假设一个图中有V个点,那么采用Adjaceny Matrices的方法,就需要建立起一个VxV的0,1矩阵。row=i,column=j的地方为1的话表示edge(i,j)存在于图中,如果edge(i,j)有权重,那么只需要在edge(i,j)处填写上相应的权重值。这种图的长的就如下图一样
具体的表示方法是
[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
[0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]
这种表示法非常简单、直接。但是,在邻接矩阵的所有 个元素中,只有 个为非零元。如果网络比较稀疏,这种表示法浪费大量的存储空间,从而增加了在网络中查找弧的时间。
Adjacency list
Adjacency list采用了adjacency matrices和edge list相结合的方式。对于每一个vertex i,存储其相对应的vertices adjacent。
其表示方法为
[ [1, 6, 8],
[0, 4, 6, 9],
[4, 6],
[4, 5, 8],
[1, 2, 3, 5, 9],
[3, 4],
[0, 1, 2],
[8, 9],
[0, 3, 7],
[1, 4, 7] ]
实际应用
在解决图的问题时,经常采用的方法还是BFS和DFS的方法,以下列举出几道图的力扣的问题。
207. 课程表
你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]
给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。
提示:
输入的先决条件是由 边缘列表 表示的图形,而不是 邻接矩阵 。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/course-schedule
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
首先是我自己对于这道题的解法,效率并不是十分的高,基本思路就是要确保没一个点都不会回到其自身,在具体的实施过程中,是分别对每一个进行判断,如果期间过程中可能的小环路,暂且忽略,只要确保不是回到自身就可。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
if(numCourses == 0 || numCourses == 1)
return true;
map<int,vector<int>>graph;
//make Adjacency list graph
for(auto &index : prerequisites)
{
graph[index[0]].push_back(index[1]);
}
for(int i = 0; i < numCourses; i++)
{
stack<int>dfs;
vector<bool>flag(numCourses, false);
dfs.push(i);
while(!dfs.empty())
{
int tmp = dfs.top();
dfs.pop();
if(flag[tmp] == true)
{
if(tmp == i)
return false;
else
continue;
}
else
flag[tmp] = true;
vector<int>tmpvec = graph[tmp];
for(auto &val : tmpvec)
dfs.push(val);
}
}
return true;
}
};
现在贴出来别人对于这道题的解法
BFS
BFS uses the indegrees of each node. We will first try to find a node with 0
indegree. If we fail to do so, there must be a cycle in the graph and we return false
. Otherwise we set its indegree to be -1
to prevent from visiting it again and reduce the indegrees of its neighbors by 1
. This process will be repeated for n
(number of nodes) times.
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
graph g = buildGraph(numCourses, prerequisites);
vector<int> degrees = computeIndegrees(g);
for (int i = 0; i < numCourses; i++) {
int j = 0;
for (; j < numCourses; j++) {
if (!degrees[j]) {
break;
}
}
if (j == numCourses) {
return false;
}
degrees[j]--;
for (int v : g[j]) {
degrees[v]--;
}
}
return true;
}
private:
typedef vector<vector<int>> graph;
graph buildGraph(int numCourses, vector<pair<int, int>>& prerequisites) {
graph g(numCourses);
for (auto p : prerequisites) {
g[p.second].push_back(p.first);
}
return g;
}
vector<int> computeIndegrees(graph& g) {
vector<int> degrees(g.size(), 0);
for (auto adj : g) {
for (int v : adj) {
degrees[v]++;
}
}
return degrees;
}
};
DFS
For DFS, in each visit, we start from a node and keep visiting its neighbors, if at a time we return to a visited node, there is a cycle. Otherwise, start again from another unvisited node and repeat this process. We use todo
and done
for nodes to visit and visited nodes.
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
graph g = buildGraph(numCourses, prerequisites);
vector<bool> todo(numCourses, false), done(numCourses, false);
for (int i = 0; i < numCourses; i++) {
if (!done[i] && !acyclic(g, todo, done, i)) {
return false;
}
}
return true;
}
private:
typedef vector<vector<int>> graph;
graph buildGraph(int numCourses, vector<pair<int, int>>& prerequisites) {
graph g(numCourses);
for (auto p : prerequisites) {
g[p.second].push_back(p.first);
}
return g;
}
bool acyclic(graph& g, vector<bool>& todo, vector<bool>& done, int node) {
if (todo[node]) {
return false;
}
if (done[node]) {
return true;
}
todo[node] = done[node] = true;
for (int v : g[node]) {
if (!acyclic(g, todo, done, v)) {
return false;
}
}
todo[node] = false;
return true;
}
};
参考资料
https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs
https://blog.csdn.net/woaidapaopao/article/details/51732947