数据结构：图结构的实现
【各种东拼西凑来的】
图(Graph)是由顶点和连接顶点的边构成的离散结构。在计算机科学中，图是最灵活的数据结构之一，很多问题都可以使用图模型进行建模求解。例如：生态环境中不同物种的相互竞争、人与人之间的社交与关系网络、化学上用图区分结构不同但分子式相同的同分异构体、分析计算机网络的拓扑结构确定两台计算机是否可以通信、找到两个城市之间的最短路径等等。
1 图的概念
1.1 图的基础概念串讲
图的结构很简单，就是由顶点$V$集和边$E$集构成，因此图可以表示成$G=(V, E)$。
注意：顶点有时也称为节点或者交点，边有时也称为链接。
无向图
我们可以说这张图中，有点集$V=\{1, 2, 3, 4, 5, 6\}$，边集$E=\{(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)\}$。在无向图中，边$(u, v)$和边$(v, u)$是一样的，因此只要记录一个就行了。简而言之，对称。
有向图
也很好理解，就是加上了方向性，顶点$(u, v)$之间的关系和顶点$(v,u)$之间的关系不同，后者或许不存在。例如，地图应用中必须存储单行道的信息，避免给出错误的方向。
加权图：
权：与图的边或弧相关的数叫做权。
与加权图对应的就是无权图，或叫等权图。如果一张图不含权重信息，我们就认为边与边之间没有差别。不过，具体建模的时候，很多时候都需要有权重，比如对中国重要城市间道路联系的建模，总不能认为从北京去上海和从北京去广州一样远(等权)。
还有很多细化的概念，比如：无向图中，任意两个顶点间都有边，称为无向完全图；加权图起一个新名字，叫网(network)……然而，如无必要，毋增实体。
两个重要关系：
邻接(adjacency)：邻接是两个顶点之间的一种关系。如果图包含$(u,v)$，则称顶点$v$与顶点$u$邻接。当然，在无向图中，这也意味着顶点$u$与顶点$v$邻接。
关联(incidence)：关联是边和顶点之间的关系。在有向图中，边$(u,v)$从顶点$u$开始关联到$v$，或者相反，从$v$关联到$u$。注意，有向图中，边不一定是对称的，有去无回是完全有可能的。细化这个概念，就有了顶点的入度(in-degree)和出度(out-degree)。无向图中，顶点的度就是与顶点相关联的边的数目，没有入度和出度。在有向图中，我们以图1-2为例，顶点10有2个入度，$3\rightarrow10$，$11\rightarrow10$，但是没有从10指向其它顶点的边，因此顶点10的出度为0。
路径(path)：依次遍历顶点序列之间的边所形成的轨迹。注意，依次就意味着有序，先1后2和先2后1不一样。
简单路径: 没有重复顶点的路径称为简单路径。说白了，这一趟路里没有出现绕了一圈回到同一点的情况，也就是没有环。
环/回路：包含相同的顶点两次或者两次以上。图1-3中的顶点序列$<1,2,4,3,1>$，1出现了两次，当然还有其它的环，比如$<1,4,3,1>$。
简单回路/简单环：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
无环图：没有环的图，其中，有向无环图有特殊的名称，叫做DAG(Directed Acyline Graph)（最好记住，DAG具有一些很好性质，比如很多动态规划的问题都可以转化成DAG中的最长路径、最短路径或者路径计数的问题）。
下面这个概念很重要：
两个连通分支：
连通的：无向图中每一对不同的顶点之间都有路径。如果这个条件在有向图里也成立，那么就是强连通的。
连通分量：无向图中的极大连通子图。
两点强连通：在有向图G中，如果两点互相可达
强连通图：如果有向图G的每两个顶点都强连通（任意两点互相可达），称G是一个强连通图。
强连通分量：非强连通有向图的极大强连通子图，称为强连通分量(strongly connected components)。
关节点(割点)：某些特定的顶点对于保持图或连通分支的连通性有特殊的重要意义。如果移除某个顶点将使图或者分支失去连通性，则称该顶点为关节点。（在某图中，若删除顶点V以及V相关的边后，图的一个连通分量分割为两个或两个以上的连通分量，则称顶点V为该图的一个关节点）。
桥(割边)：和关节点类似，删除一条边，就产生比原图更多的连通分支的子图，这条边就称为割边或者桥。
双连通图：在无向连通图中，如果删除该图的任何一个结点都不能改变该图的连通性，则该图为双连通的无向图。个人理解就是一个双连通图没有割点，没有桥的图。
1.2 一些有趣的图概念
这一部分属于图论的内容，基础图算法不会用到，但是我觉得挺有意思的，小记如下。【这部分我没看，照搬过来了】
同构4：图看起来结构不一样，但它是一样的。假定有$G_1$和$G_2$，那么你只要确认对于$G_1$中的所有的两个相邻点$a$和$b$，可以通过某种方式$f$映射到$G_2$，映射后的两个点$f(a)$、$f(b)$也是相邻的。换句话说，当两个简单图同构时，两个图的顶点之间保持相邻关系的一一对应。
图1-7就展示了图的同构，这里顶点个数很少判断图的同构很简单。我们可以把v1看成u1，自然我们会把u3看出v3。用数学的语言就是$f(u_1)=v_1$，$f(u_3)=v_3$。u1的另外一个连接是到u2，v1的另外一个连接是到v4，不难从相邻顶点的关系验证$f(u_2)=v_4$，$f(u_4)=v_2$。
欧拉回路(Euler Circuit)：小学数学课本上的哥尼斯堡七桥问题，能不能从镇里的某个位置出发不重复的经过所有桥(边)并且返回出发点。这也就小学的一笔画问题，欧拉大神解决里这个问题，开创了图论。结论很简单：至少2个顶点的连通多重图存在欧拉回路的充要条件是每个顶点的度都是偶数。证明也很容易，大家有兴趣可以阅读相关资料。结论也很好理解，从某个起点出发，最后要回起点，中间无论路过多少次起点，都会再次离开，进、出的数目必然相等，故一定是偶数。
哈密顿回路(Hamilton Circuit)：哈密顿回路条件就比欧拉回路严格一点，不能重复经过点。你可能会感到意外，对于欧拉回路，我们可以轻而易举地回答，但是我们却很难解决哈密顿回路问题，实际上它是一个NP完全问题。这个术语源自1857年爱尔兰数学家威廉·罗万·哈密顿爵士发明的智力题。哈密顿的智力题用到了木质十二面体（如图1-8(a)所示，十二面体有12个正五边形表面）、十二面体每个顶点上的钉子、以及细线。十二面体的20个顶点用世界上的不同城市标记。智力题要求从一个城市开始，沿十二面体的边旅行，访问其他19个城市，每个恰好一次，最终回到第一个城市。
因为作者不可能向每位读者提供带钉子和细线的木质十二面体，所以考虑了一个等价的问题：对图1-8(b)的图是否具有恰好经过每个顶点一次的回路？它就是对原题的解，因为这个平面图同构于十二面体顶点和边。
著名的旅行商问题(TSP)要求旅行商访问一组城市所应当选取的最短路线。这个问题可以归结为求完全图的哈密顿回路，使这个回路的边的权重和尽可能的小。同样，因为这是个NP完全问题，最直截了当的方法就检查所有可能的哈密顿回路，然后选择权重和最小的。当然这样效率几乎难以忍受，时间复杂度高达$O(n!)$。在实际应用中，我们使用的启发式搜索等近似算法，可以完全求解城市数量上万的实例，并且甚至能在误差1%范围内估计上百万个城市的问题。
关于旅行商问题目前的研究进展，可以到http://www.math.uwaterloo.ca/...。
1.3 小结
以为可以一带而过，结果写了那么多。也没什么好总结的了，当然这些也至是图论概念的一小部分，还有一些图可能我们以后也会见到，比如顺着图到网络流，就会涉及二分图，不过都很好理解，毕竟有图。
图的存储结构
1、数组（邻接矩阵）
2、邻接表
3、十字链表
4、邻接多种表
