从今天开始修炼数据结构]图结构的五种物理存储方式、深度优先搜索的递归和非递归写法、广度优先搜索
我们之前介绍了线性关系的线性表，层次关系的树形结构，下面我们来介绍结点之间关系任意的结构，图。
一、相关概念
1，图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
2，各种图定义
若两顶点之间的边没有方向，则称这条边为无向边Edge，用无序偶对(v1,v2)来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。
若从顶点v1到v2的边有方向，则称这条边为有向边，也称为弧（Arc），表示为有序偶，称v1为弧尾，v2为弧头。若图中任意两个顶点之间的边都是有向边，则称该图为有向图。
注意无向边用(),有向边用<>
图按照边或弧的多少分为稀疏图和稠密图，但划分边界比较模糊。任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复边或顶点回到自身的边的叫做简单图。
图上边或弧带权则称为网。
3，图的顶点与边之间的关系
图中顶点之间有邻接点Adjacent的概念，v和v‘相邻接，边(v,v')依附于顶点v和v’，或者说边(v,v')与顶点v和v’相关联。顶点的度Degree是与v相关联的边的数目，记作TD（v）。
有向图中有入度ID(v)和出度OD(V)的概念.
图中的顶点间存在路径则说明是连通的，如果路径最终回到起始点则成为环，不重复的路径称为简单路径。顶点不重复出现的回路，叫做简单回路或简单环。
若任意两点之间都是连通的，则成为连通图，有向则是强连通图。图中有子图，若子图极大连通则称该子图为连通分量，有向的则称为强连通分量。
无向图是连通图且n个顶点有n-1条边则叫做生成树。有向图中一顶点入度为0，其他顶点入度为1的叫做有向树，一个有向图可以分解为若干有向树构成的生成森林。
二、图的抽象数据类型
三、图的存储结构
图结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素间的关系；而多重链表的方式又有操作的不便，因此对于图来说，它实现物理存储是个难题，下面我们来看前辈们已经提供的五种不同的存储结构
1，邻接矩阵
图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。若无向图中存在这条边，或有向图中存在这条弧，则矩阵中的该位置置为1，否则置0.如下
邻接矩阵是如何实现图的创建的呢？ 代码如下
复制代码
/*
顶点的包装类
*/
public class Vertex{
private T data;
public Vertex(T data){
this.data = data;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
}
复制代码
复制代码
/*
邻接矩阵实现图的创建
*/
public class MGraph {
private Vertex[] vertexs;
private int[][] edges;
private int numVertex; //顶点的实际数量
private int maxNumVertex; //顶点的最大数量
private int INFINITY = 65535;
public MGraph(int maxNumVertex){
this.maxNumVertex = maxNumVertex;
this.vertexs = (Vertex[]) new Vertex[maxNumVertex];
this.edges = new int[maxNumVertex][maxNumVertex];
for (int i = 0; i < numVertex; i++){
for (int j = 0; j < numVertex; j++){
edges[i][j] = INFINITY;
}
}
for (int i = 0; i < numVertex; i++) {
edges[i][i] = 0;
}
}
public int getNumVertex(){
return numVertex;
}
public int getMaxNumVertex(){
return maxNumVertex;
}
public boolean isFull(){
return numVertex == maxNumVertex;
}
public void addVertex(T data){
if(isFull()){
throw new RuntimeException("图满了");
}
Vertex v = new Vertex(data);
vertexs[numVertex++] = v;
}
/**
* 删除图中与data相等的顶点
* @param data 要删除的顶点的data值
* @return 返回删除了几个顶点
*/
public int removeVertex(T data){
int flag = 0;
for (int i = 0; i < numVertex; i++){
if (vertexs[i].getData().equals(data)){
for (int j = i; j < numVertex - 1; j++){
vertexs[j] = vertexs[j + 1];
}
//删除矩阵的第 i 行
for (int row = i; row < numVertex - 1; row++){
for (int col = 0; col < numVertex; col++){
edges[col][row] = edges[col][row + 1];
}
}
//删除矩阵的第 i 列
for (int row = 0; row < numVertex; row++){
for (int col = i; col < numVertex - 1; col++){
edges[col][row] = edges[col + 1][row];
}
}
numVertex--;
flag++;
}
}
return flag;
}
private int getIndexOfData(T data){
int i = 0;
while (!vertexs[i].getData().equals(data)){
i++;
}
return i;
}
/**
* 若为无向图，data的顺序随意；若为有向图，则添加的边是data1指向data2
* @param data1 弧尾
* @param data2 弧头
* @param weight 权值
*/
public void addEdge(T data1, T data2, int weight){
int index1 = getIndexOfData(data1);
int index2 = getIndexOfData(data2);
edges[index1][index2] = weight;
}
public void removeEdge(T data1, T data2){
int index1 = getIndexOfData(data1);
int index2 = getIndexOfData(data2);
edges[index1][index2] = INFINITY;
}
public void printMatrix(){
for (int row = 0; row < numVertex; row++){
for (int col = 0; col < numVertex; col++){
System.out.print(edges[row][col] + " ");
}
System.out.println();
}
}
}
复制代码
邻接矩阵可以解决图的物理存储，但我们也发现，对于边相对顶点来说较少的图，这种结构是存在对存储空间的极大浪费的。如何解决呢？看下面
2，邻接表
我们在前面提到过，顺序存储结构存在预先分配内存可能造成空间浪费的问题，于是引出了链式存储结构。我们用类似于前面树结构中孩子表示法的方式，数组与链表相结合的存储方法称为邻接表。
处理方法：顶点用一维数组存储；每个顶点的所有邻接点构成一个线性表，用单链表存储。有向图称为顶点v的边表；无向图称为顶点v作为弧尾的出边表。
注：若是有向图，邻接表结构是类似的。由于有向图有方向，我们是以顶点为弧尾来存储边表的，这样很容易得到每个顶点的出度。但也有是为了便于确定顶点的入度，我们可以建立一个有向图的逆邻接表，即对每个顶点v1都建立一个链接为v1为弧头的表。
若是带权值的网图，可以在边表结点的定义中再增加一个weight的数据域，存储权值信息即可。
下面是邻接表存储图结构的代码实现
复制代码
public class VertexL {
private T data;
private EdgeL firstEdge;
public VertexL(T data)
{
this.data = data;
}
public void setFirstEdge(EdgeL e){
this.firstEdge = e;
}
public EdgeL getFirstEdge(){
return firstEdge;
}
public T getData(){
return data;
}
}
复制代码
复制代码
public class EdgeL {
private int adjvex; //存储邻接点对应的下标
private EdgeL nextEdge; //存储
public EdgeL(int adjvex){
this.adjvex = adjvex;
}
public EdgeL(int adjvex, EdgeL e){
this.adjvex = adjvex;
this.nextEdge = e;
}
public EdgeL getNextEdge(){
return nextEdge;
}
public void setNextEdge(EdgeL e){
this.nextEdge = e;
}
public int getAdjvex(){
return adjvex;
}
}
复制代码
复制代码
/*
无向图（无权值）的邻接表存储。
*/
public class GraphAdjList {
private VertexL[] vertexs;
private int numVertex;
private int maxNumVertex;
public GraphAdjList(int maxNumVertex){
this.maxNumVertex = maxNumVertex;
this.vertexs =(VertexL[]) new VertexL[maxNumVertex];
numVertex = 0;
}
public boolean isFull(){
return numVertex == maxNumVertex;
}
private int getNumVertex(){
return numVertex;
}
/**
* 添加顶点
* @param data
*/
public void addVertex(T data){
if (isFull()){
throw new IndexOutOfBoundsException();
}
VertexL v = new VertexL(data);
vertexs[numVertex++] = v;
}
/**
* 添加边
* @param data1
* @param data2
*/
public void addEdge(T data1, T data2){
int indexOfData1 = getIndex(data1);
int indexOfData2 = getIndex(data2);
if (vertexs[indexOfData1].getFirstEdge() == null){
vertexs[indexOfData1].setFirstEdge(new EdgeL(indexOfData2));
}else {
vertexs[indexOfData1].getFirstEdge().setNextEdge(new EdgeL(indexOfData2, vertexs[indexOfData1].getFirstEdge().getNextEdge()));
}
if (vertexs[indexOfData2].getFirstEdge() == null){
vertexs[indexOfData2].setFirstEdge(new EdgeL(indexOfData1));
}else {
vertexs[indexOfData2].getFirstEdge().setNextEdge(new EdgeL(indexOfData1, vertexs[indexOfData1].getFirstEdge().getNextEdge()));
}
}
private int getIndex(T data){
int i = 0;
for (; i < numVertex; i++){
if (data.equals(vertexs[i].getData())){
break;
}
}
if (!data.equals(vertexs[i].getData()) && i == numVertex){
throw new NullPointerException();
}
return i;
}
/**
* 删除边
* @param data1
* @param data2
*/
public void removeEdge(T data1, T data2){
int indexOfData1 = getIndex(data1);
int indexOfData2 = getIndex(data2);
VertexL v = vertexs[indexOfData1];
EdgeL e = v.getFirstEdge();
if (e.getAdjvex() == indexOfData2){
if (v.getFirstEdge().getNextEdge() == null) {
v.setFirstEdge(null);
}else {
v.setFirstEdge(e.getNextEdge());
}
}else {
while (e.getNextEdge().getAdjvex() != indexOfData2){
e = e.getNextEdge();
}
if (e.getNextEdge().getNextEdge() != null) {
e.setNextEdge(e.getNextEdge().getNextEdge());
}else {
e.setNextEdge(null);
}
}
}
/**
* 删除顶点
* @param data
*/
public void removeVertex(T data){
int index = getIndex(data);
for (int i = 0; i < numVertex; i++){
if (i == index){
continue;
}
removeEdge(vertexs[i].getData(), data);
}
for (int i = index; i < numVertex - 1; i++){
vertexs[i] = vertexs[i + 1];
}
}
复制代码
3，十字链表
对于有向图来说，邻接表只关心了出度问题，想了解入度就必须遍历整个图才能知道；反之，逆邻接表解决了入度问题，却不了解出度的情况。那么能不能把邻接表和逆邻接表结合一下呢？
这就是下面要讲的存储方式：十字链表。
我们既然要结合邻接表和逆邻接表，就要先把顶点域融合一下如下
firstin表示入边表表头指针，指向该顶点入边表的第一个结点； firstout表示出边表表头指针，指向该顶点出边表的第一个结点。
下面我们来把边表结点结构也融合一下
其中tailvex是指弧起点在顶点表的下标 ； headvex是指弧终点在顶点表中的下标。
headlink是入边表指针域，指向同一个弧头的弧；taillink是出边表指针域，指向同一个弧尾的弧。 从新的边表结点的域可以看出来，每一个边表结点既承担了作为入边表的职责，也承担了作为出边表结点的职责。
例如下面这个例子
图中虚线箭头的含义就是此图的逆邻接表的表示。我们可以简单的理解为，比如第一行的边结点，就是表示从0指向3的有向弧，所以它一定是由0直接指向，并且由3虚线指向的。
再如图中唯一连续指向的从V0指向边10，再指向边20，可以发现弧头为0的都在同一列，弧尾同的都在同一行；由于V0有两个入度，所以虚线连续指向两个边结点。
十字链表的好处是因为结合了邻接表和逆邻接表，既容易找到入度，也容易找到出度。除了结构复杂一点，它创建图算法的时间复杂度是和邻接表相同的。因此在有向图中，十字链表是非常好的数据结构。
代码实现如下：
复制代码
/*
十字链表实现的图结构的弧定义
*/
public class EdgeOL {
private int tail;
private int head;
public EdgeOL(int tail, int head) {
this.tail = tail;
this.head = head;
}
}
/*
十字链表实现的图结构的顶点定义
*/
public class VertexOL {
private T data;
private EdgeOL firstIn;
private EdgeOL firstOut;
public VertexOL(T data) {
this.data = data;
}
}
复制代码
复制代码
/*
图结构的十字链表实现
*/
public class GraphOrthogonalList {
private VertexOL[] vertexs;
private int numVertex;
private int maxNumVertex;
public GraphOrthogonalList(int maxNumVertex){
this.maxNumVertex = maxNumVertex;
vertexs = (VertexOL[])new VertexOL[maxNumVertex];
}
public boolean isFull(){
return numVertex == maxNumVertex;
}
/**
* 添加新顶点
* @param data 新顶点的数据域
*/
public void addVertex(T data){
if (isFull()){
return;
}
VertexOL v = new VertexOL<>(data);
vertexs[numVertex++] = v;
}
public void addEdge(int tail, int head){
EdgeOL e = new EdgeOL(tail, head);
//头插法，形成十字链表
e.setTailLink(vertexs[tail].getFirstOut());
vertexs[tail].setFirstOut(e);
e.setHeadLink(vertexs[head].getFirstIn());
vertexs[head].setFirstIn(e);
}
/**
* 删除一个边结点
* @param tail
* @param head
*/
public void removeEdge(int tail, int head){
removeFromTailList(tail, head);
removeFromHeadList(tail, head);
}
/**
* 从邻接表中删除一个边结点
* @param tail
* @param head
*/
private void removeFromTailList(int tail, int head){
EdgeOL e = vertexs[tail].getFirstOut();
//从tailLink中删除它
if (e != null && e.getHeadVex() == head){
//如果e是第一个但不是最后一个结点，删除它
if (e.getTailLink() != null){
vertexs[tail].setFirstOut(e.getTailLink());
}else {
//如果e是第一个也是最后一个结点，删除它
vertexs[tail].setFirstOut(null);
}
}else if (e != null){
//如果e不是第一个结点，那么遍历链表找到要删除的边结点的上一个结点！！
while (e.getTailLink() != null && e.getTailLink().getHeadVex() != head){
e = e.getTailLink();
}
if (e.getHeadVex() != head){
//throw new NullPointerException();
//这里不能抛异常，因为后面要遍历删除边，抛异常会使程序终止
return;
}else {
e.setTailLink(e.getTailLink().getTailLink());
}
}
}
/**
* 从逆邻接表中删除一个边结点
* @param tail
* @param head
*/
private void removeFromHeadList(int tail, int head){
//从headLink中删除它
EdgeOL e = vertexs[head].getFirstOut();
if (e != null && e.getTailVex() == tail){
//如果e1是第一个但不是最后一个结点，删除它
if (e.getHeadLink() != null){
vertexs[head].setFirstIn(e.getHeadLink());
}else {
//如果e1是第一个也是最后一个结点，删除它
vertexs[head].setFirstIn(null);
}
}else if (e != null){
//如果e1不是第一个结点，那么遍历链表找到要删除的边结点的上一个结点！！
while (e.getHeadLink() != null
&& e.getHeadLink().getTailVex() != tail){
e = e.getHeadLink();
}
if (e.getTailVex() != tail){
//throw new NullPointerException();
return;
}else {
e.setHeadLink(e.getHeadLink().getHeadLink());
}
}
}
/**
* 删除index角标的顶点
* @param index
*/
public void removeVertex(int index){
if (index >= numVertex){
throw new NullPointerException();
}
//删除与该顶点有关的所有边
for (int i = numVertex - 1; i > 0; i--){
removeEdge(index, i);
removeEdge(i, index);
}
//删除该结点