一直想写一篇关于图的博客，但是奈何功力不够，迟迟没有下手。查看多方资料后，觉得写一篇笔记供自己参考，各位看官轻喷。感谢这个博客https://blog.csdn.net/qq_35644234/article/details/57083107
图是顶点(vetex)和边(edge)的集合。因为图的数据结构有很多种表示方式，容易给我这种渣渣造成很多困扰。就是在没有搞会图的算法之前，先被这些存储方式搞晕了。简单来说，图有各种存储方式是因为每个存储方式有优缺点，我主要讲两种，一种是邻接矩阵，一种是邻接表。
下面待我一一道来。
1. 图的存储结构--邻接矩阵。
这种方式很简单，构建两个数组存储图的信息，一个一维数组存储顶点数据的信息，一个二维数组（也就是矩阵）存储边的信息。
如果图有n个顶点，那么邻接矩阵为n*n的方阵，方阵每个元素的值如下：
邻接矩阵
举个栗子：
图实例
有向图类似，不在赘述。
这里再说一句，如果我们需要将图表示成一个网的时候（也就是边赋权重）。假设有n个顶点，公式如下：
接下来是代码实现
import java.util.Scanner;
public class Graph {
private int[] vex; //顶点数组
private int[][] adjMatrix; //图的邻接矩阵
private int vexNum; //顶点个数
private int edge; //边的条数
public void createGraph(){
Scanner s = new Scanner(System.in);
System.out.println("请输入顶点个数：");
this.vexNum = s.nextInt();
System.out.println("请输入边的个数：");
this.edge = s.nextInt();
this.vex = new int[vexNum];
this.adjMatrix = new int[vexNum][vexNum];
//后面省略
}
2. 图的存储结构--邻接表
邻接表是一种链式存储结构。因为当图的顶点多边少的时候，矩阵将会很庞大，但是里边全都是0，浪费空间。邻接表主要是声明两个结构，一个是用来存储顶点信息的数组（对象数组，存储数据和被指向顶点的地址），一个是表节点（被指向的顶点）。
邻接表结构
举个例子：
无向图例子
下面结合代码说明邻接表的结构：
import java.util.Scanner;
public class Graph2 {
private int vexNum;//图的顶点数
private int edge; //图的边数
//存储被指向的顶点信息
class ArcNode{
int adjvex; //某条边指向的那个顶点的位置，一般是数组的下标
ArcNode nextarc; //指向下一个表结点
}
//存储顶点的信息
class Vnode{
int data; //顶点信息
ArcNode firstArc; //指向第一条依附于该顶点边的信息
}
public void createGraph(){
Scanner s = new Scanner(System.in);
System.out.println("请输入顶点个数：");
this.vexNum = s.nextInt();
System.out.println("请输入边的个数：");
this.edge = s.nextInt();
Vnode[] vnodes = new Vnode[vexNum];
//后面省略
}
}
后面还有针对有向图的存储结构---十字链表，针对无向图的存储结构，邻接多重表，只要理解了上面的这些，这些结构不难理解。
《算法第四版》推荐的存储结构，无论是有向图还是无向图，都用邻接表的形式，比较通用。还有，无向图的邻接表一般都是一条边<w,v>,w顶点要接v，v也要接w。
下面是完整的图的代码，代码的实现方式和上图中的结构有一丢丢的不同，是这样的图，不过大体上也差不多：
package com.xushu.Undirectedgraph;
/**
* Java: 邻接表表示的"无向图(List Undirected Graph)"
*/
import java.io.IOException;
import java.util.Scanner;
public class ListUDG {
// 邻接表中表对应的链表的顶点
private class ENode {
int ivex; // 该边所指向的顶点的位置
ENode nextEdge; // 指向下一条弧的指针
}
// 邻接表中表的顶点
private class VNode {
char data; // 顶点信息
ENode firstEdge; // 指向第一条依附该顶点的弧
};
private VNode[] mVexs; // 顶点数组
// /*
// * 创建图(自己输入数据)
// */
// public ListUDG() {
//
// // 输入"顶点数"和"边数"
// System.out.printf("input vertex number: ");
// int vlen = readInt();
// System.out.printf("input edge number: ");
// int elen = readInt();
// if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
// System.out.printf("input error: invalid parameters!\n");
// return ;
// }
//
// // 初始化"顶点"
// mVexs = new VNode[vlen];
// for (int i = 0; i < mVexs.length; i++) {
// System.out.printf("vertex(%d): ", i);
// mVexs[i] = new VNode();
// mVexs[i].data = readChar();
// mVexs[i].firstEdge = null;
// }
//
// // 初始化"边"
// //mMatrix = new int[vlen][vlen];
// for (int i = 0; i < elen; i++) {
// // 读取边的起始顶点和结束顶点
// System.out.printf("edge(%d):", i);
// char c1 = readChar();
// char c2 = readChar();
// int p1 = getPosition(c1);
// int p2 = getPosition(c2);
// // 初始化node1
// ENode node1 = new ENode();
// node1.ivex = p2;
// // 将node1链接到"p1所在链表的末尾"
// if(mVexs[p1].firstEdge == null)
// mVexs[p1].firstEdge = node1;
// else
// linkLast(mVexs[p1].firstEdge, node1);
// // 初始化node2
// ENode node2 = new ENode();
// node2.ivex = p1;
// // 将node2链接到"p2所在链表的末尾"
// if(mVexs[p2].firstEdge == null)
// mVexs[p2].firstEdge = node2;
// else
// linkLast(mVexs[p2].firstEdge, node2);
// }
// }
/*
* 创建图(用已提供的矩阵)
*
* 参数说明：
* vexs -- 顶点数组
* edges -- 边数组
*/
public ListUDG(char[] vexs, char[][] edges) {
// 初始化"顶点数"和"边数"
int vlen = vexs.length;
int elen = edges.length;
// 初始化"顶点"
mVexs = new VNode[vlen];
for (int i = 0; i < mVexs.length; i++) {
mVexs[i] = new VNode();
mVexs[i].data = vexs[i];
mVexs[i].firstEdge = null;
}
// 初始化"边"
for (int i = 0; i < elen; i++) {
// 读取边的起始顶点和结束顶点
char c1 = edges[i][0];
char c2 = edges[i][1];
// 读取边的起始顶点和结束顶点
int p1 = getPosition(edges[i][0]);
int p2 = getPosition(edges[i][1]);
//初始化两次，保证w后有v，v后有w
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
// 将node1链接到"p1所在链表的末尾"
if(mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1;
else
linkLast(mVexs[p1].firstEdge, node1);
// 初始化node2
ENode node2 = new ENode();
node2.ivex = p1;
// 将node2链接到"p2所在链表的末尾"
if(mVexs[p2].firstEdge == null)
mVexs[p2].firstEdge = node2;
else
linkLast(mVexs[p2].firstEdge, node2);
}
}
/*
* 将node节点链接到list的最后
*/
private void linkLast(ENode list, ENode node) {
ENode p = list;
while(p.nextEdge!=null)
p = p.nextEdge;
p.nextEdge = node;
}
/*
* 返回ch位置
*/
private int getPosition(char ch) {
for(int i=0; i<mVexs.length; i++)
if(mVexs[i].data==ch)
return i;
return -1;
}
/*
* 读取一个输入字符
*/
private char readChar() {
char ch='0';
do {
try {
ch = (char)System.in.read();
} catch (IOException e) {
e.printStackTrace();
}
} while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
return ch;
}
/*
* 读取一个输入字符
*/
private int readInt() {
Scanner scanner = new Scanner(System.in);
return scanner.nextInt();
}
/*
* 打印矩阵队列图
*/
public void print() {
System.out.printf("List Graph:\n");
for (int i = 0; i < mVexs.length; i++) {
System.out.printf("%d(%c): ", i, mVexs[i].data);
ENode node = mVexs[i].firstEdge;
while (node != null) {
System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);
node = node.nextEdge;
}
System.out.printf("\n");
}
}
public static void main(String[] args) {
char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
char[][] edges = new char[][]{
{'A', 'C'},
{'A', 'D'},
{'A', 'F'},
{'B', 'C'},
{'C', 'D'},
{'E', 'G'},
{'F', 'G'}};
ListUDG pG;
// 自定义"图"(输入矩阵队列)
//pG = new ListUDG();
// 采用已有的"图"
pG = new ListUDG(vexs, edges);
pG.print(); // 打印图
}
}
