作者lincy075 (Kasim)
看板ASIA_ISA
标题Re: [问卷] 有关使用维基百科於课业上之调查
时间Thu Jan 7 22:09:44 2010
话说今天一位大四同学问老师下面这个问题
How many spanning trees does a five node complete graph have?
(A) 120 (B) 60 (C) 48 (D) 24
老师想了想觉得这问题不容易, 就用维基百科找答案
可见维基百科是可以用在课业上的, 老师也常把维基百科的资料放到投影片,
不过呀维基百科的答案不在上面选项
http://en.wikipedia.org/wiki/Cayley%27s_formula
5^3 = 125
老师只好写了一个程式去算 (同学既然问了总是要想办法回答),
果然是 125 (看来是出题的人出错了)
有兴趣的同学可看看老师的程式 (不过是为了解答同学问题而写的, 写法没很好)
import java.util.ArrayList;
public class STCG {
static ArrayList<Edge> elist;
public static void main(String[] args) {
int [] bit = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
elist = new ArrayList<Edge>();
elist.clear();
elist.add(new Edge(0, 1));
elist.add(new Edge(0, 2));
elist.add(new Edge(0, 3));
elist.add(new Edge(0, 4));
elist.add(new Edge(1, 2));
elist.add(new Edge(1, 3));
elist.add(new Edge(1, 4));
elist.add(new Edge(2, 3));
elist.add(new Edge(2, 4));
elist.add(new Edge(3, 4));
int ntrees = 0;
for (int i = 0; i < 1024; i++) {
for (int j = 0; j < 10; j++) {
if ((i & bit[j]) == bit[j]) {
elist.get(j).treeedge = true;
} else {
elist.get(j).treeedge = false;
}
}
int edgecount = 0;
for (int j = 0; j < 10; j++) {
if (elist.get(j).treeedge == true) {
edgecount++;
}
}
if (edgecount != 4) continue;
ArrayList<Vertex> vlist = new ArrayList<Vertex>();
vlist.clear();
for (int j = 0; j < 5; j++) {
vlist.add(new Vertex(j));
}
for (int j = 0; j < 10; j++) {
if (elist.get(j).treeedge == true) {
int p1 = elist.get(j).p1;
int p2 = elist.get(j).p2;
vlist.get(p1).neighbor.add(p2);
vlist.get(p2).neighbor.add(p1);
}
}
DFSKernel(vlist, 0);
boolean kickflag = false;
for (int j = 0; j < 5; j++) {
if (vlist.get(j).ccid != 0) {
kickflag = true;
break;
}
}
if (kickflag == false)
ntrees++;
}
System.out.println(ntrees);
}
static void DFSKernel(ArrayList<Vertex> vlist, int vid) {
vlist.get(vid).flag = true;
for (int i = 0; i < vlist.get(vid).neighbor.size(); i++) {
int nid = vlist.get(vid).neighbor.get(i);
vlist.get(nid).ccid = 0;
if (vlist.get(nid).flag == false) {
DFSKernel(vlist, nid);
}
}
}
}
class Vertex {
public ArrayList<Integer> neighbor;
public int ccid;
public boolean flag;
Vertex(int ccid) {
neighbor = new ArrayList<Integer>();
neighbor.clear();
this.ccid = ccid;
flag = false;
}
}
class Edge {
public int p1;
public int p2;
public boolean treeedge;
Edge(int p1, int p2) {
this.p1 = p1;
this.p2 = p2;
}
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 210.70.83.127
1F：推 ag2360133:快回 不然会被说看不懂 01/07 22:11
2F：推 invite0403:英文的WIKI跟中文的WIKI内容丰富度差好多= = 01/08 01:47
3F：推 XXXmilk:快回不然会被说看不懂 其实我5岁的时候就常常拿这个来玩了 01/09 14:30
4F：→ ag2360133:楼上金豪洨 01/11 03:05