图论初步
通过上网课的方式，我今天了解了什么是图论，以及图论在c++中的应用方式和代码构成。
我们可以用数组的方式存储图像，如二维数组a【5】【5】；
1 2 3 4
1 0 1 1 -1
2 1 0 -1 1
3 1 -1 0 -1
4 -1 1 -1 0
可以表示图
这类似于一个表格。
从左到右第一行表示点1到点2、3、4的距离（我们假设距离为1）。如果在图中无法到达（例如点1到点4）我们用-1或者正无穷表示。
向下以此类推。
另外，我们把图分为有向图和无向图；
上面的图就是无向图（点的连接中没有方向性）
有向图就是点的连接会有一定的方向性。
例如1——>2;
这个简单的图就是有向图，路径只能从点1到点2，而不能从点2到点1。
遍历
既然有了图和点之间的方向，我们会想到从一个点如何走才能走到每一个其它点呢？
这就涉及到图的遍历。
当我们一次就走完整张图，且不重复经过任意路径时，我们说这个图中存在“欧拉路”，如果我们此时回到了出发点，我们就把我们走过的路径叫“欧拉回路”。
也就是“一笔画”
利用图的遍历我们可以解决一些“一笔画”问题。
比如著名的七桥问题
有一个叫做哥尼斯堡的小镇，考虑到“哥尼斯堡”这个名字不好记，下文我们就称之为G镇。G镇的居民很爱锻炼身体，过着日出而作日落而息的生活，而他们睡前都喜欢到公园里遛弯消食。但是，G镇的居民不是只会享受生活的一群人，他们还热爱思考数学问题。
有一天，一个孩子提出了一个问题：
"我们的公园里有一条河，河上有两个小岛，在两岸小岛之间一共建造了7座桥，如果我想走过所有的桥然后回到我出发的地方应该怎么走呢？”
听到这个问题，整个G镇的居民都陷入了沉思，有的还晚上不睡觉，一遍一遍的在桥上走来走去，但是没有找到答案。
相信有好奇的读者肯定曾经自己也在纸上画过很多遍，但是都没有找到答案。
本来这个问题委实不会影响到G镇居民的生活，毕竟这并不影响到他们的生活。幸运的是，据说，刚好有一位很厉害的数学家刚好就暂住在G镇，这个孩子的问题引起了数学家的注意。
（这段是网上抄下来的，如有侵权，立刻删除）
我们可以把这个问题简化一下
有一个简单图，有4个顶点，7条边，问：能否遍历所有的边最后回到起点且不会重复经过同一条边。
经欧拉证明，这是不可能的。
但是如何用计算机算一下呢
以下是代码（also是抄的，如有侵权，立刻删除）
/**
*Author:Yuanhonglong
*Date:2013-12-16
*1948281915
*/
package mine.algorithm.graph;
import java.util.Vector;
class Land{
public static int[][] g;
//为四块陆地定义变量order,以示区别
public int order;
public Land(int Order){
this.order=Order;
}
//定义方法go,每走一步则将两块陆地间的一座桥去除
public void go(Land x){
g[this.order][x.order]-=1;
g[x.order][this.order]-=1;
}
}
public class Bridge extends Land{
/*
* 用图论解决古老的7桥问题
*/
public Bridge(int Order) {
super(Order);
}
public static Vector l= new Vector();
public static int Result=0,turn;
public static void main(String[] args) {
//抽象出四块陆地
Land land1=new Land(0);
Land land2=new Land(1);
Land land3=new Land(2);
Land land4=new Land(3);
//为方便管理,将陆地加入到向量l中
l.add(land1);
l.add(land2);
l.add(land3);
l.add(land4);
int n=l.size();
/*
* 将四块陆地间的联系-桥抽象出来
*/
g=new int[n][n];
for(int i=0;i
for(int j=0;j
g[i][j]=0;
}
}
/*
* 如果第i到第j块陆地有m座桥
* 则g[i][j]=m;
*/
g[0][1]=1;
g[0][2]=1;
g[0][3]=1;
g[1][0]=1;
g[1][2]=2;
g[1][3]=2;
g[2][0]=1;
g[2][1]=2;
g[3][0]=1;
g[3][1]=2;
System.out.println("各陆地之间的桥的数量:");
System.out.println(" A B C D");
for(int i=0;i
if(i==0){
System.out.print("A ");
}
if(i==1){
System.out.print("B ");
}
if(i==2){
System.out.print("C ");
}
if(i==3){
System.out.print("D ");
}
for(int j=0;j
System.out.print(g[i][j]+" ");
}
System.out.println();
}
//N用来记录有几种成功的可能
int N=0;
//All用来记录一共尝试了几次
int All=0;
//以下是通过嵌套循环实现遍历
for(int begin=0;begin
//由于可以从不同的桥开始,所有用begin代表从哪一座桥开始
//一共有7座桥,所以内部一共嵌套了7层循环,每层循环代表一步
for(int a=0;a
if(begin!=a&&g[begin][a]>0){
l.get(begin).go(l.get(a));
for(int b=0;b
if(a!=b&&g[a][b]>0){
l.get(a).go(l.get(b));
for(int c=0;c
if(b!=c&&g[b][c]>0){
l.get(b).go(l.get(c));
for(int d=0;d
if(c!=d&&g[c][d]>0){
l.get(c).go(l.get(d));
for(int e=0;e
if(d!=e&&g[d][e]>0){
l.get(d).go(l.get(e));
for(int f=0;f
if(e!=f&&g[e][f]>0){
l.get(e).go(l.get(f));
for(int g1=0;g1
if(f!=g1&&g[f][g1]>0){
l.get(f).go(l.get(g1));
//如果7步走完，则N加1,代表一次成功的尝试
N+=1;
g[f][g1]+=1;
g[g1][f]+=1;
//不管成功或失败,All都要加1
All++;
}
}
g[e][f]+=1;
g[f][e]+=1;
All++;
}
}
g[d][e]+=1;
g[e][d]+=1;
All++;
}
}
g[c][d]+=1;
g[d][c]+=1;
All++;
}
}
g[b][c]+=1;
g[c][b]+=1;
All++;
}
}
g[a][b]+=1;
g[b][a]+=1;
All++;
}
}
g[begin][a]+=1;
g[a][begin]+=1;
All++;
}
}
//输出结果
System.out.println("从第"+begin+"块陆地开始,一共进行了"+All+"次尝试共有"+N+"种方法可以完成。");
//N与All归零,换另一块陆地开始
N=0;
All=0;
}
}
}
说实话这个代码我没看懂，但是它确实解决了七桥问题。
图论这个东西很高端，基础我还没弄明白。所以就不和大家装X了，今天发文只是和大家分享一下学习经历。
以后我还要努力把这个东西弄会的。