离散数学简单图的判断,什么叫简单无向图
根据性质，图可以分为有向图和有向图。 本文首先介绍有向图，然后介绍有向图。 研究图是因为图在生活中被广泛使用。
无向图
图由几个顶点(Vertices )和边(edge )相互连接而成。 边只由两个顶点连接而没有方向的图称为无向图。 在讨论图之前，有几个定义需要澄清。 下图显示了图中基本属性的含义，这里不多赘述。
图的API显示
在研究图之前，我们需要选择合适的数据结构来表示图。 有时，它经常被我们的直觉所欺骗。 如下图所示，这两个其实是一样的。 这其实也是一个研究问题，就是如何判断图的形态。
要在计算机中处理图，请抽象出表示下图的API。
Graph的API的实现可以用多种不同的数据结构表示，最基本的是维持一系列边的集合。
也可以使用邻接矩阵表示，如下所示：
也可以使用相邻列表表示如下：
这样的话，灵活性很高，如果用邻接列表表示的话，就可以定义以下的数据结构来表示Graph对象。
公共类图形
{private readonly int verticals； //顶点数
私有输入边缘； //边数
私有列表[ ]调整； //顶点连接列表
公共图形(int vertical ) )。
{this.verticals=vertical； this.edges=0；
adjacency=new List[vertical]； for(intv=0； v vertical； v )
{
adjacency[v]=new List (；
}
}公共集成电路() )
{returnverticals；
}public intGetEdges () )
{返回边缘；
} publicvoidaddedge (intverticalstart，intverticalEnd ) )。
{
adjacency [ vertical start ].add (vertical end；
adjacency [ vertical end ].add (vertical start；
edges；
} publiclistgetadjacency (intv etical ) )。
{returnadjacency[vetical]；
}
}
view代码
采用上述三种表现方式的效率如下。
在研究了图的表示之后，让我们来看看图中重要的算法——深度优先算法。
深度优先算法
在谈深度优先算法之前，让我们先看一下迷宫搜索问题。 迷宫与图的对应关系如下所示。 迷宫中的每个交点表示图的顶点，每个通道对应一条边。 迷宫搜索可以采用Trmaux绳索搜索法。 也就是说：
把绳子放在后面
在所有访问过的地方放置绳子标志访问过的十字路口和通道
遇到访问过的地方，沿着绳子回到以前没有访问过的地方：
该图标如下所示：
下面是迷宫探索的小视频：
深度优先搜索算法模拟迷宫搜索。 实际的图表处理算法通常将图表的显示与图表的处理逻辑分开。 算法的总体设计模式如下。
创建Graph对象
将Graph对象传递给图形算法处理对象，如Paths对象
查询处理后的结果以获取信息
以下是深度优先的基本代码，可以看到递归调用dfs方法，以在调用之前确定是否访问了该节点。
publicclassdepthfirstsearch { private boolean [ ]标记； //marked[v]=is there an s-v path？
私有计数； //number of vertices connected to s
publicdepthfirstsearch(graphg，ints ) {
marked=newBoolean[g.v(] () ]；
DFS(g，s )；
/p>
}//depth first search from v
private void dfs(Graph G, intv) {
count++;
marked[v]= true;for (intw : G.adj(v)) {if (!marked[w]) {
dfs(G, w);
}
}
}public boolean marked(intv) {returnmarked[v];
}public intcount() {returncount;
}
}
View Code
试验一个算法最简单的办法是找一个简单的例子来实现。
深度优先路径查询
有了这个基础，我们可以实现基于深度优先的路径查询，要实现路径查询，我们必须定义一个变量来记录所探索到的路径。所以在上面的基础上定义一个edgesTo变量来后向记录所有到s的顶点的记录，和仅记录从当前节点到起始节点不同，我们记录图中的每一个节点到开始节点的路径。为了完成这一日任务，通过设置edgesTo[w]=v，我们记录从v到w的边，换句话说，v-w是最后一条从s到达w的边。edgesTo[]其实是一个指向其父节点的树。
public classDepthFirstPaths
{private bool[] marked;//记录是否被dfs访问过
private int[] edgesTo;//记录最后一个到当前节点的顶点
private int s;//搜索的起始点
public DepthFirstPaths(Graph g, ints)
{
marked= newbool[g.GetVerticals()];
edgesTo= new int[g.GetVerticals()];this.s =s;
dfs(g, s);
}private void dfs(Graph g, intv)
{
marked[v]= true;
foreach (intw in g.GetAdjacency(v))
{if (!marked[w])
{
edgesTo[w]=v;
dfs(g,w);
}
}
}public bool HasPathTo(intv)
{returnmarked[v];
}public Stack PathTo(intv)
{if (!HasPathTo(v)) return null;
Stack path = new Stack();for (int x = v; x!=s; x=edgesTo[x])
{
path.Push(x);
}
path.Push(s);returnpath;
}
}
View Code
上图中是黑色线条表示深度优先搜索中，所有定点到原点0的路径，他是通过edgeTo[]这个变量记录的，可以从右边可以看出，他其实是一颗树，树根即是原点，每个子节点到树根的路径即是从原点到该子节点的路径。下图是深度优先搜索算法的一个简单例子的追踪。
广度优先算法
通常我们更关注的是一类单源最短路径的问题，那就是给定一个图和一个源S，是否存在一条从s到给定顶点v的路径，如果存在，找出最短的那条(这里最短定义为边的条数最小)。深度优先算法是将未被访问的节点放到一个栈中(stack)，虽然在上面的代码中没有明确在代码中写stack，但是递归间接的利用递归堆实现了这一原理。和深度优先算法不同，广度优先是将所有未被访问的节点放到了队列中。其主要原理是：
将s放到FIFO中，并且将s标记为已访问
重复直到队列为空
移除最近最近添加的顶点v
将v未被访问的邻接点添加到队列中
标记他们为已经访问
广度优先是以距离递增的方式来搜索路径的。
classBreadthFirstSearch
{privatebool[] marked;private int[] edgeTo;private int sourceVetical;//Source vertical
public BreadthFirstSearch(Graph g, ints)
{
marked=newbool[g.GetVerticals()];
edgeTo=new int[g.GetVerticals()];this.sourceVetical =s;
bfs(g, s);
}private void bfs(Graph g, ints)
{
Queue queue = new Queue();
marked[s]= true;
queue.Enqueue(s);while (queue.Count()!=0)
{int v =queue.Dequeue();
foreach (intw in g.GetAdjacency(v))
{if (!marked[w])
{
edgeTo[w]=v;
marked[w]= true;
queue.Enqueue(w);
}
}
}
}public bool HasPathTo(intv)
{returnmarked[v];
}public Stack PathTo(intv)
{if (!HasPathTo(v)) return null;
Stack path = new Stack();for (int x = v; x!=sourceVetical; x=edgeTo[x])
{
path.Push(x);
}
path.Push(sourceVetical);returnpath;
}
}
View Code
广度优先算法的搜索步骤如下：
广度优先搜索首先是在距离起始点为1的范围内的所有邻接点中查找有没有到达目标结点的对象，如果没有，继续前进在距离起始点为2的范围内查找，依次向前推进。
连通分量
使用深度优先遍历计算图的所有连通分量。
packageGraph;public classCC {private boolean[] marked;private int[] id;private intcount;public CC(Graph graph, ints) {
marked= new boolean[graph.V()];
id= new int[graph.V()];for (int i =0; i < graph.V(); i++) {if (!marked(i)) {
dfs(graph, i);
count++;
}
}
}private void dfs(Graph graph, ints) {
marked[s]= true;
id[s]=count;for (intW : graph.adj(s)) {if(marked(W))
dfs(graph, W);
}
}//判断v和W是否连通
public boolean connected(int v, intw) {return id[v] ==id[w];
}//返回W所在的连通分量的标识符
public int id(intv) {returnid[v];
}public boolean marked(intw) {returnmarked[w];
}//连通分量
public intcount() {returncount;
}
}
View Code
总结
本文简要介绍了无向图中的深度优先和广度优先算法，这两种算法时图处理算法中的最基础算法，也是后续更复杂算法的基础。其中图的表示，图算法与表示的分离这种思想在后续的算法介绍中会一直沿用，下文将讲解无向图中深度优先和广度优先的应用，以及利用这两种基本算法解决实际问题的应用。