图是比树更复杂的结构,树是一对多的关系,图是多对多的关系。
一、基本概念
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