C语言 图的问题，请使用图的算法解决，没学过图的数据结构，不太会用（最好有注释）计算机系统中产生死锁有以下四个必要条件：〈1〉互斥条件。即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占有。〈2〉不可抢占条件。进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。〈3〉占有且申请条件。进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占用已占有的资源。
2019-05-30
C语言 图的问题，请使用图的算法解决，没学过图的数据结构，不太会用（最好有注释）
计算机系统中产生死锁有以下四个必要条件：
〈1〉互斥条件。即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占有。
〈2〉不可抢占条件。进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。
〈3〉占有且申请条件。进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占用已占有的资源。
〈4〉循环等待条件。存在一个进程等待序列{P1，P2，...，Pn}，其中P1等待P2所占有的某一资源，P2等待P3所占有的某一资源，...，而Pn等待P1所占有的的某一资源，形成一个进程循环等待环。
现在系统中有m个进程，这些进程之间的等待关系是已知的。为了检测死锁是否存在，thinkpoet想请聪明的你帮忙检测这m个进程是否满足死锁的循环等待条件，即这m个进程是否存在有进程循环等待环。
Input
输入的第一行是一个整数m（0 < m <=
1000），表示进程总数。进程编号1,2,...,m。
输入的第二行到m+1行数据描述进程之间的等待关系。第i+1行描述第i个进程的等待关系，格式如下：
mi
p1 p2 ...
pmi
其中mi表示进程i需要等待mi个其他进程，后面跟着这mi个进程编号，编号从小到大排列。
Output
如果满足循环等待条件，则输出yes，否则，输出no。
Sample Input
4
0
2 1 4
1 2
1 3
Sample Output
yes
优质解答
在查询一个点是否循环时,有可能先陷入另一个循环,所以不能简单检测是否返回自身.
比如:
1->2->3->2->3.....
提供一个方案
其中还有一个问题,将图化为树进行遍历,用最小生成树方法.
接下来,建立一个用来路径记录的数组,将每一个被遍历的点存入其中,每一次存入都查找之前是否访问过该点,如果有,则判定为循环.
另外又想到一个直接的方法:
借鉴最小生成树方法,以一点作为根,生成一颗树,每一次生成新节点时,检测生成节点数是否大于mi.这样可以简单编码解决问题.
若遇到循环,则一定会生成mi+n个叶子,那么超过即判定存在循环.
在查询一个点是否循环时,有可能先陷入另一个循环,所以不能简单检测是否返回自身.
比如:
1->2->3->2->3.....
提供一个方案
其中还有一个问题,将图化为树进行遍历,用最小生成树方法.
接下来,建立一个用来路径记录的数组,将每一个被遍历的点存入其中,每一次存入都查找之前是否访问过该点,如果有,则判定为循环.
另外又想到一个直接的方法:
借鉴最小生成树方法,以一点作为根,生成一颗树,每一次生成新节点时,检测生成节点数是否大于mi.这样可以简单编码解决问题.
若遇到循环,则一定会生成mi+n个叶子,那么超过即判定存在循环.