什么是图表定义及基本术语、C语言邻接矩阵示例代码

1.什么是图

图论（graph theory）是以图为研究对象的数学分支。

图论本身就是应用数学的一部分。历史上，图论是由多位数学家独立建立的。图论最早的书面记录出现在欧拉 1736 年的论文中，即著名的柯尼斯堡问题（七桥问题）。

2。图的定义

图 G 是一个元组，即偶数阶 ，或写为 G=，其中 V 是称为顶点集的有限非空集G中的V中的元素称为顶点或结； E 称为 G 的边集，所有边 ei 都属于 E 并在 v 中有与其对应的节点，并且 ei 称为 G 的一条边。

3。图的基本概念

l 无向图：每条边都是无向边的图。

l 有向图：每条边都是有向边的图。

l 混合图：如果图中某些边是有向边，其他边是无向边，则该图是混合图。

l 有限图：点集和边集是有限集的图。

l 空图：边集为空集的图。

l 平凡图：只有一个节点且没有边的图。

l 关联：如果存在 ei=(u,v) 并且 ei 属于 E，则称 u 与 v 关联。

l 孤立点：没有边关联的点。

l 自环：如果连接到一条边的两个节点匹配，则该边称为自环。

l邻接：由同一条边连接的两个点称为邻接；连接到同一点并且相邻（或相邻）的两条边。

4。两句话：

l 推论：每个图中必须有偶数个具有奇数度数的点。

l 推论：这意味着所有点的度数之和等于外部度数之和。

（这个比较容易理解，就像你问世界上有更多的上坡还是下坡，答案是一样的）

从上面的概念，我们可以看到一棵树或者一片森林是一种特殊的图像。

5。最简单的存储——邻接矩阵

邻接矩阵的英文名称为Adjacency Matrix。其形式为bool adj[n][n]，其中n是节点数，adj[i][j]表示i和j之间是否存在边。

如果边有值，也可以直接使用 int adj[n][n] 直接存储边的权重。

它的优点是可以在O(1)时间内检测是否存在边缘，但缺点是占用O(n^2)空间。对于稀疏图（边的数量相对于点数的平方来说比较少），使用邻接矩阵来存储它的成本很高。

代码可以表示为（假设每边长度为1）：