侧边栏壁纸
博主头像
coydone博主等级

记录学习,分享生活的个人站点

  • 累计撰写 306 篇文章
  • 累计创建 51 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

coydone
2021-06-14 / 0 评论 / 0 点赞 / 312 阅读 / 4,138 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

图的定义及分类

图是由一组顶点和一组能够将两个顶点相连的边组成的。在计算机科学中,一个图就是一些顶点的集合,这些顶点通过一系列边结对(连接)。顶点用圆圈表示,边就是这些圆圈之间的连线。顶点之间通过边连接。(顶点有时也称为节点或者交点,边有时也称为链接)

图有各种形状和大小。边可以有权重(weight),即每一条边会被分配一个正数或者负数值。

边可以是有方向的。

树和链表可以被当成是图,只不过是一种更简单的形式。它们都有顶点(节点)和边(连接)。

图可以包含圈(cycles),即你可以从一个顶点出发,沿着一条路径最终会回到最初的顶点。树是不包含圈的图。

另一种常见的图类型是单向图或者 DAG:就像树一样,这个图没有任何圈(无论你从哪一个节点出发,你都无法回到最初的节点),但是这个图有有向边(通过一个箭头表示,这里的箭头不表示继承关系)。

特殊的图:

  • 自环:即一条连接一个顶点和其自身的边;

  • 平行边:连接同一对顶点的两条边;

按照连接两个顶点的边的不同,可以把图分为以下两种:

  • 无向图:边仅仅连接两个顶点,没有其他含义;

  • 有向图:边不仅连接两个顶点,并且具有方向;

相关术语:

  • 相邻顶点:当两个顶点通过一条边相连时,我们称这两个顶点是相邻的,并且称这条边依附于这两个顶点。

  • 度:某个顶点的度就是依附于该顶点的边的个数。

  • 子图:是一幅图的所有边的子集(包含这些边依附的顶点)组成的图。

  • 路径:是由边顺序连接的一系列的顶点组成。

  • 环:是一条至少含有一条边且终点和起点相同的路径。

  • 连通图:如果图中任意一个顶点都存在一条路径到达另外一个顶点,那么这幅图就称之为连通图。

  • 连通子图:一个非连通图由若干连通的部分组成,每一个连通的部分都可以称为该图的连通子图。

图的表示方式

理论上,图就是一堆顶点和边对象而已,在代码中通过邻接列表和邻接矩阵来描述。

邻接列表:在邻接列表实现中,每一个顶点会存储一个从它这里开始的边的列表。比如,如果顶点A 有一条边到B、C和D,那么A的列表中会有3条边。

邻接列表只描述了指向外部的边。A 有一条边到B,但是B没有边到A,所以 A没有出现在B的邻接列表中。查找两个顶点之间的边或者权重会比较费时,因为遍历邻接列表直到找到为止。

**邻接矩阵:**在邻接矩阵实现中,由行和列都表示顶点,由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。例如,如果从顶点A到顶点B有一条权重为 5.6 的边,那么矩阵中第A行第B列的位置的元素值应该是5.6:

往这个图中添加顶点的成本非常昂贵,因为新的矩阵结果必须重新按照新的行/列创建,然后将已有的数据复制到新的矩阵中。

大多数时候,选择邻接列表是正确的。下面是两种实现方法更详细的比较。

假设 V 表示图中顶点的个数,E 表示边的个数。

操作 邻接列表 邻接矩阵
存储空间 O(V + E) O(V^2)
添加顶点 O(1) O(V^2)
添加边 O(1) O(1)
检查相邻性 O(V) O(1)

“检查相邻性” 是指对于给定的顶点,尝试确定它是否是另一个顶点的邻居。在邻接列表中检查相邻性的时间复杂度是O(V),因为最坏的情况是一个顶点与每一个顶点都相连。

在稀疏图的情况下,每一个顶点都只会和少数几个顶点相连,这种情况下相邻列表是最佳选择。如果这个图比较密集,每一个顶点都和大多数其他顶点相连,那么相邻矩阵更合适。

一般用邻接表表示稀疏图,用邻接矩阵表示稠密图。

无向图的实现

API设计

类名 Graph
构造方法 Graph(int V):创建一个包含V个顶点但不包含边的图
成员方法
	public int V():获取图中顶点的数量
	public int E():获取图中边的数量
	public void addEdge(int v,int w):向图中添加一条边 v-w
	public Queue adj(int v):获取和顶点v相邻的所有顶点
成员变量
	private int V:记录顶点数量
	private int E:记录边数量
	private Queue[] adj: 邻接表

代码实现

import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class Graph {

    //顶点数量
    private int v;

    //边数量
    private int e;

    //邻接表
    private Queue<Integer>[] adj;

    //创建一个包含V个顶点但不包含边的图
    public Graph(int v) {
        // 初始化顶点数量
        this.v = v;
        // 初始化边的数量
        this.e = 0;
        // 初始化邻接表
        this.adj = new Queue[v];
        // 初始化邻接表中的空队列
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new ArrayBlockingQueue<>(5);
        }
    }

    //获取图中定点的数量
    public int V() {
        return v;
    }

    //获取图中边的数量
    public int E() {
        return e;
    }

    //向图中添加一条边v-w
    public void addEdge(int v, int w) {
        // 把w添加到v的链表中,这样顶点v就多了一个相邻点w
        adj[v].add(w);
        // 把v添加到w的链表中,这样顶点w就多了一个相邻的点v
        adj[w].add(v);
        // 边的数量自增1
        e++;
    }

    //获取和顶点v相邻的所有顶点
    public Queue adj(int v) {
        return adj[v];
    }

    //测试
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        graph.addEdge(0, 4);
		//new DepthFirstSearch(graph,0);
    }
}

图的搜索

深度优先搜索

所谓的深度优先搜索(Depth-First Search,简称DFS),指的是在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找子结点,然后找兄弟结点。

public class DepthFirstSearch {
    //记录有多少个顶点与S顶点相通
    private int count;
    //索引代表顶点,值代表当前顶点是否已经被搜索
    private boolean[] marked;

    //构造深度优先搜索对象,使用深度优先搜索出图中s顶点的所有相通顶点
    public DepthFirstSearch(Graph g, int s) {
        // 构造一个和图大小一样的布尔数组
        marked = new boolean[g.V()];
        // 构造g图中与顶点s相通的所有顶点
        dfs(g, s);
    }

    //使用深度优先搜索找出g图中v定点的所有相通顶点
    private void dfs(Graph g, int v) {
        System.out.println(v);
        // 当前节点标记为已搜索
        marked[v] = true;
        // 遍历v定点的邻接表,找到每一个顶点w
        Queue<Integer> queue = g.adj(v);
        for (Integer w : queue) {
            // 如果当前顶点w没有被搜索过,则递归搜索与w顶点相通的其他顶点
            if (!marked[w]) {
                dfs(g, w);
            }
        }
        // 相通的顶点数量+1
        count++;
    }

    //判断w顶点与s顶点是否相通
    public boolean marked(int w) {
        return marked[w];
    }

    public int count() {
        return count;
    }
}

广度优先搜索

所谓的广度优先搜索(Breadth-First Search,简称BFS),指的是在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找兄弟结点,然后找子结点。

import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class BreadthFirstSearch {

    //索引代表顶点,值代表当前顶点是否已经被搜索
    private boolean[] marked;

    //记录有多少个顶点与s顶点想通
    private int count;

    //存储待搜索邻接表的点
    private Queue<Integer> waitSearch;

    //使用广度优先搜索找出G图中v顶点的所有相邻顶点
    public BreadthFirstSearch(Graph g, int v) {
        // 构造一个和图大小一样的布尔数组
        marked = new boolean[g.V()];
        // 初始化待搜索顶点的队列
        waitSearch = new ArrayBlockingQueue<>(g.V());
        // 构造g图中与顶点s相通的所有顶点
        bfs(g, v);
    }

    //使用广度优先搜索找出g图中v顶点的所有相邻顶点
    private void bfs(Graph g, int v) {
        // 把当前顶点v放入到队列中,等待搜索它的邻接表
        waitSearch.offer(v);
        // 使用while循环从队列中取出待搜索的顶点wait,进行搜索邻接表
        while (!waitSearch.isEmpty()) {
            Integer wait = waitSearch.poll();
            // 把wait设为已搜索
            marked[wait] = true;
            System.out.println(wait);
            // 遍历wait顶点的邻接表,得到每一个顶点
            Queue<Integer> queue = g.adj(wait);
            for (Integer w : queue) {
                // 如果当前顶点w没有被搜索,则递归搜索与w想通的其他顶点
                if (!marked[w] && !waitSearch.contains(w)) {
                    waitSearch.offer(w);
                }
            }
        }
        count++;
    }

    //判断w顶点与s顶点是否相通
    public boolean marked(int w) {
        return marked[w];
    }

    public int count() {
        return count;
    }
}
0

评论区