【各种东拼西凑来的】
图(Graph)是由顶点和连接顶点的边构成的离散结构。在计算机科学中，图是最灵活的数据结构之一，很多问题都可以使用图模型进行建模求解。例如：生态环境中不同物种的相互竞争、人与人之间的社交与关系网络、化学上用图区分结构不同但分子式相同的同分异构体、分析计算机网络的拓扑结构确定两台计算机是否可以通信、找到两个城市之间的最短路径等等。
图的结构很简单，就是由顶点$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、邻接多种表