图的顺序存储和链式存储实现

本文主要是介绍图的顺序存储和链式存储实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、顺序存储

有向图：

无向图

代码实现

二、链式存储

有向图

无向图

代码实现

一、顺序存储

主要用到的是一个二维数组，也就是矩阵，直接上栗子：

有向图：

若要储存如下这个有向图：

需要建立一个二维数组

注意：

1、每一行代表的是图的每一个顶点

2、某一行的这一列，代表当前顶点所连接的下一个结点

初始化整个二维数组为0，在二维数组中：

因为A连向B，所以arr[A的下标][B的下标]=1（与0做出一个区分）

如果边有权重，就赋值权重

以此类推，储存图。

如图，这个矩阵就已经把无向图储存好了：

无向图

其实和无向图，并无区别，只需要做一个小小的修改。

以下面这个图为例：

顶点A连接B，所以在A所在行，的第b列进行赋值（如果有权重，赋值权重，没有赋值1）

与此同时，接下来是和有向图不一样的地方了哦：

在B所在行，的第a列进行赋值。

为什么？

很简单啊，就是用单项箭头来模拟出双向箭头嘛。

以此类推，生成二维矩阵：

代码实现

package CSDN;import GraphByList.GraphByList;import javax.swing.plaf.IconUIResource;/*** Created with IntelliJ IDEA* Description:* User:34398* Date:2024-05-11* Time:10:07*/public class GrapByMatrix {int[][] matrix;//定义一个二维数组，用来存放图char[] vertexS;//放所有的顶点boolean isDirect;//判断是否是有向图//当前主类的构造方法，传入所有的顶点，告诉程序是否有向图public GrapByMatrix(char[] arrV, boolean isDirect) {//初始化咱们的顶点数组vertexS=new char[arrV.length];for (int i = 0; i <arrV.length ; i++) {vertexS[i]=arrV[i];}this.isDirect = isDirect;matrix = new int[arrV.length][arrV.length];//初始化好二维数组的大小}/** src是其实顶点* des是目标顶点* weight是权重* 这个函数，把边和结点的信息放到二维数组中* */public void addEdge(char src, char des, int weight) {//查找对应v的下标int a = _getIndexOfV(src);int b = _getIndexOfV(des);matrix[a][b] = weight;if (!isDirect) {//如果是无向的，需要在相反位置继续赋值matrix[b][a] = weight;}}private int _getIndexOfV(char v) {for (int i = 0; i < vertexS.length; i++) {if (vertexS[i] == v) return i;}return -1;}public int getDevOfV(char v){int ret=0;//最终的答案//找到对应下标int index=_getIndexOfV(v);for (int i = 0; i <vertexS.length ; i++) {if(matrix[index][i]!=0){ret++;}}//如果是无向图，需要把所有指向v顶点的也要算上if(!isDirect){for (int i = 0; i <vertexS.length ; i++) {if(i==index){//因为这一个已经在上一个循环记录了，所以直接跳过//当然这个也可以不加，因为matrix[index][index]就是0，是本身，只是想在这里提一嘴continue;}if(matrix[i][index]!=0){ret++;}}}
return ret;}public void printGrap(){System.out.print("   ");for (int i = 0; i <vertexS.length ; i++) {System.out.print(vertexS[i]+" ");}System.out.println();for (int i = 0; i <vertexS.length ; i++) {System.out.print(vertexS[i]+"：");for (int j = 0; j < vertexS.length ; j++) {System.out.print(matrix[i][j]+" ");}System.out.println();}}}

测试：

结果：

二、链式存储

有向图

链式存储有点向哈希表，底层是用一个储存链表的数组实现的，专业术语叫：

邻接表。

以这个，有向图为例，进行链式存储

这样就把每一个顶点所指向的顶点全部表示好了。

注意：

有向图的度==入度+出度

所以要统计某一个有向图的度，只需要记录当前顶点链表的节点数，在加上其他链表含有当前顶点节点的数目即可。

例如在上面这个图中：

顶点A的度，

就等于A链表上的两个节点，在加上E链表上那个A节点

就等于3

无向图

此图为例：

在每一次进行链接的时候，记得在反方向在增加一个结点即可。

比如说A结点和B结点：

以此类推，得到：

注意：

如果要知道无向图vi顶点的度，只需要统计vi顶点所在链表的节点数即可。

例如，顶点A的度，就是A链表的的节点数，是2（注意顶点集合中的字母不是一个顶点哦，是一个引用）

代码实现

package CSDN;import java.util.ArrayList;/*** Created with IntelliJ IDEA* Description:* User:34398* Date:2024-05-11* Time:10:07*/
public class GraphByList {char[] vertexS;//放顶点的集合boolean isDirect;//是否是有向图ArrayList<Node> nodeList;//储存图的表//实例内部类public class Node {char src;//起始顶点char des;//目标顶点int weight;//权重Node next;//下一个结点//构造方法public Node(char src, char des, int weight) {this.src = src;this.des = des;this.weight = weight;}}//主类的构造方法//传入一个顶点集合public GraphByList(char[] vertexS, boolean isDirect) {//把顶点集合赋值this.vertexS = new char[vertexS.length];for (int i = 0; i < vertexS.length; i++) {this.vertexS[i] = vertexS[i];}this.isDirect = isDirect;//初始化表nodeList = new ArrayList<>(vertexS.length);//ArrayList底层是数组for (int i = 0; i < vertexS.length; i++) {nodeList.add( null);//全部设置为空,记住默认是尾插}}public void addEdge(char src, char des, int weight) {_addEdge(src, des, weight);//直接调用子方法if (!isDirect) {//如果是无向图，需要反方向在来一次_addEdge(des, src, weight);}}private void _addEdge(char src, char des, int weight) {int index1 = getIndexOfV(src);//计算起始顶点在char数组中的下标//先去链表里面找有没有src->desNode cur = nodeList.get(index1);while (cur != null) {//遍历时，如果有同一个路径，直接返回了if (cur.des == des) return;cur = cur.next;}//程序到达这里，说明需要创建一个节点，去表示顶点之间的信息Node newNode = new Node(src, des, weight);newNode.next = nodeList.get(index1);//头插链表nodeList.set(index1, newNode);//重新对index1下表的值进行赋值//        //程序到达这里，对这个表的头插已经搞定了}private int getIndexOfV(char v) {for (int i = 0; i < vertexS.length; i++) {if (vertexS[i] == v) return i;}return -1;}public int getDevOfV(char v) {int index = getIndexOfV(v);//计算对应数组的下标int ret = 0;//用来计算顶点的度Node cur = nodeList.get(index);while (cur != null) {//链表不为空，就一直遍历ret++;cur = cur.next;}if (isDirect) {//如果是有向图，需要遍历其余的链表(查看节点中的des是否和v一致)for (int i = 0; i < vertexS.length; i++) {if (i == index) continue;//这个链表不用遍历，因为在刚才的循环中，已经遍历了cur = nodeList.get(i);while (cur != null) {if (cur.des == v) ret++;cur = cur.next;}}}return ret;}/** 这个函数，用来打印邻接表* */public void printGraph(){for (int i = 0; i <vertexS.length ; i++) {Node cur=nodeList.get(i);System.out.print(vertexS[i]);if(cur==null){System.out.println(" -> "+"空");continue;//然后这个一个链表就完了，去遍历打印下一个链表}while(cur!=null){System.out.print(" -> "+cur.des);cur=cur.next;}System.out.print("-> 空");System.out.println();}}
}

测试类：

public class Test {public static void main(String[] args) {char[] array = {'A','B','C'};GraphByList graph = new GraphByList(array,true);graph.addEdge('A','B',1);graph.addEdge('B','A',1);graph.addEdge('B','C',1);graph.printGraph();}
}