图是比树更复杂的结构，树是一对多的关系，图是多对多的关系。
一、基本概念
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];//默认所有顶点都未遍历，数组中值都为0System.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];//默认所有顶点都未遍历，数组中值都为0System.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
