当前位置: 首页 > news >正文

图一:入门篇

文章目录

    • 一、图
      • 1.1 概念
      • 1.2 图的表示
        • 1.2.1 邻接矩阵
        • 1.2.2 邻接表
      • 1.3 图的遍历
        • 1.3.1 深度优先搜索 DFS
        • 1.3.2 广度优先搜索 BFS
        • 1.3.3 DFS 与 BFS的比较
      • 1.4 拓扑排序
      • 1.5 最短路径算法
        • 15.2 最短路径算法应用
      • 1.6 最小生成树
    • 参考


一、图

1.1 概念

一个图可以表示为(V,E),其中V是结点的结合,称为顶点;E是两个顶点的连线,称为边。


1. 有向边

  • 有序顶点对(u,v)
  • u 是源点,v是终点

在这里插入图片描述


2. 无向边

  • 无序顶点对(u,v)。例如:铁路线
    在这里插入图片描述

3.有向图

  • 所有的边都是有向边。例如:路由网络
    在这里插入图片描述

4.无向图

  • 所有的边都是无向边。例如:飞行网络

在这里插入图片描述


4. 树

  • 无环图称为树,树是不包含环的连通图

在这里插入图片描述


5.自环

  • 自环指的是一条连接顶点及其自身的边

在这里插入图片描述


6.连通图

  • 如果图中每对顶点之间都有路径相连,则称该图是连通图

7.有向无环图

  • 是一种不包含环的有向图

在这里插入图片描述


8.二分图

  • 顶点能被分成两个集合的图,其中所有的边只连接来自不同集合的顶点

9.有权图

  • 图的每条边被赋值一个整数

在这里插入图片描述


10.完全图

  • 包含所有边的图称为完全图

11. 稀疏图、稠密图
仅包含少量边的图,称作稀疏图;仅有少量边缺失的图,称作稠密图


1.2 图的表示

  • 邻接矩阵
  • 邻接表

1.2.1 邻接矩阵

图的表示需要顶点数、边数以及它们之间的连接关系。本方法采用 V x V的矩阵Adj。如果存在一条从顶点u到顶点v的边,则设置 Adj[u,v]为1,否则为0。

  • 无向图
    对于所有顶点,可以设置 Adj[u,u]都是1

  • 有向图
    在这里插入图片描述
    无向图的代码如下所示:
public class Graph {private boolean adjMatrix[][];private int vertexCount;public Graph(boolean[][] adjMatrix, int vertexCount) {this.adjMatrix = adjMatrix;this.vertexCount = vertexCount;}public void addEdge(int i, int j) {if(i >=0 && i < vertexCount && j > 0  && j < vertexCount) {adjMatrix[i][j] = true;adjMatrix[j][i] = true;}}public void removeEdge(int i, int j) {if(i >=0 && i < vertexCount && j > 0  && j < vertexCount) {adjMatrix[i][j] = false;adjMatrix[j][i] = false;}}public boolean isEdge(int i, int j) {if(i >=0 && i < vertexCount && j > 0  && j < vertexCount) {return adjMatrix[i][j];} else {return false;}}
}

当图是稠密图时,邻接矩阵是一种很好的表示方法,邻接矩阵需要O(V2)个存储单位和O(N2)来初始化。 但是,如果图是稀疏的,则不适合


1.2.2 邻接表

在这里插入图片描述

在这种表示方法中,所有与某个顶点v相连的顶点都在v的邻接表中列出,采用链表很容易实现。邻接表中的每一个顶点v都有一个与其对应的链表,链表结点表示v的邻接点与v之间的连接。每个顶点一个链表
在这里插入图片描述

由于顶点 A与B和D有边相连,所以将B和D添加到A的邻接表中。

边的顺序决定了顶点在连接表中的顺序;相同的图在邻接表中可以有不同的表示方法。边在邻接表中出现的顺序也会影响算法处理的顺序。


1.3 图的遍历

1.3.1 深度优先搜索 DFS

深度优先搜索DFS算法原理类似于树的前序遍历,本质上也是使用栈来实现。

初始时所有顶点都被标记为未被放过(false)。DFS算法从图中一个顶点 u开始,首先考虑从u到其他顶点的边,如果该边通往一个已经被访问的顶点,那么回溯到当前顶点 u。如果该边通往一个未被访问过的顶点,则到达该顶点,并从该顶点开始进行访问,即将新的顶点变为当前顶点,重复这个过程直到算法到达“末端”。然后从在这个“末端”点开始回溯。当回溯到起始顶点时整个过程结束。

在这里插入图片描述
下图为例:有时边会通往一个已经被访问过的顶点,这些边称为回退边,其余的边称为 树边, 因为从图中删除回退边会产生一棵树。最终产生的树称为DFS树,顶点的访问顺序称为顶点的DSF编号。

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
DFS 遍历将产生一棵树(没有回退边),该树称为DFS树。如果使用邻接表来表示图,则DFS算法时间复杂度 O(V+E)。这是因为从某个顶点开始,算法只访问该顶点尚未被访问的邻接点。而邻接矩阵难以快速找到所有与某个顶点相邻的边,因此其时间复杂度为 O(V2)


code如下,仅做参考: 无向图、基于邻接矩阵的DFS算法。该算法利用了Stack这种数据结构来完成结点回溯操作。

public class Graph4 {private final int maxVertices = 20;//最大顶点数为20private Vertex[] vertexList; //顶点集合private int adjMatrix[][];private int vertexCount;//顶点数private Queue theQueue;public Graph4() {this.vertexList = new Vertex[maxVertices];this.adjMatrix = new int[maxVertices][maxVertices]; //邻接钜阵this.vertexCount = 0;for (int y = 0; y < maxVertices; y++) {for (int x = 0; x < maxVertices; x++) {adjMatrix[x][y] = 0; //邻接矩阵初始化}}theQueue = new LinkedList();}/*** 添加顶点。* @param lab*/public void addVertex(char lab) {vertexList[vertexCount++] = new Vertex(lab);//添加顶点}/*** 添加边* @param start* @param end*/public void addEdge(int start,int end) {adjMatrix[start][end] = 1;adjMatrix[end][start] = 1;}/*** 展示表* @param v*/public void displayVertex(int v) {System.out.println(vertexList[v].lable);}public void bfs() {vertexList[0].visited = true;//访问第一个点displayVertex(0);theQueue.add(0);//入栈int v2;while (!theQueue.isEmpty()) {int v1 = (int) theQueue.remove();while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {vertexList[v2].visited = true;displayVertex(v2);theQueue.add(v2);}}for(int j = 0; j < vertexCount; j++) {vertexList[j].visited = false; //初始化标记}}/***  该点到其它点所有的边。* @param v* @return*/public int getAdjUnvisitedVertex(int v) {for(int j = 0; j < vertexCount; j++) {if(adjMatrix[v][j] == 1 && vertexList[j].visited == false) {return j;}}return -1;}public static void main(String[] args) {Graph4 graph4 = new Graph4();graph4.addVertex('A');graph4.addVertex('B');graph4.addVertex('C');graph4.addVertex('D');graph4.addVertex('E');graph4.addVertex('F');graph4.addVertex('G');graph4.addVertex('H');graph4.addEdge(0,1);graph4.addEdge(1,2);graph4.addEdge(2,3);graph4.addEdge(1,7);graph4.addEdge(2,4);graph4.addEdge(4,7);graph4.addEdge(4,5);graph4.addEdge(4,6);graph4.bfs();for (int i = 0; i < 20; i++) {for (int j = 0; j < 20; j++) {System.out.print(graph4.adjMatrix[i][j] + " ");}System.out.println();}}
}class Vertex {public char lable;public boolean visited;//是否访问过public Vertex(char lable) {this.lable = lable;this.visited = false;//默认表示未访问过}
}

按照DFS的输出顺序:A B C D F G H.


DFS的应用

  • 连通分量求解
  • 类似迷宫问题
  • 拓扑排序
    ……

1.3.2 广度优先搜索 BFS

BFS算法的原理类似于树的层次变量,该算法也使用队列。BFS逐层对图进行遍历。初始时,BFS从一个给定的顶点出发,该顶点位于第 0 层。第一步,它访问所有处于第一层的顶点。第二步,访问第二层的所有顶点,即与第一层顶点相邻的顶点。BFS算法重复这个过程,直到图的所有层都访问一遍。

BFS遍历图如下所示:

在这里插入图片描述在这里插入图片描述在这里插入图片描述如果使用邻接表表示图,BFS算法 O(V+E) 。邻接矩阵为O(V2)

code如下,仅做参考: 无向图、基于邻接矩阵的BFS算法。实现是基于Queue.

public class Graph4 {private final int maxVertices = 20;//最大顶点数为20private Vertex[] vertexList; //顶点集合private int adjMatrix[][];private int vertexCount;//顶点数private Queue theQueue;public Graph4() {this.vertexList = new Vertex[maxVertices];this.adjMatrix = new int[maxVertices][maxVertices]; //邻接钜阵this.vertexCount = 0;for (int y = 0; y < maxVertices; y++) {for (int x = 0; x < maxVertices; x++) {adjMatrix[x][y] = 0; //邻接矩阵初始化}}theQueue = new LinkedList();}/*** 添加顶点。* @param lab*/public void addVertex(char lab) {vertexList[vertexCount++] = new Vertex(lab);//添加顶点}/*** 添加边* @param start* @param end*/public void addEdge(int start,int end) {adjMatrix[start][end] = 1;adjMatrix[end][start] = 1;}/*** 展示表* @param v*/public void displayVertex(int v) {System.out.println(vertexList[v].lable);}public void bfs() {vertexList[0].visited = true;//访问第一个点displayVertex(0);theQueue.add(0);int v2;while (!theQueue.isEmpty()) {int v1 = (int) theQueue.remove();while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {vertexList[v2].visited = true;displayVertex(v2);theQueue.add(v2);}}for(int j = 0; j < vertexCount; j++) {vertexList[j].visited = false; //初始化标记}}/***  该点到其它点所有的边。* @param v* @return*/public int getAdjUnvisitedVertex(int v) {for(int j = 0; j < vertexCount; j++) {if(adjMatrix[v][j] == 1 && vertexList[j].visited == false) {return j;}}return -1;}public static void main(String[] args) {Graph4 graph4 = new Graph4();graph4.addVertex('A');graph4.addVertex('B');graph4.addVertex('C');graph4.addVertex('D');graph4.addVertex('E');graph4.addVertex('F');graph4.addVertex('G');graph4.addVertex('H');graph4.addEdge(0,1);graph4.addEdge(1,2);graph4.addEdge(2,3);graph4.addEdge(1,7);graph4.addEdge(2,4);graph4.addEdge(4,7);graph4.addEdge(4,5);graph4.addEdge(4,6);graph4.bfs();for (int i = 0; i < 20; i++) {for (int j = 0; j < 20; j++) {System.out.print(graph4.adjMatrix[i][j] + " ");}System.out.println();}}
}
class Vertex {public char lable;public boolean visited;//是否访问过public Vertex(char lable) {this.lable = lable;this.visited = false;//默认表示未访问过}
}

输出的顺序应该是:A B C H D E F G


BFS的应用

  • 连通分量
  • 查找两个节点之间的最短路径
  • 测试图的二分性
    ……

1.3.3 DFS 与 BFS的比较

DFS的优势在于它的内存开销要远远小于BFS,因为它不需要存储每一层结点的所有孩子结点指针。根据数据和查找内容的不同,DFS和BFS各有优势。BFS每次访问一层,若预先知道需要搜索的结果处在一个较低的深度,那么BFS是适合的。若结果处于最大深度,则DFS是更好的选择。

在这里插入图片描述


1.4 拓扑排序

拓扑排序是在一个有向无环图(DAG)中对顶点的排序,有向无环图中,每个顶点都排在所有以它为起点的相邻结点之前。若图中存在环,则无法进行拓扑排序,因为环上的两个点存在相互依赖。

在这里插入图片描述

拓扑排序的应用

  • 课程选修的先决条件
  • 检测死锁
  • 计算作业的流水线
  • 检查符号链接环
  • 解析点子表格中的公式
    ……

1.5 最短路径算法

给定一个图 G = (V,E)和一个特殊的顶点S,需要查找从S 到图中其他每个顶点的最短路径。根据输入图像的类型不同,最短路径算法相应地有一些变化。主要包括:
在这里插入图片描述

15.2 最短路径算法应用

  • 查找从一个地方到另一个地方的最快方式
  • 查找从一个城市到另一个城市的飞行、发送数据最便宜的方式
    ……

在这里插入图片描述code如下,仅做参考


  • 有权图中的最短路径(Dijkstra 算法)
    在这里插入图片描述在这里插入图片描述在这里插入图片描述

  • Bellman_ford 算法
    在这里插入图片描述

1.6 最小生成树

在这里插入图片描述


参考

《数据结构与算法经典问题解析-Java语言描述》


http://www.taodudu.cc/news/show-6105730.html

相关文章:

  • (宏) Word图片题注“图一-1”转化为“图1-1”
  • app性能测试怎么做
  • PCB布局和绘制的关键操作
  • 什么是CAD的模型和布局?
  • 阿里巴巴矢量图标库icon图标在线引用
  • 精灵随着鼠标的移动而移动
  • 【cocos2D-X】Plist使用 实现 移动精灵多图片动画
  • 移动设备上“精灵图”的制作适配
  • cocos2dx 精灵的移动(2)
  • Cocos2d-x 2.0 百例精讲:如何让一个精灵跟随触点移动
  • 在屏幕的任意位置拖拽,控制精灵移动
  • 精灵的移动效果,旋转效果
  • 【JavaScript】实现移动小精灵
  • 让视角随着精灵移动
  • 移动设备上“精灵图”的制作
  • 移动端精灵图的使用
  • Cocos2d-x随记(2)-精灵移动
  • buntu22.04安装WPS中文版(一百一十八)
  • 数数
  • 视网膜数据集(2)Messidor
  • realsense 相机的部分信息获取
  • Linux线程数和系统线程数查看
  • 数的表示与运算
  • 如何判断一个数是否是NaN
  • SQLite获取查询结果数
  • 用while循环写四叶玫瑰数(自幂数)
  • 【算法讲20:Dsu on Tree】树上数颜色 | Lomsat gelral
  • Deep_Learn关于数组和数的操作
  • codeforces1670F Jee, You See?(DP/位运算/前缀和/组合数)
  • SEEM~