目录
一、顺序存储
有向图：
无向图
代码实现
二、链式存储
有向图
无向图
代码实现
一、顺序存储
主要用到的是一个二维数组，也就是矩阵，直接上栗子：
有向图：
若要储存如下这个有向图：
需要建立一个二维数组
注意：
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->des
Node 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();
}
}
注意，不论是顺序存储还是链式存储，无向图都要对方向处理两次！（因为默认是两个方向的嘛）
