图的表示及代码实现

python基础

浏览数:41

2019-10-8

一、图的表示

  从图的逻辑结构定义来看,无法将图中的顶点排列成一个唯一的线性序列。在图中任意一个顶点都可以看成是图的第一个顶点,对任何一个顶点而言,它的邻接点之间也不存在顺序关系。为了方便存储和操作,需要将图中的顶点按一定的序列排列起来。

  顶点在图中的位置就是指该顶点在人为确定的序列中的位置。

  由于图的结构比较复杂,任意两个顶点之间都可能存在联系,因此无法以数据元素在存储区的位置来表示元素之间的关系,即图没有顺序映像的存储结构,但可以借助数组来表示数据元素之间的关系。

  借助数组存储的方法有邻接矩阵表示法和邻接表表示法,边集表示法。

1.邻接矩阵表示法

1>定义

  图的邻接矩阵(adjacent matrix)表示法是使用数组来存储图结构的方法,也被称为数组表示法。 它采用两个数组来表示图:一个是用于存储所有顶点信息的一维数组,另一个是用于存储图中顶点之间关联关系的二维数组,这个关联关系数组也被称为邻接矩阵。

  

  

2>性质

邻接矩阵有如下特性:

  • (1)图中各顶点序号确定后,图的邻接矩阵是唯一确定的。
  • (2)无向图和无向网的琳姐矩阵是一个对称矩阵。
  • (3)无向图邻接矩阵中第i行或第i列的非0元素个数即为第i个顶点的度。
  • (4)有向图邻接矩阵第i行非0元素个数为第i个顶点的出度,第i列非0元素个数为第i个顶点的入度,第i个顶点的度为第i行与第i列非0元素个数之和。
  • (5)无向图的边数等于邻接矩阵中非0元素个数之和的一半,有向图的弧数等于邻接矩阵中非0元素个数之和。

3>优缺点

优点:

邻接矩阵表示法对于以图的顶点为主的运算比较适合。

缺点:

除完全图外,其他图的邻接矩阵有许多零元素,特别是当n值较大,而边数相对完全图的边n-1又少的多时,则此矩阵称为稀疏矩阵,非常浪费存储空间。

3>表示

  

2.邻接表表示法

  邻接表(adjacency list)是图的一种链式存储方法,邻接表表示法类似于树的孩子链表表示法。

  在邻接表中对于图G中的每个顶点vi建立一个单链表,将所有邻接于vi的顶点vj链成一个单链表,并在表头附设一个表头结点,这个单链表就称为顶点vi的邻接表。

1>结点

  邻接表中共有两种结点结构,分别是边表结点和表头结点。

  

邻接表中的每一个结点均包含有两个域:邻接点域和指针域。

  • 邻接点域用于存放与定点vi相邻接的一个顶点的序号。
  • 指针域用于指向下一个边表结点。

边表结点由3个域组成:

  • 邻接点域(adjvex)指示与定点vi邻接的顶点在图中的位置。
  • 链域(nextdge)指向下一条边所在的结点。
  • 数据域(info)存储和边有关的信息。

头结点由2个域组成:

  • 链域(firstedge)指向链表中的第一个结点之外。
  • 数据域(data)存储顶点相关信息。

如下图为邻接表的存储示例:

  

2>分类

在无向图的邻接表中,顶点的每一个边表结点对应于与顶点相关联的一条边。

在有向图的邻接表中,顶点的每一个边表结点对应于以顶点为始点的一条弧,因此也称有向图的邻接表的边表为出边表。

在有向图的邻接表中,将顶点的每个边表结点对应于以顶点为重点的一条弧,即用便捷点的邻接点域存储邻接到顶点的序号,由此构成的邻接表称为有向图的逆邻接表,逆邻接表有边表称为入边表。

3>邻接表与邻接矩阵的关系

邻接表与邻接矩阵的关系如下:

  • (1)对应于邻接矩阵的每一行有一个线形连接表;
  • (2)链接表的表头对应着邻接矩阵该行的顶点;
  • (3)链接表中的每个结点对应着邻接矩阵中该行的一个非零元素;
  • (4)对于无向图,一个非零元素表示与该行顶点相邻接的另一个顶点;
  • (5)对于有向图,非零元素则表示以该行顶点为起点的一条边的终点。

邻接表表示法示例如下:

  

4>邻接表的性质

邻接表的性质如下:

  • (1)图的邻接表表示不是惟一的,它与表结点的链入次序有关。
  • (2)无向图的邻接表中第i个边表的结点个数即为第i个顶点的度。
  • (3)有向图的邻接表中第i个出边表的结点个数即为第i个结点的出度,有向图的逆邻接表中第i个入边表的结点个数即为第i个结点的入度。
  • (4)无向图的边数等于邻接表中边表结点数的一半,有向图的弧数等于邻接表(逆邻接表)中出边表结点(入边表结点)的数目。

需要说明的是:

  • (1)在邻接表的每个线性链接表中各结点的顺序是任意的。
  • (2)邻接表中的各个线性链接表不说明他们顶点之间的邻接关系。
  • (3)对于无向图,某顶点的度数=该顶点对应的线性链表的结点数。
  • (4)对于有向图,某顶点的“出度”数=该顶点对应的线性链表的结点数;求某顶点的“入度”需要对整个邻接表的各链接扫描一遍,看有多少与该顶点相同的结点,相同结点数之和即为“入度”值。

3.边集表示法

  边集表示就是把每条边都存储起来作为一个集合。如下图所示

    

  表示的图为:

    

二、代码实现:

  邻接表表示法:

 1 import java.util.ArrayList;
 2 import java.util.List;
 3 
 4 
 5 /*邻接表*/
 6 public class GraphNode_AL {
 7     public int val;
 8     private List neighbors;// 邻居
 9 
10     public boolean checked = false;
11 
12     public GraphNode_AL(int val) {
13         this.val = val;
14     }
15 
16     public GraphNode_AL getNeighbor(int i) {
17         return neighbors.get(i);
18     }
19 
20     public void add(GraphNode_AL node) {
21         if (this.neighbors == null)
22             this.neighbors = new ArrayList<>();
23         this.neighbors.add(node);
24     }
25 
26     public int size() {
27         return this.neighbors.size();
28     }
29 }

  Graph类:

 1 /*邻接表来表示图*/
 2 public class Graph {
 3     public static void main(String[] args) {
 4         GraphNode_AL n1 = new GraphNode_AL(1);
 5         GraphNode_AL n2 = new GraphNode_AL(2);
 6         GraphNode_AL n3 = new GraphNode_AL(3);
 7         GraphNode_AL n4 = new GraphNode_AL(4);
 8         GraphNode_AL n5 = new GraphNode_AL(5);
 9         GraphNode_AL n6 = new GraphNode_AL(6);
10         GraphNode_AL n7 = new GraphNode_AL(7);
11         GraphNode_AL n8 = new GraphNode_AL(8);
12         GraphNode_AL n9 = new GraphNode_AL(9);
13 
14         n1.add(n2);
15         n1.add(n3);
16         n1.add(n7);
17         n1.add(n8);
18         n1.add(n9);
19 
20         n2.add(n1);
21         n2.add(n5);
22 
23         n3.add(n1);
24         n3.add(n5);
25         n3.add(n6);
26 
27         n4.add(n1);
28         n4.add(n6);
29         n5.add(n2);
30         n5.add(n3);
31         n6.add(n3);
32         n6.add(n4);
33         n7.add(n1);
34         n8.add(n1);
35         n9.add(n1);
36 
37         dfs(n9);
38 
39     }
40 
41     static void dfs(GraphNode_AL node) {
42         System.out.println(node.val);
43         node.checked = true;
44         for (int i = 0; i < node.size(); i++) {
45             GraphNode_AL graphNode = node.getNeighbor(i);
46             if (graphNode.checked == false)
47                 dfs(graphNode);
48         }
49     }
50 }

  表示的图为:

    

 

作者:|旧市拾荒|