1. 编程号首页

图的存储结构及实现_逻辑结构和存储结构的关系[通俗易懂]

编程小号 • • 未分类

图的存储结构及实现_逻辑结构和存储结构的关系[通俗易懂]以下包含一种顺序存储（邻接矩阵）和三种链式存储（邻接表、十字链表、邻接多重表）

以下包含一种顺序存储（邻接矩阵）和三种链式存储（邻接表、十字链表、邻接多重表）。

一、邻接矩阵

邻接矩阵是利用矩阵不同位置来表示任意两个顶点间的关系。对于含有 n n n个顶点（ v 1 , v 2 , . . . v n v_1,v_2,…v_n v1​,v2​,...vn​）的图或网，需要一个 n ∗ n n*n n∗n的矩阵用来存储。（为方便给这样的矩阵命名为A）

对于图，若存储的是无向图，如果两个顶点 v i ， v j v_i，v_j vi​，vj​之间存在边( v i ， v j v_i，v_j vi​，vj​)，则令 A [ i ] [ j ] = 1 A[i][j]=1 A[i][j]=1，否则为0。因此无向图的邻接矩阵一定沿左右对角线对称。若存储的是有向图，如果两个顶点 v i ， v j v_i，v_j vi​，vj​之间存在弧< v i ， v j v_i，v_j vi​，vj​>，则令 A [ i ] [ j ] = 1 A[i][j]=1 A[i][j]=1，否则为0。

对于网，也就是带权图，若存储的是无向网，如果两个顶点 v i ， v j v_i，v_j vi​，vj​之间存在边( v i ， v j v_i，v_j vi​，vj​)，则令 A [ i ] [ j ] A[i][j] A[i][j]等于这条边或弧上的权值，否则用 + ∞ +\infty +∞表示。若存储的是有向网，如果两个顶点 v i ， v j v_i，v_j vi​，vj​之间存在弧< v i ， v j v_i，v_j vi​，vj​>，则令 A [ i ] [ j ] A[i][j] A[i][j]等于这条边或弧上的权值，否则用 + ∞ +\infty +∞表示。

注意弧带有方向性。
两个顶点间存在边或弧指的是这两个顶点被直接联系而不是间接。

用邻接矩阵创建无向图

算法步骤：

  1. 输入总顶点数和总边数。
  2. 依次输入所有顶点的信息存入顶点数组中。
  3. 初始化矩阵，所有位置权值初始化为0。
  4. 构造邻接矩阵，依次输入每条边依附的两个顶点，并根据两个顶点在顶点数组中的位置将对应的矩阵位置处值修改为1。

例如对于下面这个图，分别输入顶点与边总数5,6，所有顶点A,B,C,D,E，再依次输入每条边依附的两个顶点(A,B)，(A,D)，(B,C)，(B,E)，(C,D)，(C,E)，就会得到右面的邻接矩阵。
在这里插入图片描述

import java.util.Scanner;

public class MatrixUDG { 
   
	private char[] vertex; 							// 顶点数组
	private int[][] matrix; 						// 二维矩阵
	private Scanner sc;

	public MatrixUDG() { 
   
		sc = new Scanner(System.in);
		System.out.println("分别输入顶点总数与边数，空格隔开：");
		int VerNums = sc.nextInt(); 				// 获取顶点总数
		int edgeNums = sc.nextInt(); 				// 获取边总数
		matrix = new int[VerNums][VerNums];
		vertex = new char[VerNums];
		// 所有顶点存入数组
		System.out.println("输入所有顶点，顶点间空格隔开：");
		vertexInArray();
		// 创建矩阵，因为二维数组属于成员变量带有默认值，所以这里省略了初始化0
		System.out.println("依次输入每条边依附的两个顶点，每输入一对回车，顶点间空格隔开：");
		creatMatrix(edgeNums);
		// 打印邻接矩阵
		System.out.println("该图的邻接矩阵：");
		printMatrix();
	}

	private void vertexInArray() { 
   
		// 先读取一次取走缓存中的回车符，这里与算法无关
		sc.nextLine();
		String str = sc.nextLine().replaceAll(" ", "");
		// 输入时每个顶点只能以一个字符表示
		for (int i = 0; i < vertex.length; i++) { 
   
			vertex[i] = str.charAt(i);
		}
	}

	private void creatMatrix(int edgeNums) { 
   
		String str;
		int m, n;
		for (int i = 0; i < edgeNums; i++) { 
   
			str = sc.nextLine().replaceAll(" ", "");
			m = locate(str.charAt(0));
			n = locate(str.charAt(1));
			matrix[m][n] = matrix[n][m] = 1;
		}
	}

	// 返回顶点在顶点数组中的位置
	private int locate(char c) { 
   
		int i = 0;
		for (; i < vertex.length; i++) { 
   
			if (c == vertex[i])
				break;
		}
		return i;
	}

	private void printMatrix() { 
   
		for (int i = 0; i < matrix.length; i++) { 
   
			for (int j = 0; j < matrix.length; j++) { 
   
				System.out.print(matrix[i][j] + "\t");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) { 
   
		MatrixUDG m = new MatrixUDG();
		m.sc.close();
	}
}

时间复杂度跟根据具体的算法实现来说，上面的执行时间主要用在了定位顶点在顶点数组中的位置，所以跟总边数及具体的查找算法相关。如果存储的是网那么二维数组的初始化也要考虑进去。

邻接矩阵表示法的优缺点

优点：

  • 方便判断两顶点间是否有边，直接根据A[i][j]的值判断。
  • 方便计算图中顶点的度，对于顶点 i，无向图中第 i 行或第 i 列的元素之和就是 i 的度。有向图中第 i 行元素之和为 i 的出度，第 i 列元素之和为 i 的入度。网因为存储的是权值所以没有这种关系。

缺点：

  • 不方便增加或删除结点，因为要重新修改二维数组。
  • 不方便统计边的数目，必须要遍历整个二维数组才能确定。
  • 空间复杂度较高，存储n个顶点的图的空间复杂度 O ( n 2 ) Ο(n^2) O(n2)。

二、邻接表

邻接表的存储结构概括来讲就是“数组+链表”形式，对应分别存储图的顶点与边。数组中存放图的所有顶点，各顶点又作为表头结点，后面以单链表的形式链接上它的所有邻接点，以头结点和邻接点两个顶点表示一条边。

这个单链表也叫做边表，为什么说它存的是边可以这样看，下面的A顶点与之相连的为(0,3)(0,1)两条边，B顶点与之相连的为(1,4)(1,2)(1,0)三条边。

比如下面左边这个无向图对应的邻接表，后面的数字表示每个邻接点在数组中的位置：
在这里插入图片描述

用邻接表创建无向图

算法步骤：

  1. 输入顶点总数和边总数。
  2. 依次输入所有顶点的信息存入顶点数组中作为单链表的表头结点。如果指针域没有默认值还需要初始化为null。
  3. 创建邻接表，依次输入每条边依附的两个顶点，根据这两个顶点在顶点数组中的位置插入到对应头结点的单链表中。例如顶点 i 与顶点 j，i 插在头结点 j 的单链表中，j 插在头结点 i 的单链表中。(从这可以看出两个顶点 i, j 间如果有边，则 i 的链表中有 j，j 的链表中有 i )

下面代码中分别输入顶点与边总数5,6，所有顶点A,B,C,D,E，再依次输入每条边依附的两个顶点(A,B)，(A,D)，(B,C)，(B,E)，(C,D)，(C,E)，就会得到上图中右面的邻接表。

import java.util.Scanner;

//表头结点
class VertexNode { 
   
	char data;
	EdgeNode next;

	public VertexNode(char verName) { 
   
		data = verName;
	}
}

//边结点
class EdgeNode { 
   
	int index;
	EdgeNode next;

	public EdgeNode(int num) { 
   
		index = num;
	}
}

public class AdjacencyListUDG { 
   
	VertexNode[] array; 					// 存表头结点的数组
	Scanner sc;

	public AdjacencyListUDG() { 
   
		sc = new Scanner(System.in);
		System.out.println("输入顶点总数和边数，空格隔开：");
		int verNums = sc.nextInt();
		int edgeNums = sc.nextInt();
		array = new VertexNode[verNums];
		System.out.println("输入所有顶点，顶点间空格隔开：");
		vertexInArray();
		System.out.println("依次输入每条边依附的两个顶点，每输入一对回车，顶点间空格隔开：");
		creatList(edgeNums);
		System.out.println("邻接表为：");
		printList();
	}

	private void vertexInArray() { 
   
		sc.nextLine();
		String str = sc.nextLine().replaceAll(" ", "");
		for (int i = 0; i < array.length; i++) { 
   
			array[i] = new VertexNode(str.charAt(i));
		}
	}

	private void creatList(int edgeNums) { 
   
		String str;
		int front, behind;
		EdgeNode node;
		for (int i = 0; i < edgeNums; i++) { 
   
			str = sc.nextLine().replaceAll(" ", "");
			front = locate(str.charAt(0));
			behind = locate(str.charAt(1));
			// 这里采用的是头插法
			node = new EdgeNode(front);
			node.next = array[behind].next;
			array[behind].next = node;

			node = new EdgeNode(behind);
			node.next = array[front].next;
			array[front].next = node;
		}
	}

	private void printList() { 
   
		EdgeNode node;
		for (int i = 0; i < array.length; i++) { 
   
			System.out.print(i + ":" + array[i].data);
			node = array[i].next;
			while (node != null) { 
   
				System.out.print("-->" + node.index);
				node = node.next;
			}
			System.out.println();
		}
	}

	private int locate(char c) { 
   
		int i = 0;
		for (; i < array.length; i++) { 
   
			if (c == array[i].data)
				break;
		}
		return i;
	}

	public static void main(String[] args) { 
   
		AdjacencyListUDG lt = new AdjacencyListUDG();
		lt.sc.close();
	}
}

时间复杂度 O ( n + e ) Ο(n+e) O(n+e)，n为顶点总数，e为边总数。分别对应初始化数组中的所有头结点和将边结点插入到单链表的操作。

邻接表表示法的优缺点

优点：

  • 便于增删顶点，所有的链表结构都方便增删操作，只需要修改指针。
  • 方便统计边的数目。边的总数 = 所有单链表中边结点总数 x 1 2 \frac 12 21​，因为每条边会插入两个边结点。
  • 空间复杂度较低，无向图存储需要n个头结点+2e个边结点的空间，有向图存储需要n个头结点+e个边结点的空间，空间复杂度都为 O ( n + e ) Ο(n+e) O(n+e)。

空间复杂度较低不是指一定比邻接矩阵存储低，虽然相比邻接矩阵，邻接表只为存在边的邻接点建立存储空间，但因为结点结构中含有链域，如果是网还需要增加存储权值的空间，所以邻接表只适用于存储稀疏图。具体稀疏到什么地步，可以根据用矩阵存储和用邻接表存储各自占据的空间之间的大小来判断。

缺点：

  • 不方便判断两顶点之间是否有边，这需要扫描两顶点中任一个顶点作为头结点的单链表，最坏情况下时间复杂度 O ( n ) Ο(n) O(n)。
  • 不方便统计有向图中顶点的度。对于无向图顶点 i 的度等于以顶点 i 为头结点的单链表中的边结点数，可以遍历这个单链表得到。而对于有向图，一条单链表中的边结点数只等于头结点顶点的出度，求入度需要遍历所有头结点的单链表。

三、十字链表

十字链表主要是为了解决邻接表中不方便计算有向图入度的问题， 与邻接表相比头结点和边结点都多增加了一个指向入度弧的指针域，在原来邻接表的基础上将每个头结点顶点的所有入度弧以单链表形式和这个头结点链接起来。所以十字链表可以看成是邻接表与逆邻接表的结合，用来存储有向图。

其中头结点由数据域、入度弧指针域、出度弧指针域三部分组成，边结点由弧尾位置域、弧头位置域、入度弧指针域、出度弧指针域四部分组成，如果存储的是网还需要增加存储权值的空间。

例如对于下面左边的这个有向图，对应的十字链表为（蓝线指向下一个出度弧，红线指向下一个入度弧）：
在这里插入图片描述
用十字链表创建有向图

算法步骤与邻接表类似，唯一区别是在除了将新创建的弧链接在以它弧尾顶点为头结点的单链表中作为这个顶点的出度弧之外，还需要将这条弧链接在以它弧头顶点为头结点的单链表中作为该顶点的入度弧。

下面代码中分别输入顶点与弧总数4,7，所有顶点A,B,C,D，再依次输入每条弧的弧尾弧头两个顶点(A,B)，(A,C)，(D,A)，(D,B)，(D,C)，(C,A)，(C,D)，就会得到上图中右面的十字链表。

每个单链表中弧出现的先后顺序可能和上面有些不同，这是因为链表的插入方式导致。

import java.util.Scanner;

class VertexNode { 
   
	char data;
	EdgeNode inNext;
	EdgeNode outNext;

	public VertexNode(char verName) { 
   
		data = verName;
	}
}

class EdgeNode { 
   
	int tailIndex;							// 弧尾顶点位置
	int headIndex;							// 弧头顶点位置
	EdgeNode inNext;						// 入度弧指针域
	EdgeNode outNext;						// 出度弧指针域

	public EdgeNode(int tail, int head) { 
   
		tailIndex = tail;
		headIndex = head;
	}
}

public class OrthogonalListDG { 
   
	VertexNode[] array;
	Scanner sc;

	public OrthogonalListDG() { 
   
		sc = new Scanner(System.in);
		System.out.println("输入顶点总数和边数，空格隔开：");
		int verNums = sc.nextInt();
		int edgeNums = sc.nextInt();
		array = new VertexNode[verNums];
		System.out.println("输入所有顶点，顶点间空格隔开：");
		vertexInArray();
		System.out.println("依次输入每条弧的弧尾和弧头顶点，每输入一对回车，顶点间空格隔开：");
		creatList(edgeNums);
		System.out.println("十字链表为：");
		printList();
	}

	private void vertexInArray() { 
   
		sc.nextLine();
		String str = sc.nextLine().replaceAll(" ", "");
		for (int i = 0; i < array.length; i++) { 
   
			array[i] = new VertexNode(str.charAt(i));
		}
	}

	private void creatList(int edgeNums) { 
   
		String str;
		int head, tail;
		EdgeNode node;
		for (int i = 0; i < edgeNums; i++) { 
   
			str = sc.nextLine().replaceAll(" ", "");
			tail = locate(str.charAt(0));
			head = locate(str.charAt(1));

			node = new EdgeNode(tail, head);
			// 前插法插入出度弧
			node.outNext = array[tail].outNext;
			array[tail].outNext = node;
			// 前插法插入入度弧，也是相对创建邻接表唯一不同的地方
			node.inNext = array[head].inNext;
			array[head].inNext = node;
		}
	}

	private void printList() { 
   
		EdgeNode node;
		for (int i = 0; i < array.length; i++) { 
   
			System.out.print("出度弧：" + i + ":" + array[i].data);
			node = array[i].outNext;
			while (node != null) { 
   
				System.out.print("-->(" + node.tailIndex + "," + node.headIndex + ")");
				node = node.outNext;
			}
			System.out.println();

			System.out.print("入度弧：" + i + ":" + array[i].data);
			node = array[i].inNext;
			while (node != null) { 
   
				System.out.print("-->(" + node.tailIndex + "," + node.headIndex + ")");
				node = node.inNext;
			}
			System.out.println();
		}
	}

	private int locate(char c) { 
   
		int i = 0;
		for (; i < array.length; i++) { 
   
			if (c == array[i].data)
				break;
		}
		return i;
	}

	public static void main(String[] args) { 
   
		OrthogonalListDG lt = new OrthogonalListDG();
		lt.sc.close();
	}
}

时间复杂度和创建邻接表相同，为 O ( n + e ) Ο(n+e) O(n+e)。n为顶点总数，e为弧总数。

四、邻接多重表

邻接多重表主要是为了解决邻接表存储无向图时边重复存储的问题。解决方法是每读取一行输入获取到两个边顶点时不是像邻接表那样直接创建两个边结点分别插入到两个单链表中，而是只创建一条边，让以边两端顶点为头结点的两个单链表都链接上这条边。因为不同头结点的邻边不同，所以势必要给边结点增加一个指针域，用来构建另一个头结点的单链表。

与邻接表相比头结点结构不变，边结点结构为两个用来存储边两端顶点位置的域 + 两个分别用来保存不同头结点的单链表指针的域，有时涉及到遍历可能还需要设置一个标记域，标记是否被访问。

下面是它的一个邻接多重表，对应的邻接多重表不唯一。

在这里插入图片描述
代码实现中将边插入到两个链表的部分还有些冲突，暂时没有想到好的解决办法，搞明白了回来补上。

类似于邻接多重表，个人觉得也可以直接分别用一个顶点数组和一个边数组来存放图的所有顶点和边，只是相比于邻接多重表，这种存储方式没有构建顶点与其邻边之间的链表，不方便统计顶点的邻边。

今天的文章图的存储结构及实现_逻辑结构和存储结构的关系[通俗易懂]分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/86748.html

赞 (0)
编程小号编程小号
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注