图的概念
图(Graph)是一些顶点的集合，顶点之间通过边连接。
边可以有权重(weight),即每条边可以被赋值，正负皆可。
边分为有向边(Directed Edge)、无向边(Undirected Edge)。
顶点的度指连接该顶点的边的数目。
图的表示方法
对于如上的图，有两种主要的表示方法：
- 邻接表(Adjaccency List)
邻接表的优点是节省空间，只存储实际存在的边。
缺点是关注顶点的度时，可能要遍历一个链表。
实现图解如下图：
Java实现代码：
/**
* 有向带权图的邻接表实现
*/
public class LinkGraph {
//顶点
private class Vertex {
char data; //顶点的名称(值)
Node firstEdge; //顶点的第一个邻接点
}
//某个顶点的邻接点的相关信息
private class Node {
int index; //代表此Node在vertex数组中的序号
int weight; //顶点与此邻接点的边的权值
Node nextNode; //点的下一个邻接点
}
//边
static class Edge {
char start; //起点的顶点名称(值)
char end; //重点的顶点名称(值)
int weight; //边的权值
public Edge(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
}
private Vertex[] vertexNameList; //所有顶点名的数组
public LinkGraph(char[] vert, Edge[] edge){
//读入顶点，并初始化
vertexNameList = new Vertex[vert.length];
parent = new int[vert.length];
for (int i = 0; i < vert.length; i++) {
vertexNameList[i] = new Vertex();
vertexNameList[i].data = vert[i]; //顶点名称
vertexNameList[i].firstEdge = null; //还没有邻接点，当然没边
}
//初始化边
for (int i = 0; i < edge.length; i++) {
char start = edge[i].start;
char end = edge[i].end;
//获取顶点对应的序号
int startRank = getPosition(start);
int endRank = getPosition(end);
//1.endRank是startRank的邻接点，把endRank连接在以startRank为头的链表中
Node endRankNode = new Node();
endRankNode.index = endRank;
endRankNode.weight = edge[i].weight;
linkedLast(startRank,endRankNode);
}
}
//尾插法，将顶点连接到链表的尾巴
private void linkedLast(int index, Node node) {
if(vertexNameList[index].firstEdge == null)
vertexNameList[index].firstEdge = node;
else{
Node tmp = vertexNameList[index].firstEdge;
while(tmp.nextNode != null){
tmp = tmp.nextNode;
}
tmp.nextNode = node;
}
}
//获取某个顶点在数组中序号
private int getPosition(char v) {
for (int i = 0; i < vertexNameList.length; i++) {
if(vertexNameList[i].data == v) return i;
}
//不存在这样的顶点则返回-1
return -1;
}
public static void main(String[] args) {
char[] vexs = {'A', 'B', 'C', 'D', 'E'}; //顶点
Edge[] edges = { //边
// 起点 终点 权
new Edge('A', 'B', 5.6),
new Edge('A', 'C', 1.0),
new Edge('A', 'D', 4.2),
new Edge('B', 'C', 2.7),
new Edge('C', 'A', 1.0),
new Edge('C', 'B', 2.7),
new Edge('E', 'B', -3.0)
};
LinkGraph graph = new LinkGraph(vexs,edges);
}
- 邻接矩阵(Adjacency Matrix)
邻接矩阵的优点是可快速添加和删除边，可快速判断两个点之间是否存在边。
缺点是如顶点之间的边比较少，会浪费空间，因为是一个n*n的矩阵。
实现图解如下图：
Java实现代码：
/**
* 邻接矩阵的实现
*/
public class MatrixGraph {
private char[] vertex; //顶点名的集合
private int[][] edges; //邻接矩阵，存储边
private int numOfEdges; //边的个数
public MatrixGraph(int n){
edges = new int[n][n];
vertex = new char[n];
}
//顶点的个数
public int getNumOfVertexs(){
return vertex.length;
}
//边的数目
public int getNumOfEdges(){
return numOfEdges;
}
//获取序号v1顶点到序号v2顶点的权值
public int getWeight(int v1,int v2){
return edges[v1][v2];
}
//插入一条边
public void insertEdge(int v1,int v2,int weight){
edges[v1][v2] = weight;
numOfEdges++;
}
//获取某顶点下标v的第一个邻接点在vertex数组的下标
public int getFirstNeighbor(int v){
for (int i = 0; i < vertex.length; i++) {
if(edges[v][i] != 0)
return i;
}
return -1;
}
//根据顶点下标v1的前一个邻接点下标v2,获取v1的下一个邻接点
public int getNextNeighbor(int v1,int v2){
for (int i = v2+1; i < vertex.length; i++) {
if(edges[v1][i] != 0)
return i;
}
return -1;
}
}
图的遍历算法(基于邻接表)
- 深度优先遍历(DFS: Depth First Search)
深度优先算法的过程，简单来说是从起点开始，找到一条最深的路径，到头之后，返回上一个节点，继续找一条最深的路径(每个节点只能访问一次)。
Java实现代码：
//深度优先搜索(DFS)遍历图,从第一个顶点开始遍历图
public void DFS(){
boolean[] visited = new boolean[vertexNameList.length]; //顶点是否已被遍历，默认为false
int[] path = new int[vertexNameList.length]; //遍历时，顶点出现的顺序，按序记录其下标
int index = 0; //path[]的索引
/**
* MyStack:表示数据结构——栈;先进后出
* 栈的基本操作：
* 1） push(Object o)：元素入栈
* 2） Object pop()：返回栈顶元素，并把该元素从栈中删除。
* 3） Object peek()：返回栈顶元素，但不把该元素删除。
*/
MyStack stack = new MyStack(vertexNameList.length);
for (int i = 0; i < visited.length; i++)
{
//利用栈的先进后出特性，先找到一条最深的路径
stack.push(i);
if(!visited[i])
{
visited[i] = true; //下标i的顶点被遍历
path[index++] = i; //第一个被遍历的顶点，其下标是i
while(!stack.isEmpty())
{
int v = getUnVisitedVertex(stack.peek(),visited);
//如果不存在没有访问的邻接点，就出栈，原路返回
if(v == -1) stack.pop();
else
{
path[index++] = v; //访问邻接点顺序
visited[v] = true; //邻接点v已访问
stack.push(v); //入栈
}
}
}
else
{
stack.pop();
}
}
//打印DFS路径
System.out.println("DFS路径：");
for (int i = 0; i < path.length; i++) {
System.out.print(vertexNameList[path[i]].data + " ");
}
}
//返回某个顶点还没有被访问的邻接点的序号
private int getUnVisitedVertex(Integer v, boolean[] visited) {
Node tmp = vertexNameList[v].firstEdge;
//如果存在邻接点,且邻接点还没有被遍历，返回此邻接点下标;
while(tmp != null){
if(!visited[tmp.index]) return tmp.index;
tmp = tmp.nextNode;
}
//不存在没有被访问的邻接点
return -1;
}
stack进出栈顺序：
- 广度优选遍历(BFS: Breadth First Search)
广度优先算法，是从起点开始，找到这个点所有的邻接点，到头之后，从它的第一个邻接点开始，继续找一条最广的路径(每个节点只能访问一次)。
Java实现代码：
//广度优先搜索，从第一个顶点开始遍历
public void BFS(){
boolean[] visited = new boolean[vertexNameList.length]; //顶点是否已被遍历，默认为false
int[] path = new int[vertexNameList.length]; //遍历时，顶点出现的顺序，按序记录其下标
int index = 0; //path[]的索引
/**
* MyQueue:表示数据结构——队列;先进先出
* 队列的基本操作：
* 1） enqueue(T t)：元素入队
* 2） T dequeue()：元素出队，并把该元素从队列中删除。
* 3） T peek()：返回队列头元素，但不把该元素删除。
*/
MyQueue<Integer> queue = new MyQueue<Integer>(vertexNameList.length);
for (int i = 0; i < visited.length; i++)
{
//利用队列的先进先出特性，先找到一条最广的路径
queue.enqueue(i);
if(!visited[i])
{
visited[i] = true; //下标i的顶点被遍历
path[index++] = i; //第一个被遍历的顶点，其下标是i
while(!queue.isEmpty())
{
int v = getUnVisitedVertex(queue.peek(),visited);
//如果不存在没有访问的邻接点，就出队
if(v == -1) queue.dequeue();
else
{
path[index++] = v;
visited[v] = true;
queue.enqueue(v);
}
}
}
else
{
queue.dequeue();
}
}
//打印BFS路径
System.out.println("BFS路径：");
for (int i = 0; i < path.length; i++) {
System.out.print(vertexNameList[path[i]].data + " ");
}
}
queue进出队列顺序：