cad制图简单趣味图片,简单基础平面图
有向图是最简单的图模型，边只是两个顶点之间的连接。 连接v和w的边用v-w的符号表示，而w-v是这一边的另一种表示方式。
特殊的图。 自循环：连接顶点和自身的边；
连接同一对顶点的两条边称为平行边。
简单术语介绍
当两个顶点由一条边连接时，我们称这两个顶点相邻，称这一边依赖这两个顶点。 顶点的度数是依赖于顶点的边的总数。 子图是由图表中所有边的子集以及它们所依赖的所有顶点组成的图表。
路径是由边依次连接的一系列顶点。 简单路径是没有重复顶点的路径。 回路至少包含一条边，且路径的起点和终点相同。 简单循环是不包含重叠顶点和边的循环(除了“起点”和“终点”必须相同外)。 或者，循环的长度是其中包含的边的数量。
如果存在从一个顶点到另一个任意顶点的路径，则此图称为连通图。 一个无连通图由几个连通部分组成，它们都是其极大连通部分图。 树是一个无圈的连通图。 不互相连接的树的集合叫做森林。 连通图的生成树是其子图，包含图的所有顶点，是一棵树。 图中的生成树林是所有合并子图的生成树的集合。 一棵树造一片树林
树的数学性质
且，只有当包含v个节点图g满足以下5个条件中的任意一个时，g才是具有V-1条边且不含环的树
g有V-1的边，连接着
g已连接，但删除其中一条边缘将无法连接
g是无环的，但添加其中一条边会生成环
g中的任意顶点对之间只存在一个简单路径。
图的密度是指已连接的顶点对在所有连接的顶点对中所占的百分比。 在稀疏图中，连接的顶点对很少； 另一方面，在稠密图中，顶点对之间只有很少一部分没有边连接。 一般来说，如果一个图中不同边的数量在顶点总数v的小常数倍以内，则可以认为该图是稀疏的。
二分图是一幅所有节点均可分为两部分的图，其中图的各边连接的两个顶点分别属于不同的部分。
表示有向图的数据类型
要开发处理图问题的各种算法，首先来看看定义了图基本操作的API有向图的API
最常见的图形处理代码
计算v的度数
publicstaticintdegree(graphg，int v ) {
int degree=0；
for(intw:g.adj ) v ) )德格利；
返回降级；
}
计算所有顶点的最大度数
publicstaticintmaxdegree{
int max=0；
for(intv=0； v G.V (； v )
if(Degree(g，v ) max ) ) ) ) ) ) )。
max=degree(g，v )；
返回最大；
}
计算所有顶点的平均度数
publicstaticdoubleavggegree{
return 2.0 * G.E ()/G.V )；
}
计算自循环的个数
publicstaticintnumberofselfloops {
int count=0；
for(intv=0； v G.V (； v )
for(intw:g.adj ) v ) )
if(v==w ) count；
返回计数/2； //每边被记录了两次
}
图邻表的字符串表示(Graph的实例方法) )。
公共字符串
String s=V 'vertices，' E ' edges\n '；
for(intv=0； v； v ) {
s =v ': '；
for(intw:this.adj ) ) v ) )
s =w ' '；
s ='\n '；
}
返回s；
}
图的几种表示方法
这里必须面对的问题是用什么样的方式(数据结构)表示图、实现API，这包括以下两个要求。 必须为在APP中可能遇到的各种类型的图留出足够的空间；
Graph实例方法的实现一定是——它们是开发处理图的各种用例的基础。
虽然这些要求很模糊，但它们有助于您在三种图的显示方式之间进行选择。 邻接矩阵。 可以使用v乘以v的布尔矩阵。 如果存在连接在顶点v和顶点w之间的边缘，则定义v行w列的元素为true。 该表示方法一般不符合最初条件——的包含数百万个顶点的图，V^2个布尔值所需的空间无法满足。
边缘数组。 我们可以
使用一个Edge类，它含有两个int实例变量。这种表示方法很简洁但不满足第二个条件——要实现adj()需要检查图的所有边。
邻接表数组。我们可以使用一个以顶点为索引的列表数组，其中的每个元素都是和该顶点相邻的顶点列表，如图。这种数据结构能够同时满足上面两点。邻接表数组示意(无向图)
邻接表的数据结构
非稠密图的标准表示称为邻接表的数据结构，它将每个顶点的所有相邻顶点都保存在该顶点对应的元素所指向的一张链表中。我们使用这个数组就是为了快速访问给定顶点的邻接顶点列表。我们使用Bag这个抽象数据类型来实现这个链表，这样我们就可以在常数时间内添加新的边或遍历任意顶点的所有相邻顶点。
这种Graph的实现的性能有如下特点：使用的空间可V+E成正比
添加一条边所需要的时间为常数
遍历顶点v的所有相邻顶点所需要的时间和v的度数成正比(处理每个相邻顶点所需的时间为常数)
Graph数据类型
public class Graph {
private final int V;//顶点数目
private int E;//边的数目
private Bag[] adj;//邻接表
public Graph(int V) {
this.V = V;this.E = 0;
adj = (Bag[]) new Bag[V];//创建邻接表
for(int v = 0; v < V; v++)//将所有链表初始化为空
adj[v] = new Bag();
}
public Graph(In in) {
this(in.readInt());//读取V并将图初始化
int E = in.readInt();//读取E
for(int i = 0; i < E; i++ ) {
//添加一条边
int v = in.readInt();//读取一个顶点
int w = in.readInt();//读取另一个顶点
addEdge(v,w);//添加一条连接他们的边
}
}
public int V(){return V;}
public int E(){return E;}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
E++;
}
public Iterable adj(int v){
return adj[v];
}
}
这份Graph的实现使用了一个由顶点索引的整数链表数组。每条边都会出现两次，即当存在一条连接v与w的边时，w会出现在v的链表中，v也会出现在w的链表中。第二个构造函数从输入流中读取一幅图，开头是V，然后是E，再然后是一列整数对，大小在0到V-1之间
实际操作情况
在实际应用中还有一些操作可能是很有用的，例如添加一个顶点
删除一个顶点
实现这些操作的一种方法是扩展之前的API，使用符号表(ST)来代替由顶点索引构成的数组(这样修改之后就不需要约定定点名必须是整数了)。删除一条边
检查图是否含有边v-w
要实现这些方法可能需要使用SET来替代Bag来实现邻接表。我们称这种方法为邻接集。典型Graph实现的性能复杂度