有向图的邻接表和邻接矩阵

这篇具有很好参考价值的文章主要介绍了有向图的邻接表和邻接矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

邻接表

有向图的邻接表是一种常用的表示方法,用于表示图中各个节点之间的关系。在有向图中,每条边都有一个方向,因此邻接表中的每个节点记录了该节点指向的其他节点。
具体来说,有向图的邻接表由一个由节点和它们的邻居节点列表组成的集合构成。对于每个节点,邻接表记录了该节点指向的所有邻居节点。这种表示方法可以用一个哈希表或数组来实现,其中哈希表或数组的键或索引表示节点,对应的值是一个列表,存储了该节点的所有邻居节点。
举例来说,考虑以下有向图:

A -> B, C
B -> C, D
C -> D
D -> A

对应的邻接表表示如下:

A: [B, C]
B: [C, D]
C: [D]
D: [A]

在邻接表中,每个节点及其邻居列表的组合表示了整个有向图的结构。使用邻接表可以有效地表示稀疏图,并且支持快速查找节点的邻居。

java表示这样的邻接表:
在 Java 中,可以使用 Map 来表示有向图的邻接表。具体来说,可以使用 Map<String, List>,其中键是节点的名称(如字符串表示),值是一个列表,存储了该节点指向的所有邻居节点的名称。以下是一个示例代码:

import java.util.*;



public class DirectedGraph {
 
    private Map<String, List<String>> adjacencyList;



    public DirectedGraph() {
 
        this.adjacencyList = new HashMap<>();
 
    }



    public void addEdge(String source, String target) {
 
        adjacencyList.computeIfAbsent(source, k -> new ArrayList<>()).add(target);
 
    }



    public List<String> getNeighbors(String node) {
 
        return adjacencyList.getOrDefault(node, Collections.emptyList());
 
    }



    public static void main(String[] args) {
 
        DirectedGraph graph = new DirectedGraph();
 
        graph.addEdge("A", "B");
 
        graph.addEdge("A", "C");
 
        graph.addEdge("B", "C");
 
        graph.addEdge("B", "D");
 
        graph.addEdge("C", "D");
 
        graph.addEdge("D", "A");



        for (String node : graph.adjacencyList.keySet()) {
 
            List<String> neighbors = graph.getNeighbors(node);
 
            System.out.print(node + " -> ");
 
            for (String neighbor : neighbors) {
 
                System.out.print(neighbor + " ");
 
            }
 
            System.out.println();
 
        }
 
    }
}
}

在这个示例中,DirectedGraph 类表示有向图,使用 Map 存储邻接表。addEdge 方法用于添加一条边,getNeighbors 方法用于获取指定节点的邻居节点列表。在 main 方法中,创建了一个有向图并添加了一些边,然后遍历输出了每个节点及其邻居节点列表。

邻接矩阵

有向图的邻接矩阵是一个二维数组,用于表示图中节点之间的关系。对于有向图,邻接矩阵是一个 N × N 的矩阵,其中 N 是节点的数量,矩阵的每个元素 a[i][j] 表示从节点 i 到节点 j 是否存在一条有向边,通常用 0 或 1 表示不存在或存在边。
具体来说,邻接矩阵的构造如下:
如果图中存在一条从节点 i 到节点 j 的有向边,则将矩阵中的 a[i][j] 设为 1。
如果图中不存在从节点 i 到节点 j 的有向边,则将矩阵中的 a[i][j] 设为 0。
在有向图中,邻接矩阵是一个对称矩阵。但需要注意的是,有些情况下,如果图中存在权重(例如表示边的距离或成本),邻接矩阵的元素可能不只是 0 或 1,而是表示具体权重的数值。
举例来说,考虑以下有向图:
cssCopy code
A -> B
A -> C

B -> C

B -> D
C
C -> D
D
D -> A

对应的邻接矩阵为:
cssCopy code
A B C D

A 0 1 1 0
B 0 0 1 1
C
C 0 0 0 1
D
D 1 0 0 0

在 Java 中,可以使用二维数组来表示邻接矩阵,如下所示:
javaCopy code
int[][] adjacencyMatrix = {

{0, 1, 1, 0},

{0, 0, 1, 1},

{0, 0, 0, 1},

{1, 0, 0, 0}

}
};

其中,adjacencyMatrix[i][j] 表示从节点 i 到节点 j 是否存在一条有向边。

用 Java 代码表示有向图的邻接矩阵,你可以使用二维数组来实现。假设有 N 个节点,可以用一个 N × N 的二维数组来表示邻接矩阵,其中 adjMatrix[i][j] 表示从节点 i 到节点 j 是否存在一条有向边。如果存在,则 adjMatrix[i][j] 为 1;否则为 0。以下是一个示例代码:
javaCopy code
public class DirectedGraph {

private int[][] adjMatrix;

private int numNodes;



public DirectedGraph(int numNodes) {

    this.numNodes = numNodes;

    this.adjMatrix = new int[numNodes][numNodes];

}



public void addEdge(int source, int target) {

    adjMatrix[source][target] = 1;

}



public void removeEdge(int source, int target) {

    adjMatrix[source][target] = 0;

}



public boolean hasEdge(int source, int target) {

    return adjMatrix[source][target] == 1;

}



public int getNumNodes() {

    return numNodes;

}



public void printAdjMatrix() {

    for (int i = 0; i < numNodes; i++) {

        for (int j = 0; j < numNodes; j++) {

            System.out.print(adjMatrix[i][j] + " ");

        }

        System.out.println();

    }

}



public static void main(String[] args) {

    DirectedGraph graph = new DirectedGraph(4);

    graph.addEdge(0, 1);

    graph.addEdge(0, 2);

    graph.addEdge(1, 2);

    graph.addEdge(1, 3);

    graph.addEdge(2, 3);



    graph.printAdjMatrix();

}

}
}

在这个示例中,DirectedGraph 类表示有向图,使用二维数组 adjMatrix 来存储邻接矩阵。addEdge 方法用于添加一条边,removeEdge 方法用于删除一条边,hasEdge 方法用于判断两个节点之间是否有边。printAdjMatrix 方法用于打印邻接矩阵。在 main 方法中,创建了一个包含 4 个节点的有向图,并添加了一些边,然后打印了邻接矩阵。文章来源地址https://www.toymoban.com/news/detail-836813.html

到了这里,关于有向图的邻接表和邻接矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS)

    有向图(Directed Graph),也被称为有向图形或方向图,是一种图的类型。在有向图中,图中的边具有方向,从一个顶点指向另一个顶点。 在有向图中,每个顶点表示一个实体,而有向边则表示实体之间的关系或连接。这种有方向性的边表明了连接的起点和终点之间的单向关系

    2024年02月09日
    浏览(50)
  • 数据结构|连通图、完全图、无向图、有向图的边数计算问题

    完全图 也称简单完全图。一个图任意两个顶点之间都有边的话,该图就称为完全图。 连通图(一般都是指无向图) 如果图中任意俩顶点都连通,则该图为连通图。 有向图 由点和弧所构成的图( 强连通图必然是有向图,因为强连通和弱连通的概念只在有向图中存在 ) 无向

    2023年04月08日
    浏览(48)
  • 试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点a到顶点b的路径

    试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点a到顶点b的路径,注意a!=b(必须严格按照样例进行输入输出,先输入图的顶点数和弧数,并依次输入弧的相关信息,最后输入要判断的两个顶点的信息) 样例如下: 输入: 5 4 2 4 2 1

    2024年02月15日
    浏览(41)
  • 有向图的拓扑排序

    拓扑排序 。任意给定一个有向图,设计一个算法,对它进行拓扑排序。拓扑排序算法思想:a.在有向图中任选一个没有前趋的顶点输出;b.从图中删除该顶点和所有以它为尾的弧;c.重复上述a、b,直到全部顶点都已输出,此时,顶点输出序列即为一个拓朴有序序列;或者直到

    2024年02月09日
    浏览(48)
  • 有向图的强连通分量

    对于一个有向图,连通分量:对于分量中任意两点u,v,必然可以从u走到v,且从v走到u. 强连通分量:极大连通分量。 求出强连通分量后,可以通过将强连通分量缩点的方式,将有向图转化成有向无环图。 求强连通分量的方法:tarjan O(n+m),时间复杂度是线性的 1 . 采用dfs来遍历整

    2024年02月10日
    浏览(39)
  • 公开游戏、基于有向图的游戏

    目录 〇,背景 一,公开游戏、策梅洛定理 1,公开游戏 2,策梅洛定理 3,非有向图游戏的公开游戏 力扣 486. 预测赢家(区间DP) 力扣 877. 石子游戏(退化贪心) 力扣 1140. 石子游戏 II(二维DP) 力扣 1406. 石子游戏 III(数列DP) 力扣 1563. 石子游戏 V(区间DP)  力扣 1686.

    2024年02月09日
    浏览(45)
  • 有向图的强连通分量算法

    有向图的强连通分量算法 强连通分量定义 在有向图中,某个子集中的顶点可以直接或者间接互相可达,那么这个子集就是此有向图的一个强连通分量,值得注意的是,一旦某个节点划分为特定的强连通分量后,此顶点不能在其它子树中重复使用,隐含了图的遍历过程和极大

    2024年02月06日
    浏览(84)
  • 真题详解(有向图)-软件设计(六十二)

    真题详解(极限编程)-软件设计(六十一) https://blog.csdn.net/ke1ying/article/details/130435971 CMM指软件成熟度模型,一般1级成熟度最低,5级成熟度最高,采用更高级的CMM模型可以提高软件质量。 初始:杂乱无章。 可重复级:建立基本的项目管理过程和跟踪费用项。 已定义(确定)

    2024年02月01日
    浏览(63)
  • 2023-04-09 有向图及相关算法

    有向图的的应用场景 社交网络中的关注 互联网连接 程序模块的引用 任务调度 学习计划 食物链 论文引用 无向图是特殊的有向图,即每条边都是双向的 改进Graph和WeightedGraph类使之支持有向图 Graph类的改动 WeightedGraph类的改动 有些问题,在有向图中不存在,或者我们通常不考

    2024年02月05日
    浏览(46)
  • 2023-8-29 有向图的拓扑排序

    题目链接:有向图的拓扑排序

    2024年02月11日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包