数据结构笔记04

背景

线性表和树都只能有一个前驱节点,也就是父节点,当需要表示多对多关系的时候就需要使用图。图是一种数据结构,其中:节点可以具有 0 个或多个相邻元素,两个节点之间的连接称为边(Edge),节点也被称为顶点(Vertices)。

无向图

顶点之间的连接没有方向,例如:

有向图

顶点之间有方向,只能从一点到另一点,但不能直接返回

带权图

路径有权值(个人看起来像EIGRP),也叫网

图的表示方式

二维数组(邻接矩阵)

邻接矩阵是表示图形中顶点之间相邻关系的矩阵,对于n个顶点的图而言,矩阵的行和列表示1到n个点。

例如:左侧列中4(代表图中的 4)所在的行,和上方行中的2(代表图中的2)所在的列的交点值(4,2)是1,表示可以直接连接。

链表表示(邻接表)

由于邻接矩阵有一个缺点:它需要为每个顶点都分配 n 个边的空间,其实有很多边都是不存在的(比如上面的 0,0 不链接,也需要表示出来),这 会造成空间的一定损失。

邻接表只关心存在的边,因此没有空间浪费,由 数组 + 链表组成。

例如:标号为 0 的链表表示图中的 0 和哪些顶点直接相连。

图的创建

分析

  • 保存顶点 ArrayList
  • 保存矩阵 int[][] deges

代码

import java.util.ArrayList;
import java.util.Arrays;

public class GraphExample {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        String vertexValue[]={"A","B","C","D","E"};
        for (String VertexValue:vertexValue) {
            graph.addVertex(VertexValue);
        }
        //A-B A-C B-C B-D B-E
        graph.addEdge(0,1,1);
        graph.addEdge(0,2,1);
        graph.addEdge(1,2,1);
        graph.addEdge(1,3,1);
        graph.addEdge(1,4,1);

        graph.showGraph();
    }
}

class Graph {
    private ArrayList<String> vertexList;
    private int[][] edge;
    private int numOfEdges; //number of edges

    public Graph(int numOfVertex) {
        edge = new int[numOfVertex][numOfVertex];
        vertexList = new ArrayList<>(numOfVertex);
        numOfEdges = 0;
    }

    public void addVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * add edge
     *
     * @param vertex1 first vertex
     * @param vertex2 second vertex
     * @param weight  weight of edge
     */
    public void addEdge(int vertex1, int vertex2, int weight) {
        edge[vertex1][vertex2] = weight;
        edge[vertex2][vertex1] = weight;
        numOfEdges++;
    }

    public int getNumOfVertex() {
        return vertexList.size();
    }

    public int getNumOfEdges() {
        return numOfEdges;
    }

    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    public int getWeight(int vertex1, int vertex2) {
        return edge[vertex1][vertex2];
    }

    public void showGraph() {
        for (int[] link : edge) {
            System.out.println(Arrays.toString(link));
        }
    }
}

深度优先遍历 Depth First Search, DFS

从初始访问节点出发,初始访问节点可能有多个邻接节点(直连)

深度优先遍历的策略为:初始节点出发,访问第一个邻节点,再将访问到的邻节点视为初始节点,访问它的第一个邻节点,以此类推。

算法步骤:

  1. 访问初始节点 v ,并标记已访问
  2. 查找节点的第一个邻节点 w
  3. 若 w 存在,执行步骤 4 ,若不存在返回第一步,从 v 的下一个节点继续
  4. 若 w 未被访问,对 w 进行深度优先遍历递归(把 w 看成 v,继续执行1、2、3)
  5. 若 w 被访问过,查找节点 w 的下一个邻节点,转到步骤 3

在本例中,以 A 为初始节点,在 vertexList 中,顶点的储存方式为 { A, B, C, D, E }

  1. 从 A 出发,标记成已访问
  2. 它的第一个节点是 B,存在且未被访问,访问 B 的第一个邻节点 C
  3. C存在,访问 C ,标记为已访问,C 的下一个节点的 D,但无法到达(不存在),回溯至上一步
  4. B 的第一个节点是 C,被访问,查找下一个邻节点 D
  5. D存在,访问 D ,标记为已访问,D 的下一个节点的 E,但无法到达(不存在),回溯至上一步
  6. B 的第一个、第二个邻节点都被访问,访问第三个邻节点 E
  7. E 存在,访问 E ,标记为已访问(回溯/打断)

广度优先遍历 Broad First Search, BFS

类似于分层搜索,广度优先遍历需要使用一个队列来保存访问过的节点的顺序。按此顺序来访问这些节点的邻接节点

算法步骤:

  1. 访问初始节点 v ,并标记已访问
  2. 将 v 加入队列
  3. 当 v 为非空时,继续执行,否则算法结束
  4. 出队列,取得头节点 u
  5. 查找 u 的第一个邻节点 w
  6. 若 w 不存在,转到步骤 3,否则:
    6.1. 若 w 未访问,标记为已访问
    6.2. 节点 w 入队
    6.3. 查找节点 u 的继 w 零界点后的下一个邻节点 w,转到步骤 6

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
隐藏
变装