IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 《黑马程序员》— 图的入门 -> 正文阅读

[数据结构与算法]《黑马程序员》— 图的入门

目录

图的定义

图的相关术语

图的存储结构

?邻接矩阵

邻接表

无向图的实现

?图的搜索

深度优先搜索(DFS)

广度优先搜索(BFS)


图的定义

图是由一组顶点和一组能够将两个顶点相连的边组成的

?特殊图:

图可以分为无向图和有向图。有向图就是连接是有方向的。

图的相关术语

度: 某个顶点的度就是依附于该顶点的边的个数
环: 是一条至少含有一条边且终点和起点相同的路径
连通图: 如果图中任意一个顶点都存在一条路径到达另外一个顶点

?

图的存储结构

要表示一幅图,只需要表示清楚以下两部分内容即可:
1. 图中所有的顶点
2. 所有连接顶点的边
常见的图的存储结构有两种:邻接矩阵和邻接表

?邻接矩阵

1. 使用一个 V*V 的二维数组 int[V][V] adj, 把索引的值看做是顶点;
2. 如果顶点 v 和顶点 w 相连,我们只需要将 adj[v][w] adj[w][v] 的值设置为 1, 否则设置为 0 即可。

矩阵的横纵坐标代表了顶点,中间的元素值代表是否连接。

缺点:内存占用空间较大

邻接表

1. 使用一个大小为 V 的数组 Queue[V] adj 把索引看做是顶点
2. 每个索引处 adj[v] 存储了一个队列,该队列中存储的是所有与该顶点相邻的其他顶点。

无向图的实现

?无向图的构建:

import java.util.LinkedList;
import java.util.Queue;

public class Graph {
    private final int V; //顶点数量
    private int E; //边的数量
    private Queue<Integer>[] adj;

    public Graph(int V){
        //初始化
        this.V = V;
        this.E = 0;
        this.adj = new LinkedList[V];

        for(int i=0; i<adj.length; i++){
            adj[i] = new LinkedList();
        }
    }

    public int V(){
        return V;
    }

    public int E(){
        return E;
    }

    public void addEdge(int v, int w){
        // 无向图
        adj[v].offer(w);
        adj[w].offer(v);
        // 边的数量+1
        E++;
    }

    public Queue<Integer> adj(int v){
        return adj[v];
    }
    
}

?图的搜索

深度优先搜索(DFS)

先找子结点,再找兄弟结点

?(搜索过的点不用再搜索)

public class DFS {
    private boolean[] marked; //数组索引代表顶点,表示当前顶点是否已经被搜索
    private int count;  // 记录有多少个顶点与顶点s相通
    public DFS(Graph G, int s){
        //初始化
        this.marked = new boolean[G.V()];
        this.count = 0;

        dfs(G,s);
    }

    private void dfs(Graph G, int V){
        // 把V顶点标识为已经搜索
        marked[V] = true;

        for(Integer w: G.adj(V)){
            //判断当前w顶点有没有被搜索过
            if(!marked[w]){
                dfs(G,w);
            }
        }
        count++; // 相通顶点数量+1
    }

    //判断W顶点是否和S顶点相通
    private boolean marked(int w){
        return marked[w]; //被搜索过则意味着相通
    }
    //获取与顶点s相同的所有顶点的总数
    public int count(){
        return count;
    }
}

广度优先搜索(BFS)

先找兄弟结点,再找子结点

(搜索过的点不用再搜索)

层序遍历其实就是广度优先搜索

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
    private boolean[] marked;
    private int count;
    private Queue<Integer> waitSearch; //辅助队列

    public BFS(Graph G, int s){
        this.marked = new boolean[G.V()];
        this.count = 0;
        this.waitSearch = new LinkedList<Integer>();
        bfs(G,s);
    }

    private void bfs(Graph G, int v){
        marked[v] = true;
        waitSearch.offer(v);
        while(!waitSearch.isEmpty()){
            Integer wait = waitSearch.remove();
            //遍历wait顶点的邻接表
            for(Integer w: G.adj(wait)){
                if(!marked[w]){
                    bfs(G, w);
                }
            }
        }
        count ++;
    }

    public boolean marked(int w){
        return marked[w];
    }
    public int count(){
        return count;
    }
}

?

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-28 08:04:35  更:2021-07-28 08:06:27 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 17:28:40-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码