数据结构之图(java语言版)

图是比树更复杂的结构，树是一对多的关系，图是多对多的关系。

一、基本概念

1、定义：图(graph)是由一些点(vertex)和这些点之间的连线(edge)所组成的；其中，点通常被成为"顶点(vertex)"，而点与点之间的连线则被成为"边或弧"(edege)。通常记为，G=(V,E)。

2、根据边是否有方向，将图可以划分为：无向图和有向图。

3、度，在无向图中，某个顶点的度是邻接到该顶点的边(或弧)的数目。

在有向图中，度还有"入度"和"出度"之分。
某个顶点的入度，是指以该顶点为终点的边的数目。而顶点的出度，则是指以该顶点为起点的边的数目。
顶点的度=入度+出度。

4、弧头和弧尾

有向图中：用<A,B>,<B,C>,<B,F>，A->B,A是弧尾，B是 弧头。

无向图中：用(A,B),(A,C),(B,C)，弧头和弧尾没有区别。

5、权

弧如果有值的话，称为权。

二、图的存储结构

图的存储结构有许多种，有邻接矩阵，邻接表，十字链表等。

邻接矩阵

用矩阵表示，用线性表存储数据，直观简单，但是浪费空间。

邻接表

用数组和链表表示结构，节省空间，可伸缩。

数组中存储了链表，链表的头节点代表定点，存储着数据及下一个顶点的引用，后面的节点存储着下标和下一个顶点的引用。

图来自《大话数据结构》

邻接表实现图

顶点及索引结构

顶点存储着数据和索引。

索引结构存储着顶点在数组中的下标。

class VexNode{//顶点
    String data;//顶点的数据
    EdgeNode fnext;//指向下一个顶点
    public VexNode(){}
    public VexNode(String data){
        this.data=data;
    }

}

class EdgeNode{//存储索引的节点
    int index;//索引
    //int weight;//权重
    EdgeNode next;//指向下一个顶点
}

建立图

使用数组存储链表。

构造方法传入顶点数和弧数。

public class Graph{

    public VexNode[] vexTable;//表
    private int numNode;//顶点数量
    private int size;//弧数
    
    public Graph(int numNode,int size){//构造函数，确定顶点数量
        this.numNode=numNode;
        this.size=size;
        vexTable=new VexNode[numNode];
    }

    public VexNode[] init(){//建立邻接表

        Scanner scanner =new Scanner(System.in);
        for(int i=0;i<numNode;i++){
            System.out.println("输入顶点数据");
            String data=scanner.next();
            VexNode node=new VexNode(data);
            vexTable[i]=node;
        }

        System.out.println("输入弧数据：");
        for(int k=0;k<size;k++){
            EdgeNode eNode=new EdgeNode();
            System.out.println("输入弧头：");
            int x=scanner.nextInt();
            System.out.println("输入弧尾：");
            int y=scanner.nextInt();

            eNode.index=y;
            eNode.next=vexTable[x].fnext;//头插法插入链中
            vexTable[x].fnext=eNode;

             eNode=new EdgeNode();//无向表需要弧头弧尾相同
             eNode.index=x;//如果建立的是有向表，将这四行代码去除即可
             eNode.next=vexTable[y].fnext;
             vexTable[y].fnext=eNode;

        }

        return vexTable;
    } 
}

查看弧

图的遍历比较复杂，我们可以先通过弧来查看图是否正确。

public void display(VexNode[] vexTable){
        System.out.println("打印表：");
        for(int i=0;i<numNode;i++){
            EdgeNode v=vexTable[i].fnext;
            while(v!=null){
                System.out.printf("(%s %s) ",vexTable[i].data,vexTable[v.index].data);
                v=v.next;
            }
            System.out.println();
        }
    }

用以下图来表示，数据输入顺序代表数据在数组中的位置。所以顶点输入顺序是

abcde

弧的输入顺序代表方向，不过我们建立的表是无向图，所以无所谓。

主函数中测试:

    public static void main(String[] args) {
        Graph graph=new Graph(5,5);
        VexNode[] vexTable=graph.init();
        graph.display(vexTable);
        
    }

输入数据：

输入顶点数据
a
输入顶点数据
b
输入顶点数据
c
输入顶点数据
d
输入顶点数据
e
输入弧数据：
输入弧头：
0
输入弧尾：
1
输入弧头：
1
输入弧尾：
3
输入弧头：
3
输入弧尾：
4
输入弧头：
4
输入弧尾：
2
输入弧头：
2
输入弧尾：
0

得到结果：

无向图会打印两次，有向图只有一个指向只会打印一次。

打印表：
(a c) (a b)
(b d) (b a)
(c a) (c e)
(d e) (d b)
(e c) (e d)

遍历

图的遍历有深度优先和广度优先。

深度优先遍历是从图中某个顶点出发,访问此顶点,然后从它未被访问到的邻接点出发深度优先遍历图,直到图中所有和它有路径相通的顶点都被访问到.，类似树的先序遍历。

广度优先遍历从某个顶点出发，访问其所有相邻元素，再从某个相邻元素开始广度优先遍历，类似树的层级遍历。

深度优先遍历

对遍历过的点需要标记，以免重复遍历。

同样可以递归来遍历。

	private int[] visit;//标记顶点是否遍历，1为已遍历，0为未遍历

    //深度优先遍历
    public void DFS(VexNode[] vexTable){
        this.visit=new int[numNode];//默认所有顶点都未遍历，数组中值都为0
        System.out.println("深度优先遍历：");
        for(int i=0;i<numNode;i++){
            if(visit[i]==0){    
                DFSVisit(vexTable, i);
            }
        }
        System.out.println();
    }

   public void DFSVisit(VexNode[] vexTable,int i){//对为遍历的数据输出
        EdgeNode eNode;
        visit[i]=1;//该顶点已经遍历
        System.out.print(" "+vexTable[i].data);
        eNode=vexTable[i].fnext;

        while(eNode!=null){
            if(visit[eNode.index]==0){
                DFSVisit(vexTable, eNode.index);
            }
            eNode=eNode.next;
        }
    }

广度优先遍历

广度优先遍历的特点是我们需要一个先进先出的容器来保存顶点。

使用队列即可，这里的队列可以采用之前的队列，也可以通过java已经提供好的LinkedList类来实现。

我们采用之前的链表队列：

public class Queue{
    SingleLinkList list;
    public Queue(){
        list=new SingleLinkList();
    }

    public void enQueue(Object e) {
        list.add(e);
        System.out.println("入队");
	}
	
	public Object deQueue() {
        Object e=list.get(1);
        list.remove(1);
        System.out.println("出队");
		return e;
	}
	
	public void display() {
		list.display();
    }
    
    public int getSize(){
        return list.getSize();
    }
}

广度优先如下：

    private Queue queue;
    //广度优先遍历
    public void BFS(){
        this.visit=new int[numNode];//默认所有顶点都未遍历，数组中值都为0
        System.out.println("广度优先遍历：");
        this.queue=new Queue();//建立队列

        for(int i=0;i<numNode;i++){
            if(visit[i]==0){
                BFSVisit();
            }
        }
        System.out.println();
    }

    public void BFSVisit(){//遍历操作
        for(int i=0;i<numNode;i++){
            if(visit[i]==0){
                visit[i]=1;
                System.out.print(" "+vexTable[i].data);
                queue.enQueue(i);//入队

                EdgeNode eNode;
                while(!queue.isEmpty()){
                    queue.deQueue();//出队
                    eNode=vexTable[i].fnext;
                    while(eNode!=null){
                        if(visit[eNode.index]==0){
                            visit[eNode.index]=1;
                            System.out.print(" "+vexTable[eNode.index].data);
                            queue.enQueue(eNode.index);
                        }
                        eNode=eNode.next;
                    }
                }
            }
        }
    }

还是采用这个图：使用同样的输入数据在主方法中测试：

public static void main(String[] args) {
        Graph graph=new Graph(5,5);
        VexNode[] vexTable=graph.init();
       
        graph.DFS(vexTable);
        graph.BFS();
        
    }

深度优先遍历：
 a c e d b
广度优先遍历：
 a c b d e