六、 使用图解决编程问题
图可以表示为Graph＝（V,E)，V顶点，E边
完全图(complete graph)：图中的每个顶点与其他顶点都有边相连。在完全图中边数目达到最大。
连通图：若从顶点vi到顶点vj有路径，则称顶点vi与vj是连通的。如果无向图中任意两个顶点都是连通的，则称此图是连通图。
生成树(spanning tree)：一个连通图的生成树是它的一个连通子图，它包含图中全部n个顶点和仅使这n个顶点连通的n-1条边。
两种最通用的表示图的方式是：
邻接矩阵——缺点：当顶点多而边数少时，矩阵是稀疏矩阵，有很大费。
邻接表
两种方法的遍历图：
深度优先搜索(DFS)
深度优先搜索是从图中某一顶点v出发，在访问顶点v后，再依次从v的任一还没有被访问的邻接顶点w出发进行深度优先搜索；直到图中所有与顶点v有路径相通的顶点都被访问过为止。
DFS可以使用递归算法实现，也可以使用栈实现。
实现时，需要设置一个数组表示相应的顶点有没有被访问过,初始所有顶点的访问标志置0。
算法：DFS（v）
1.将起始顶点v访问标志置1，顶点压入栈中；
2.重复以下三步直到栈变成空：
从栈中弹出一个顶点。
访问弹出的顶点。
将所有与该顶点相邻接的还未访问顶点的访问标志置1，并压入栈中。
如果图不是连通的，算法将不能遍历所有节点。为了解决这个问题，需要对图中所有未访问顶点重复执行上述算法。
1.对图中每个顶点v重复步骤2
2.如果v未被访问：
a.调用DFS(v)
namespace play
{
class Vertex
{
public Vertex(string vna)
{
vname = vna;
wasVisited = false;
}
public string vname;
public bool wasVisited;
}
class Graph
{
private Vertex[] vertices = new Vertex[10];
private int[,] cost = new int[10, 10];//邻近矩阵包含边的代价
private int n;//n是顶点的数目
int infinity = 9999999;//将非常大的值作为无穷大。
Stack<Vertex> thestack = new Stack<Vertex>(10);
Queue<Vertex> thequeue = new Queue<Vertex>();
…………
public void dfs()//深度遍历
{
vertices[0].wasVisited = true;
Console.Write("深度遍历的结果：" + vertices[0].vname + ",");
thestack.Push(vertices[0]);
while (thestack.Count > 0)
{
int v = getAdjUnvisitedVertex(thestack.Count - 1);//有问题
if (v == -1)
thestack.Pop();
else
{
vertices[v].wasVisited = true;
Console.Write(vertices[v].vname + ",");
thestack.Push(vertices[v]);
}
}
for (int j = 0; j < n; j++)
vertices[j].wasVisited = false;
Console.WriteLine();
}
public int getAdjUnvisitedVertex(int v)
{
for (int j = 0; j < n; j++)
if (cost[v, j] != infinity && vertices[j].wasVisited == false)
return j;
return -1;
}
}
}
广度优先搜索(BFS)
广度优先搜索是从图的某一顶点V出发，访问此顶点后，再依次访问V的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到。
算法：BFS（v）
1.访问起始顶点v，将其访问标志置1，并且将它插入队列。
2.重复步骤4直到队列变成空。
3.从队列删除一个顶点，访问该顶点所有未访问的邻接顶点，将它们的访问标志置1，并且将它们插入到队列中。
如果图不是连通的，算法将不能遍历所有顶点。为了解决这个问题，需要对图中的未访问顶点重复执行这个算法。
1.为图中每个顶点V重复步骤2。
2.如果v未被访问：
a.调用BFS(v)
public void bfs()//广度遍历
{
Console.Write("广度遍历的结果：" + vertices[0].vname + ",");
vertices[0].wasVisited = true;
thequeue.Enqueue(vertices[0]);
while (thequeue.Count > 0)
{
int w = getAdjUnvisitedVertex(thequeue.Count - 1);
if (w == -1)
thequeue.Dequeue();
else
{
Console.Write(vertices[w].vname + ",");
vertices[w].wasVisited = true;
thequeue.Enqueue(vertices[w]);
}
}
for (int j = 0; j < n; j++)
vertices[j].wasVisited = false;
Console.WriteLine();
}
By Crayon
数据结构与算法（一）：http://blog.csdn.net/crayon_chen/article/details/7700665
数据结构与算法（二）：http://blog.csdn.net/crayon_chen/article/details/7700675
数据结构与算法（四）：http://blog.csdn.net/crayon_chen/article/details/7700697