图的简单认识
**1.顶点(vertex):**图中的数据元素,如图一。
**2.边(edge):**图中连接这些顶点的线,如图一。
所有的顶点构成一个顶点集合,所有的边构成边的集合,一个完整的图结构就是由顶点集合和边集合组成。图结构在数学上记为以下形式:
G=(V,E) 或者 G=(V(G),E(G))
其中 V(G)表示图结构所有顶点的集合,顶点可以用不同的数字或者字母来表示。E(G)是图结构中所有边的集合,每条边由所连接的两个顶点来表示。
图结构中顶点集合V(G)不能为空,必须包含一个顶点,而图结构边集合可以为空,表示没有边。
图的基本概念
1.无向图
如果一个图结构中,所有的边都没有方向性,那么这种图便称为无向图。典型的无向图,如图二所示。由于无向图中的边没有方向性,这样我们在表示边的时候对两个顶点的顺序没有要求。例如顶点VI和顶点V5之间的边,可以表示为(V2, V6),也可以表示为(V6,V2)。
对于图二无向图,对应的顶点集合和边集合如下:
V(G)= {V1,V2,V3,V4,V5,V6}
E(G)= {(V1,V2),(V1,V3),(V2,V6),(V2,V5),(V2,V4),(V4,V3),(V3,V5),(V5,V6)}
2.有向图
一个图结构中,边是有方向性的,那么这种图就称为有向图,如图三所示。由于图的边有方向性,我们在表示边的时候对两个顶点的顺序就有要求。我们采用尖括号表示有向边,例如<V2,V6>表示从顶点V2到顶点V6,而<V6,V2>表示顶点V6到顶点V2。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ylFPv8ks-1581605615956)(images/824470-20180529220933054-293758125.png)]
图三 有向图
对于图三有向图,对应的顶点集合和边集合如下:
V(G)= {V1,V2,V3,V4,V5,V6}
E(G)= {<V2,V1>,<V3,V1>,<V4,V3>,<V4,V2>,<V3,V5>,<V5,V3>,<V2,V5>,<V6,V5>,<V2,V6>,<V6,V2>}
注意:
无向图也可以理解成一个特殊的有向图,就是边互相指向对方节点,A指向B,B又指向A。
3.顶点的度
连接顶点的边的数量称为该顶点的度。顶点的度在有向图和无向图中具有不同的表示。对于无向图,一个顶点V的度比较简单,其是连接该顶点的边的数量,记为D(V)。 例如,图二所示的无向图中,顶点V5的度为3。而V6的度为2。
对于有向图要稍复杂些,根据连接顶点V的边的方向性,一个顶点的度有入度和出度之分。
-
入度是以该顶点为端点的入边数量, 记为ID(V)。
-
出度是以该顶点为端点的出边数量, 记为OD(V)。
这样,有向图中,一个顶点V的总度便是入度和出度之和,即D(V) = ID(V) + OD(V)。例如,图三所示的有向图中,顶点V5的入度为3,出度为1,因此,顶点V5的总度为4。
4.邻接顶点
邻接顶点是指图结构中一条边的两个顶点。 邻接顶点在有向图和无向图中具有不同的表示。对于无向图,邻接顶点比较简单。例如,在图二所示的无向图中,顶点V2和顶点V6互为邻接顶点,顶点V2和顶点V5互为邻接顶点等。
对于有向图要稍复杂些,根据连接顶点V的边的方向性,两个顶点分别称为起始顶点(起点或始点)和结束顶点(终点)。有向图的邻接顶点分为两类:
-
入边邻接顶点:连接该顶点的边中的起始顶点。例如,对于组成<V2,V6>这条边的两个顶点,V2是V6的入边邻接顶点。
-
**出边邻接顶点:**连接该顶点的边中的结束顶点。例如,对于组成<V2,V6>这条边的两个顶点,V6是V2的出边邻接顶点。
5.无向完全图
如果在一个无向图中, 每两个顶点之间都存在条边,那么这种图结构称为无向完全图。典型的无向完全图,如图四所示。
图四 无向完全图
理论上可以证明,对于一个包含M个顶点的无向完全图,其总边数为M(M-1)/2。比如图四总边数就是5(5-1)/ 2 = 10。
6.有向完全图
如果在一个有向图中,每两个顶点之间都存在方向相反的两条边,那么这种图结构称为有向完全图。典型的有向完全图,如图五所示。
图五 有向完全图
理论上可以证明,对于一个包含N的顶点的有向完全图,其总的边数为N(N-1)。这是无向完全图的两倍,这个也很好理解,因为每两个顶点之间需要两条边。
7.有向无环图(DAG图)
如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图。
有向无环图可以利用在区块链技术中。
8.无权图和有权图
这里的权可以理解成一个数值,就是说节点与节点之间这个边是否有一个数值与它对应,对于无权图来说这个边不需要具体的值。对于有权图节点与节点之间的关系可能需要某个值来表示,比如这个数值能代表两个顶点间的距离,或者从一个顶点到另一个顶点的时间,所以这时候这个边的值就是代表着两个节点之间的关系,这种图被称为有权图;
如:在交通运输网中,边上的权值可能表示的是路程,也可能表示
的是运输费用(显然二者都是数字)。不过,边上的权值也有可能
是其它东西,比如说是一个字符串,甚至是一个更加复杂的数据包,
里面集合了更多的数据
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-S0Ho0WLl-1581605615960)(images/1071674-20170705165123847-2077753454.png)]
9.图的连通性
图的每个节点不一定每个节点都会被边连接起来,所以这就涉及到图的连通性,如下图:
可以发现上面这个图不是完全连通的。
9.简单图 ( Simple Graph)
对于节点与节点之间存在两种边,这两种边相对比较特殊
1.自环边(self-loop):节点自身的边,自己指向自己。
2.平行边(parallel-edges):两个节点之间存在多个边相连接。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8xQiwZT3-1581605615962)(images/824470-20190420092908548-1950023783.png)]
这两种边都是有意义的,比如从A城市到B城市可能不仅仅有一条路,比如有三条路,这样平行边就可以用到这种情况。不过这两种边在算法设计上会加大实现的难度。而简单图就是不考虑这两种边。
图的遍历
深度优先遍历和广度优先遍历
图的节点和边的结合变量
package edu.xalead.Graph;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
public class GraphNode {
private Object data;
private List<GraphNode> nexts = new ArrayList<>();
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
GraphNode graphNode = (GraphNode) o;
return Objects.equals(data, graphNode.data) &&
Objects.equals(nexts, graphNode.nexts);
}
@Override
public int hashCode() {
return Objects.hash(data, nexts);
}
public GraphNode(Object data) {
this.data = data;
this.nexts = nexts;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public List<GraphNode> getNexts() {
return nexts;
}
public void setNexts(List<GraphNode> nexts) {
this.nexts = nexts;
}
}
两种遍历方法
package edu.xalead.Graph;
import java.util.*;
public class Test {
/**
* 图的深度优先(递归)
* @root 图的起始节点
* @visited 已经访问过的节点集合
*/
public static void dft(GraphNode root,ArrayList<GraphNode> visiteds){
System.out.print (root.getData() + " ");
visiteds.add(root);
for(int i = 0 ; i < root.getNexts().size() ; i++){
GraphNode t = root.getNexts().get(i);
if(!visiteds.contains(t)){
dft(t,visiteds);
}
}
}
/**
* 图的广度优遍历
* @param root 图的起始节点
* @param visiteds 已经访问过的节点集合
*/
public static void bft(GraphNode root,ArrayList<GraphNode> visiteds){
Queue<GraphNode> queue = new LinkedList<>();
queue.offer(root);
visiteds.add(root);
while(!queue.isEmpty()){
GraphNode poll = queue.poll();
System.out.print(poll.getData() + " ");
for(int i=0;i<poll.getNexts().size();i++){
GraphNode node = poll.getNexts().get(i);
if(!visiteds.contains(node)){
queue.offer(node);
visiteds.add(node);
}
}
}
}
public static void main(String[] args) {
GraphNode node1 = new GraphNode(0);
GraphNode node2 = new GraphNode(1);
GraphNode node3 = new GraphNode(2);
GraphNode node4 = new GraphNode(3);
GraphNode node5 = new GraphNode(4);
GraphNode node6 = new GraphNode(5);
GraphNode node7 = new GraphNode(6);
GraphNode node8 = new GraphNode(7);
node1.getNexts().add(node2);
node1.getNexts().add(node3);
node3.getNexts().add(node7);
node2.getNexts().add(node4);
node2.getNexts().add(node5);
node4.getNexts().add(node6);
node5.getNexts().add(node6);
node5.getNexts().add(node8);
System.out.println("图的深度优先遍历(递归 栈)");
dft(node1,new ArrayList<>());
System.out.println();
System.out.println("图的广度度优先遍历(队列)");
bft(node1,new ArrayList<>());
}
}
结果展示:
下一篇: SingalR的简单认识