概念
定义
图是一种较线性表和树更为复杂的数据结构
相较于线性表的一对一（每个结点只有一个前驱后驱）和树的一对多（层级结构，上层结点可以与多个下层结点相关），图形结构的元素关系是多对多（即结点之间的关系可以是任意的）
图可分为有向图和无向图
术语
连通图：对于无向图，如果任意两个结点之间都是通的，则称之为连通图
连通分量：对于无向非连通图，极大连通子图称为其连通分量
强连通图：对于有向图，任意两个结点有路径
强连通分量：对于有向图非连通图，极大连通子图称为其强连通分量
连通图的生成树：该图的极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树
例如上图a中无向图G3，图b便为其三个连通分量
上图为连通分量图的生成树
图的存储结构
图的常用的存储结构有：邻接矩阵、邻接链表、十字链表、邻接多重表和边表，其中邻接矩阵和邻接链表是较常用的表示方法。
邻接矩阵
即用一维数组放置其顶点，二维数组放置顶点之间的关系
例如对于无向图，A[i][j]=0表示i结点和j结点之间不连通，A[i][j]=1表示连通；对于有向图，A[i][j]表示i结点和j结点之间的权值。
该二维数组又称为邻接矩阵
邻接链表
即用一个数组存储所有顶点，而每个顶点有一个域指向一个单链表，该单链表存储该顶点所有邻接顶点及其相关信息。
如上图，头结点（顶点）中data存储该顶点相关信息，firstarc存储单链表第一个结点的位置；
表结点（链表结点）中adjvex存储该领接顶点位置，nextarc存储链表下一个结点位置，info存储边相关信息（例如有向图中的权值）
下图为邻接链表的图解
20130708131719421.png
实现代码
给出手动实现的邻接矩阵代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 弧
*/
class Arc{
//弧连接的两个顶点
Object v1,v2;
//图：-1 无连接 >=0有连接
int Type;
//弧的信息
String info;
public Arc() {}
public Arc(Object v1, Object v2, int type, String info) {
super();
this.v1 = v1;
this.v2 = v2;
Type = type;
this.info = info;
}
@Override
public String toString() {
return v1+" "+v2+" "+Type+" "+info;
}
}
/**
* 领接矩阵图
*/
public class MatrixGraph {
/**默认顶点最大个数*/
final static int defaultSize=10;
/**顶点集合*/
List<Object> vertexs;
/**边的关系矩阵*/
Arc[][] arcs;
/**最大顶点个数*/
int maxLen;
/**弧的个数*/
int arcNum;
/**
* 默认构造函数
*/
public MatrixGraph() {
this.maxLen = defaultSize;
this.vertexs = new ArrayList<Object>(maxLen);
this.arcs = new Arc[maxLen][maxLen];
this.arcNum = 0;
}
/**
* 带参构造函数
* @param vers 顶点数组
*/
public MatrixGraph(Object[] vers) {
this.maxLen=vers.length;
this.vertexs=new ArrayList<Object>(Arrays.asList(vers));
this.arcs = new Arc[maxLen][maxLen];
this.arcNum = 0;
}
/**
* 添加顶点
* @param v
*/
public void addVertex(Object v) {
vertexs.add(v);
if(vertexs.size()>maxLen)
extendSize();
}
/**
* 扩展最大顶点个数和领接矩阵
*/
public void extendSize() {
maxLen*=2;
arcs=Arrays.copyOf(arcs, maxLen);
}
/**
* 添加一条弧
* @param a
* @param b
*/
public void addArc(Object a,Object b) {
addArc(a, b, 0);
}
/**
* 添加一条带权弧
* @param a
* @param b
* @param weight
*/
public void addArc(Object a,Object b,int weight) {
int i=vertexs.indexOf(a);
int j=vertexs.indexOf(b);
if(i==-1||j==-1){
throw new ArrayIndexOutOfBoundsException("该顶点不存在");
}
arcs[i][j]=new Arc(a, b, weight, "");
arcNum++;
}
/**
* 删除a到b的弧
* @param a
* @param b
*/
public void removeArc(Object a,Object b) {
int i=vertexs.indexOf(a);
int j=vertexs.indexOf(b);
if(i==-1||j==-1){
throw new ArrayIndexOutOfBoundsException("该顶点不存在");
}
if(arcs[i][j]!=null){
arcs[i][j]=null;
arcNum--;
}
else {
System.out.println("该弧已经不存在");
}
}
/**
* 删除一个顶点
* @param a
*/
public void removeVertexs(Object a) {
int i=vertexs.indexOf(a);
if(i==-1)
throw new ArrayIndexOutOfBoundsException("该顶点不存在");
vertexs.remove(i);
//重新生成邻接矩阵
int length=arcs.length;
for (int j = 0; j < length-1; j++) {
for (int z = 0; z < length-1; z++) {
if(z>=i)
arcs[j][z]=arcs[j][z+1];
}
arcs[j][length-1]=null;
if(j>=i)
arcs[j]=arcs[j+1];
}
arcs[length-1]=new Arc[length];
}
/**
* 清空图
*/
public void clear() {
vertexs=null;
arcs=null;
arcNum=0;
maxLen=defaultSize;
}
/**
* 打印图的信息
*/
public void printGraph() {
for (int i = 0; i < arcs.length; i++) {
for (int j = 0; j < arcs[i].length; j++) {
if(arcs[i][j]!=null)
System.out.println(arcs[i][j]);
}
}
}
public static void main(String[] args) {
Object obj[] = { 'A', 'B', 'C', 'D', 'E', 'F' };
MatrixGraph graph = new MatrixGraph(obj);
graph.addArc('A','C',5);
graph.addArc('B','A',2);
graph.addArc('C','B',15);
graph.addArc('E','D',4);
graph.addArc('F','E',18);
graph.addArc('A', 'F', 60);
graph.addArc('C', 'F', 70);
graph.printGraph();
System.out.println("--------------");
graph.removeVertexs('A');
graph.printGraph();
System.out.println("--------------");
graph.removeArc('C', 'B');
graph.printGraph();
}
}/**Output:
A C 5
A F 60
B A 2
C B 15
C F 70
E D 4
F E 18
--------------
C B 15
C F 70
E D 4
F E 18
--------------
C F 70
E D 4
F E 18 */
图的遍历
图的遍历有两种：DFS（Deep First Search）和BFS（Breadth First Search）
这两个算法算是我在ACM呆的时候做题最多的算法了。
DFS（深度优先算法）
即每次遍历时偏向纵深方向搜索，类似树的先序遍历
递归实现：
- 访问顶点v；visited[v]=1；//算法执行前visited[n]=0
- w=顶点v的第一个邻接点；
- while（w存在）
if（w未被访问）
从顶点w出发递归执行该算法；
w=顶点v的下一个邻接点；
非递归实现：
- 栈S初始化；visited[n]=0；
- 访问顶点v；visited[v]=1；顶点v入栈S
- while(栈S非空)
x=栈S的顶元素(不出栈)；
if(存在并找到未被访问的x的邻接点w)
访问w；visited[w]=1；
w进栈;
else
x出栈；
BFS（广度优先算法）
即每次时遍历分层搜索，先搜索完每个顶点的领接结点，再对领接结点重复这一步。
非递归实现
- 初始化队列Q；visited[n]=0；
- 访问顶点v；visited[v]=1；顶点v入队列Q；
- while（队列Q非空）
v=队列Q的对头元素出队；
w=顶点v的第一个邻接点；
while（w存在）
如果w未访问，则访问顶点w；
visited[w]=1；
顶点w入队列Q；
w=顶点v的下一个邻接点。
下面是具体的代码
/**
* 深度优先遍历
* @param o
* @return
*/
public String dfs(Object o) {
StringBuilder result=new StringBuilder();
Stack<Object> stack=new Stack<Object>();
//访问标记数组
Boolean[] visit=new Boolean[vertexs.size()];
//初始化所有顶点为未访问
for (int i = 0; i < visit.length; i++) {
visit[i]=false;
}
//放入起始结点入栈
stack.push(o);
visit[vertexs.indexOf(o)]=true;
result.append(o);
//利用栈进行深度优先遍历
while (!stack.isEmpty()) {
//访问栈的顶点
Object out=stack.peek();
Object next=getNext(out, visit);
if(next!=null){
stack.push(next);
visit[vertexs.indexOf(next)]=true;
result.append("->"+next);
}
else{
stack.pop();
}
}
return result.toString();
}
/**
* 广度优先遍历
* @param o
* @return
*/
public String bfs(Object o) {
StringBuilder result = new StringBuilder();
Queue queue = new LinkedList<Object>();
// 访问标记数组
Boolean[] visit = new Boolean[vertexs.size()];
// 初始化所有顶点为未访问
for (int i = 0; i < visit.length; i++) {
visit[i] = false;
}
//放入起始结点入队列
queue.add(o);
visit[vertexs.indexOf(o)]=true;
result.append(o);
//利用队列进行广度优先遍历
while (!queue.isEmpty()) {
//访问堆顶点
Object out=queue.peek();
Object next=getNext(out, visit);
if(next!=null){
queue.add(next);
visit[vertexs.indexOf(next)]=true;
result.append("->"+next);
}else{
queue.poll();
}
}
return result.toString();
}
/**
* 获取o结点的下一个未被访问的领接结点
* @param o
* @param visit
* @return
*/
private Object getNext(Object o,Boolean[] visit){
int index=vertexs.indexOf(o);
for (int j = 0; j < arcs.length; j++) {
if(arcs[index][j]!=null&&visit[j]==false)
return vertexs.get(j);
}
return null;
}
