算法级数15天快速第十四天图

今天给大家分享一张照片，这是一种复杂的非线性数据结构，其中的原因是复杂的因为他们的数据元素之间的关系是任意的，而不是一棵树，由几个定理的框架，元素之间的关系是很明显的，一个广泛的图表的使用，如网络爬虫的短路径，等等，但我们也不害怕，

越是复杂的东西，我们农民代码的核心竞争力就越强。

既然你想学习图形，你就必须遵守游戏规则。

第一：概念

一个图由一组顶点和一组边组成。注：g =（v，e）；

无向图

图的边缘没有方向，所以（V1，V2）边缘自然等于（V2，V1），无向图的表示一般是圆括号。
有向图

图的边有一个方向，它不等于图的边，而图的表示一般用点括号表示。
邻接点

边缘上的两个顶点称为邻接点，如（V1，V2），（V1，V3），（V1，V5），只是在有向图中有边和边。

例如，概念，V3的边缘是V5和V3外面V2，V1、V4。
度

这和树的度数是一样的，但在地图上也分为两种类型，据信是可以理解的。
完全图

每两个顶点都有一个边，这是一个完美的表达式，自然可以计算出边的个数。

无向图：边= n（n-1） 2；

有向图：边= n（n-1）；由于有向图是边，所以它必须在原x2的基础上。
子图

如果G1的所有顶点和边都在G2中，那么G1就是G2的子图，更不用说了。
路径、路径长度和循环（这些概念更重要）

路径：如果有一个顺序的VM和越南之间的顶点。这意味着VM VN是一个路径。

路径长度：路径中的边数。

简单路径：如果路径的顶点不重复，则它是一个简单的路径。

循环：如果路径的第一个顶点与最后一个顶点相同，则为循环。

简单循环：第一个顶点与最后一个顶点相同，而其他顶点不重复的循环是一个简单的循环。
连通图与连通图（无向图）

连通图：在无向图中，任意两个顶点连接和连接图，如V1、V2、V4。

连通分量：极性大连极点的无向图是连通分量，一般连通分量是图本身，除非是非连通图，

例如，下面的图是两个连通的部分。
强连通图与强连通图（有向图）

这里主要关注的方向是，V4可以到V3，而V3不到V4，所以它不能被称为一个强连通图。
网络

边上有权的图叫做网，很有意思，是吗。
二：存储

图形存储的常用方法是邻接矩阵和邻接表。

邻接矩阵：操作是使用两个数组，一个数组来保存顶点的信息，一个二维数组使用边的信息。

缺点是占用空间更大。

邻接表：一种改进的邻接矩阵。缺点是判断两个顶点之间是否有一个边是不方便的，但它节省了空间。
三：创建图表

这里我们使用邻接矩阵来保存图，一般的操作是：（1）创建和遍历。

复制代码代码如下所示：
该#区域邻接矩阵的结构图
X
图邻接矩阵x的结构
X
matrixgraph公共类
{
保存顶点信息
公共字符串{ }顶点；

保存侧信息
公共边缘；

深搜索和宽搜索遍历标记
公共istrav bool { }；

顶点的数量
public int vertexnum；

边缘数
public int edgenum；

图表类型
public int图类型；

X
公共存储容量初始化
X
X
X
X
公共matrixgraph（int，int vertexnum，edgenum图类型，int）
{
this.vertexnum = vertexnum；
this.edgenum = edgenum；
this.graphtype =图类型；

顶点=新的字符串vertexnum } {；
边缘=新国际vertexnum vertexnum {，}；
istrav =新vertexnum bool { }；
}

}
#铁心端部定点
创建一个图形很容易，让用户输入一些边、点、权重来建立一个图表。

复制代码代码如下所示：
#区域图的创建
X
创建映射
X
X
公共matrixgraph creatematrixgraph（）
{
console.writeline（请输入的创作图，顶点的边数，该数是否是一个无向图（0,1），已由一个逗号分开。）；

var = console.readline（initdata）。Split（），选择（我= int（我）（解析）。列出）；

matrixgraph图=新matrixgraph（initdata { 0 }，{ 1 } initdata，initdata { 2 }）；

console.writeline（请输入每个顶点信息：）；

为（int i = 0；i < graph.vertexnum；i++）
{
控制台。写入（）+（i + 1）+ 顶点是：；

VaR单= console.readline（）；

将顶点信息放入集合中
图.顶点{ } =单个；
}

console.writeline（请输入构成两个顶点的边和权重，用逗号分隔。；

为（int i = 0；i < graph.edgenum；i++）
{
控制台。写入（）+（i + 1）+边缘：；

InitData = Console.ReadLine (.Split) ('').Select (J = int.Parse (J)) (.ToList);

起始= initdata { 0 }；
INT端= initdata { 1 }；
Int weight = initData{2};

指定位置分配/矩阵的坐标
图.边缘{开始- 1，结束- 1 } =重量；

如果图是无方向的，那么数据是两个，四象限对称的。
如果（graph.graphtype = 1）
{
图.边缘{ - 1，开始- 1 } =重量；
}
}

返回图；
}
#铁心端部定点
BFS

我们如何优先考虑下面的模式结构事实上，我们只对我们定义中的规则和规则进行了广泛的探索有深刻的理解。

次访问，您可以存储顶点的下标在strav { }的布尔数组来确定节点是否被访问。

第一步：首先，我们选择的是不是从istrav数组访问的节点，如V1。

第二步：访问V1邻居V2、V3、V5，并将这三个节点标记为真。

第三步：在第二步之后，我们开始访问V2邻居V1、V3，但它们都被访问了。

第四步：我们开始从V3在第二步结束访问他的邻居V2，V1、V4、V5，它是好的，是不是在这个时候访问v4，然后标记。

第五步：我们访问V1、V3、V5、V4的邻居，但他们都去过了。

第六步：在一些图中，我们不能通过顶点的宽度优先遍历所有顶点。当我们重复（1-5）步骤时，我们最终可以实现广度优先遍历。
复制代码代码如下所示：
#区域广度优先
X
X广度优先
X
X
公共无效BFSTraverse（matrixgraph图）
{
默认情况下初始化访问令牌。
为（int i = 0；i < graph.vertexnum；i++）
{
图。istrav {我} = false；
}

遍历每个顶点
为（int i = 0；i < graph.vertexnum；i++）
{
/ /广度遍历访问过的顶点
如果（！图istrav {我}）。
{
（参考图，我BFSM）；
}
}
}

X
x广度遍历算法
X
X
public void BFSM（REF matrixgraph图，int顶点）
{
这里是队列系统
队列=新队列（）；

挂起/顶点
Enqueue（顶点）队列；

这次访问被标记为
图istrav {点} =真；

输出顶点
控制台。写入（++图。顶点{ }）；

相邻顶点点/广度遍历
而（queue.count！= 0）
{
VaR温度=队列。Dequeue（）；

横坐标 /遍历矩阵
为（int i = 0；i < graph.vertexnum；i++）
{
如果（！图。istrav {我}图。边{温度}，我！= 0）
{
图istrav { } =真实的我；

Enqueue（我）队列；

/ /输出未访问过的顶点
控制台。写入（++图。顶点{ }）；
}
}
}
}
#铁心端部定点
深度优先

这是同一个人物，我们看如何实现深度优先，深度优先，作为不屈的英雄，跟随可以进入，或者脱离原则。

第一步是选择不是从istrav数组访问的节点，如V1。

第二步：邻接点和已访问V1，直到树回来了，V1、V2、V3、V4、V5，V5，访问的邻接点V1，V1是参观，

此时对回溯的访问达到V1。

第三步：类似地，在一些图中，我们不能遍历顶点的深度优先遍历所有顶点。此时，我们重复（1-2）步骤完成深度优先遍历。
复制代码代码如下所示：
#区深度优先
X
先改变深度
X
X
公共无效DFSTraverse（matrixgraph图）
{
默认情况下初始化访问令牌。
为（int i = 0；i < graph.vertexnum；i++）
{
图。istrav {我} = false；
}

遍历每个顶点
为（int i = 0；i < graph.vertexnum；i++）
{
/ /广度遍历访问过的顶点
如果（！图istrav {我}）。
{
有限状态机（参考图，我）；
}
}
}

递归#区域深度的具体算法
X
x中递归算法的深度
X
X
X
公共无效的状态机（参考matrixgraph图，int顶点）
{
控制台。写入（++图。顶点{ }）；

标记为访问
图istrav {点} =真；

六点遍历
为（int i = 0；i < graph.vertexnum；i++）
{
如果（图。istrav {我} {假=图。边的顶点，我} = 0！）
{
深递归
有限状态机（参考图，我）；
}
}
}
#铁心端部定点
#铁心端部定点
最后是总的代码。

复制代码代码如下所示：
使用系统；
使用system.collections.generic；
使用LINQ系统；
使用系统文本；

命名空间matrixgraph
{
程序公开课
{
static void main（String { } args）
{
matrixgraphmanager经理=新matrixgraphmanager（）；

创建地图
matrixgraph图= manager.creatematrixgraph（）；

Manager.OutMatrix（图）；

控制台。写入（宽度递归：）；

manager.bfstraverse（图）；

控制台。写入（）depth recursion: t);

manager.dfstraverse（图）；

Console.ReadLine（）；

}
}

该#区域邻接矩阵的结构图
X
图邻接矩阵x的结构
X
matrixgraph公共类
{
保存顶点信息
公共字符串{ }顶点；

保存侧信息
公共边缘；

深搜索和宽搜索遍历标记
公共istrav bool { }；

顶点的数量
public int vertexnum；

边缘数
public int edgenum；

图表类型
public int图类型；

X
公共存储容量初始化
X
X
X
X
公共matrixgraph（int，int vertexnum，edgenum图类型，int）
{
this.vertexnum = vertexnum；
this.edgenum = edgenum；
this.graphtype =图类型；

顶点=新的字符串vertexnum } {；
边缘=新国际vertexnum vertexnum {，}；
istrav =新vertexnum bool { }；
}

}
#铁心端部定点

X
只是操作类的一张地图
X
matrixgraphmanager公共类
{
#区域图的创建
X
创建映射
X
X
公共matrixgraph creatematrixgraph（）
{
console.writeline（请输入的创作图，顶点的边数，该数是否是一个无向图（0,1），已由一个逗号分开。）；

var = console.readline（initdata）。Split（），选择（我= int（我）（解析）。列出）；

matrixgraph图=新matrixgraph（initdata { 0 }，{ 1 } initdata，initdata { 2 }）；

console.writeline（请输入每个顶点信息：）；

为（int i = 0；i < graph.vertexnum；i++）
{
控制台。写入（）+（i + 1）+ 顶点是：；

VaR单= console.readline（）；

将顶点信息放入集合中
图.顶点{ } =单个；
}

console.writeline（请输入构成两个顶点的边和权重，用逗号分隔。；

为（int i = 0；i < graph.edgenum；i++）
{
控制台。写入（）+（i + 1）+边缘：；

initdata = console.readline（。分）（'），选择（J = int（J）（解析）。列出）；

起始= initdata { 0 }；
INT端= initdata { 1 }；
体重= initdata { 2 }；

指定位置分配/矩阵的坐标
图.边缘{开始- 1，结束- 1 } =重量；

如果图是无方向的，那么数据是两个，四象限对称的。
如果（graph.graphtype = 1）
{
图.边缘{ - 1，开始- 1 } =重量；
}
}

返回图；
}
#铁心端部定点

#输出矩阵数据区域
X
公共数据输出矩阵
X
X
公共无效outmatrix（matrixgraph图）
{
为（int i = 0；i < graph.vertexnum；i++）
{
为（j = 0；J < graph.vertexnum；j++）
{
控制台。写入（图形；
}
包装
console.writeline（）；
}
}
#铁心端部定点

#区域广度优先
X
X广度优先
X
X
公共无效BFSTraverse（matrixgraph图）
{
默认情况下初始化访问令牌。
为（int i = 0；i < graph.vertexnum；i++）
{
图。istrav {我} = false；
}

遍历每个顶点
为（int i = 0；i < graph.vertexnum；i++）
{
/ /广度遍历访问过的顶点
如果（！图istrav {我}）。
{
（参考图，我BFSM）；
}
}
}

X
x广度遍历算法
X
X
public void BFSM（REF matrixgraph图，int顶点）
{
这里是队列系统
队列=新队列（）；

挂起/顶点
Enqueue（顶点）队列；

这次访问被标记为
图istrav {点} =真；

输出顶点
控制台。写入（++图。顶点{ }）；

相邻顶点点/广度遍历
而（queue.count！= 0）
{
VaR温度=队列。Dequeue（）；

横坐标 /遍历矩阵
为（int i = 0；i < graph.vertexnum；i++）
{
如果（！图。istrav {我}图。边{温度}，我！= 0）
{
图istrav { } =真实的我；

Enqueue（我）队列；

/ /输出未访问过的顶点
控制台。写入（++图。顶点{ }）；
}
}
}
}
#铁心端部定点

#区深度优先
X
先改变深度
X
X
公共无效DFSTraverse（matrixgraph图）
{
默认情况下初始化访问令牌。
为（int i = 0；i < graph.vertexnum；i++）
{
图。istrav {我} = false；
}

遍历每个顶点
为（int i = 0；i < graph.vertexnum；i++）
{
/ /广度遍历访问过的顶点
如果（！图istrav {我}）。
{
有限状态机（参考图，我）；
}
}
}

递归#区域深度的具体算法
X
x中递归算法的深度
X
X
X
公共无效的状态机（参考matrixgraph图，int顶点）
{
控制台。写入（++图。顶点{ }）；

标记为访问
图istrav {点} =真；

六点遍历
为（int i = 0；i < graph.vertexnum；i++）
{
如果（图。istrav {我} {假=图。边的顶点，我} = 0！）
{
/ /深度递归
有限状态机（参考图，我）；
}
}
}
#铁心端部定点
#铁心端部定点

}
}
我们在代码中建立了以下图表。