图的基本概念

图是由顶点（Vertex）的有穷非空集合和顶点之间边（Edge）的集合组成，记作G =（V,E）。其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

• 无向图

  • 边是没有方向的，即对于边（u,v）和（v,u）都表示为同一条边

• 有向图

  • 边是有方向性的，即对于边（u,v）和（v,u）都表示的是不同的边，一条是从u到v，另一条是从u到v

• 无向网

  • 边是没有方向的，并且每一条边存在着具有某种含义的数值，称之为权（weight）

• 有向网

  • 边是有方向性的，并且每一条边存在着具有某种含义的数值（权）

权：每条边上标上具有某种含义的数值，称为权。可以表示从一个顶点到另一个顶点的距离、时间或者代价等含义。

完全图

• 无向完全图
  任意两个顶点都存在着一条边。边数达到的最大值: $n(n-1)/2$n(n−1)/2
• 有向完全图
  任意两个顶点都存在着两条边。对于u,v两个顶点，存在（u,v）且（v,u）。边数达到的最大值: $n(n-1)$n(n−1)

子图

对于G =（V,E）和 G’ =（V’,E’），V’和E’分别是V和E的子集，即V’∈V 和 E’∈E，则称G’为G的子图。记作G’∈G。特殊的，若G’∈G 且 V’ = V，则称G‘是G的生成子图。

邻接点

• 无向图
  若存在着一条边（u,v），则称u与v互为邻接点（Adjacent）。边（u,v）称为顶点u和v关联的边，顶点u和v成为边(u,v)关联的顶点。
• 有向图
  若存在着一条边<u,v>（有向边），则称顶点u邻接到v，顶点v邻接自u。边<u,v>和顶点u、v关联。

顶点的度

图中与该顶点相关联的边的数目。记作D（v），其中，v指的是任意一个顶点。在有向图中有出度和入度之分，以顶点v为终点的边称之为入度（In Degree），记为ID（v）；以顶点v为起点的边称之为出度（Out Degree），记为OD（v）。

连通图和连通分量

针对于无向图。

• 连通图：图中任意两个顶点都是连通的（可达）。
• 连通分量：无向图中极大连通子图。

例图中的无向图不是连通图，存在着三个连通分支a、b和c。其中，每一个连通分支都是连通的。

强连通图和强连通分量

针对于有向图
强连通图：图中任意两个顶点都是连通的（可达）。
强连通分量：有向图中极大连通子图。

生成树和生成森林

• 生成树：包含图中的全部顶点，但只有构成一棵树的n-1条边（不形成回路）。
• 特：对于非连通图，每个连通分量可以形成一棵生成树，这些树组成了该非连通图的生成森林。

图的存储结构

主要方法

package GraphDemo;

public interface IGraph<T> {
	
	void createGraph();
	//Number of Vertices
	int getVexNum();
	//Number of Edges
	int getArcNum();
	//Returns the vertex value of the corresponding location
	T getVex(int v) throws Exception;
	//Returns the location of the corresponding vertex value
	int locateVex(T vex);
	//Return to the first adjacent point, if not exist,return -1
	int firstAdjVex(int v) throws Exception;
	//Return to the next adjacent point according to w,if w is the last adjacent point then return -1
	int nextAdjVex(int v,int w) throws Exception;
	
}

图的类型

package GraphDemo;

public enum GraphKind {
	UDG,	//UnDirected Graph
	DG,		//Directed Graph
	UDN,	//UnDirected Network
	DN;		//UnDirected Network
}

邻接矩阵

邻接矩阵用来表示顶点之间相邻关系的矩阵。对于图 G =（V,E），假设具有n（n>=1）个顶点，顶点的顺序依次为{v0,v1,……，vn-1}，则邻接矩阵是一个n阶方阵并且行列依次代表各个顶点。

代码如下：

package GraphDemo;

import java.util.Arrays;
import java.util.Scanner;

import QueueDemo.LinkQueue;
@SuppressWarnings("unchecked")
public class MGraph<T> implements IGraph<T> {

	public final static int INFINITY = Integer.MAX_VALUE; // ∞

	private GraphKind kind; // Type labels of Graphs

	private int vexNum, arcNum; // Current number of Vertices and Edges of Graphs

	private T[] vexs; // Vertex Array

	private int[][] arcs; // Adjacency Matrix

	public MGraph() {
		this(null, 0, 0, null, null);
	}

	public MGraph(GraphKind kind, int vexNum, int arcNum, T[] vexs, int[][] arcs) {
		this.kind = kind;
		this.vexNum = vexNum;
		this.arcNum = arcNum;
		this.vexs = vexs;
		this.arcs = arcs;
	}

	/* * @see GraohDemo.IGraph#createGraph() Create the Graph */
	
	public void createGraph() {
		Scanner sc = new Scanner(System.in);
		System.out.println("Please input type of Graph( UDG--DG--UDN--DN )");
		GraphKind kind = GraphKind.valueOf(sc.next());
		
		System.out.println("Please enter the Vertex numbers and Edge numbers of the Graph separetely !");
		vexNum = sc.nextInt();
		arcNum = sc.nextInt();
		vexs = (T[]) new Object[vexNum];
		
		System.out.println("Please enter each Vertex of the Graph separetely");
		//Constructing vertex vectors
		for (int v = 0; v < vexNum; v++)
			vexs[v] = (T) sc.next();
		arcs = new int[vexNum][vexNum];
		
		switch (kind) {
		case UDG:
			createUDG();
			sc.close();
			return;
		case DG:
			createDG();
			sc.close();
			return;
		case UDN:
			createUDN();
			sc.close();
			return;
		case DN:
			createDN();
			sc.close();
			return;
		}
	}

	private void createUDG() {
		Scanner sc = new Scanner(System.in);

		System.out.println("Please enter two vertices on each side to create edge");
		
		//Assigning values to adjacent matrices
		for(int k=0;k<arcNum;k++) {
			int v = locateVex((T)sc.next());
			int u = locateVex((T)sc.next());
			arcs[v][u] = arcs[u][v] = 1;
		}
		sc.close();
	}

	private void createDG() {
		Scanner sc = new Scanner(System.in);
		
		System.out.println("Please enter two vertices on each side to create edge");
		
		//Assigning values to adjacent matrices
		for(int k=0;k<arcNum;k++) {
			int v = locateVex((T)sc.next());
			int u = locateVex((T)sc.next());
			arcs[v][u] = 1;
		}
		sc.close();
	}

	private void createUDN() {
		Scanner sc = new Scanner(System.in);
		
		//Initializing each value of Array
		for(int v=0;v<vexNum;v++)
			for(int u=0;u<vexNum;u++)
				arcs[v][u] = INFINITY;
		System.out.println("Please enter two vertices on each side and their weights to create edge");
		
		//Assigning values to adjacent matrices
		for(int k=0;k<arcNum;k++) {
			int v = locateVex((T)sc.next());
			int u = locateVex((T)sc.next());
			arcs[v][u] = arcs[u][v] = sc.nextInt();
		}
		sc.close();
	}

	private void createDN() {
		Scanner sc = new Scanner(System.in);
		
		//Initializing each value of Array
		for(int v=0;v<vexNum;v++)
			for(int u=0;u<vexNum;u++)
				arcs[v][u] = INFINITY;
		System.out.println("Please enter two vertices on each side and their weights to create edge");
		
		//Assigning values to adjacent matrices
		for(int k=0;k<arcNum;k++) {
			int v = locateVex((T)sc.next());
			int u = locateVex((T)sc.next());
			arcs[v][u] = sc.nextInt();
		}
		sc.close();
	}

	// Get the numbers of Vertices
	public int getVexNum() {
		return vexNum;
	}

	// Get the numbers of Edges
	public int getArcNum() {
		return arcNum;
	}

	// Get the value of Vertex
	public T getVex(int v) throws Exception {
		if(v<0 || v>=vexNum)
			throw new Exception("第"+v+"个顶点不存在");
		return vexs[v];
	}

	// Get the vertex's location by given its value,not exists then return -1
	public int locateVex(T vex) {
		for(int v=0;v<vexNum;v++)
			if(vexs[v].equals(vex))
				return v;
		return -1;
	}

	// Get the first adjacent point,if not exists,then return -1
	public int firstAdjVex(int v) throws Exception {
		if(v<0 || v>=vexNum)
			throw new Exception("第"+v+"个顶点不存在");
		for(int j=0;j<vexNum;j++)
			if(arcs[v][j]!=0 && arcs[v][j]<INFINITY)
				return j;
		return -1;
	}

	// Get the first adjacent point,if not exists,then return -1
		public int firstAdjVex(T vex) throws Exception {
			int v = locateVex(vex);
			if(v<0 || v>=vexNum)
				throw new Exception("该顶点不存在");
			for(int j=0;j<vexNum;j++)
				if(arcs[v][j]!=0 && arcs[v][j]<INFINITY)
					return j;
			return -1;
		}
	
	
	// Get the next adjacent point,if not exists,return -1
	public int nextAdjVex(int v, int w) throws Exception {
		if(v<0 || v>=vexNum)
			throw new Exception("第"+v+"个顶点不存在");
		for(int j=w+1;j<vexNum;j++)
			if(arcs[v][j]!=0 && arcs[v][j]<INFINITY)
				return j;
		return-1;
	}
	
	public GraphKind getKind() {
		return kind;
	}

	public int[][] getArcs(){
		return arcs;
	}
	
	public Object[] getVexs() {
		return vexs;
	}
	
	//Test
	public static void main(String[] args) throws Exception {
		MGraph<String> mGraph = new MGraph<>();
		mGraph.createGraph();
		System.out.println("----Vertex Array----");
		System.out.println(mGraph.getVexs().getClass().toString());
		System.out.println(Arrays.toString(mGraph.getVexs()));
		int [][] arr = mGraph.getArcs();
		
		System.out.println("----Adjacent Matrix---");
		for(int i=0;i<arr.length;i++) {
			System.out.print(mGraph.getVexs()[i]+":");
			System.out.println(Arrays.toString(arr[i]));
		}
		
		//BFSTraverse(mGraph);
	}
	
	
	
}

邻接表

邻接表是图的一种链式存储方式，由一个顺序存储的顶点表和n个链式存储的边表组成。

顶点结点和边结点的结构如下：

顶点结点：

package GraphDemo;
//Vertex Node class of Adjacency Table of Graphs
public class VNode<T> {
	public T data;	
	public ArcNode firstArc;	//Point to the first edge
	
	public VNode() {
		this(null,null);
	}
	
	public VNode(T data) {
		this(data, null);
	}
	
	public VNode(T data,ArcNode firstArc) {
		this.data = data;
		this.firstArc = firstArc;
	}
}

边结点：

package GraphDemo;

public class ArcNode {
	public int adjVex;			//Point to the location of the vertex
	public int value;			//the edge's weight
	public ArcNode nextArc;		//Point to the next ArcNode(Edge)
	public ArcNode() {
		this(-1,0,null);
	}
	public ArcNode(int adjVex) {
		this(adjVex,0,null);
	}
	public ArcNode(int adjVex, int value) {
		this(adjVex, value, null);
	}
	
	public ArcNode(int adjVex, int value, ArcNode nextArc) {
		this.adjVex = adjVex;
		this.value = value;
		this.nextArc = nextArc;
	}
}

邻接矩阵：

package GraphDemo;

import java.util.ArrayList;
import java.util.Scanner;

import GraphDemo.GraphKind;

/** * @author OMG丶 * */

@SuppressWarnings("unchecked")
public class Adjacency<T> implements IGraph<T> {

	private GraphKind kind; // Type labels of Graphs

	private int vexNum, arcNum; // Current number of Vertices and Edges of Graphs
	
	private ArrayList<VNode<T>> vexs; // Vertex Array


	public Adjacency() {
		this(null, 0, 0, null);
	}

	public Adjacency(GraphKind kind, int vexNum, int arcNum, ArrayList<VNode<T>> vexs) {
		this.kind = kind;
		this.vexNum = vexNum;
		this.arcNum = arcNum;
		this.vexs = vexs;
	}

	/* * @see GraohDemo.IGraph#createGraph() Create the Graph */
	public void createGraph() {
		Scanner sc = new Scanner(System.in);
		System.out.println("Please input type of Graph( UDG--DG--UDN--DN )");
		GraphKind kind = GraphKind.valueOf(sc.next());
		
		System.out.println("Please enter the Vertex numbers and Edge numbers of the Graph separetely !");
		vexNum = sc.nextInt();
		arcNum = sc.nextInt();
		
		vexs = new ArrayList<VNode<T>>(vexNum);
		
		System.out.println("Please enter each Vertex of the Graph separetely");
		//Constructing vertex vectors
		for (int v = 0; v < vexNum; v++)
			vexs.add(new VNode<T>((T)sc.next()) );
		
		switch (kind) {
		case UDG:
			createUDG();
			sc.close();
			return;
		case DG:
			createDG();
			sc.close();
			return;
		case UDN:
			createUDN();
			sc.close();
			return;
		case DN:
			createDN();
			sc.close();
			return;
		}
	}

	private void createUDG() {
		Scanner sc = new Scanner(System.in);

		System.out.println("Please enter two vertices on each side to create edge");

		// Assigning values to adjacent matrices
		for (int k = 0; k < arcNum; k++) {
			int v = locateVex((T)sc.next());
			int u = locateVex((T)sc.next());
			addArc(v,u,0);
			addArc(u, v, 0);
		}
		sc.close();
	}

	private void createDG() {
		Scanner sc = new Scanner(System.in);

		System.out.println("Please enter two vertices on each side to create edge");

		// Assigning values to adjacent matrices
		for (int k = 0; k < arcNum; k++) {
			int v = locateVex((T)sc.next());
			int u = locateVex((T)sc.next());
			addArc(v,u,0);
		}
		sc.close();

	}

	private void createUDN() {
		Scanner sc = new Scanner(System.in);
		
		System.out.println("Please enter two vertices on each side and their weights to create edge");

		// Assigning values to adjacent matrices
		for (int k = 0; k < arcNum; k++) {
			int v = locateVex((T)sc.next());
			int u = locateVex((T)sc.next());
			int value = sc.nextInt();
			addArc(v,u,value);
			addArc(u, v, value);
		}
		sc.close();

	}

	private void createDN() {
		Scanner sc = new Scanner(System.in);
		
		System.out.println("Please enter two vertices on each side and their weights to create edge");

		// Assigning values to adjacent matrices
		for (int k = 0; k < arcNum; k++) {
			int v = locateVex((T)sc.next());
			int u = locateVex((T)sc.next());
			int value = sc.nextInt();
			addArc(v,u,value);
		}
		sc.close();

	}

	private void addArc(int v, int u, int value) {
		//Head insertion
		if(v==-1 || u==-1)
			try {
				throw new Exception("添加有误");
			} catch (Exception e) {
				e.printStackTrace();
			}
		ArcNode arc = new ArcNode(u,value);
		arc.nextArc = vexs.get(v).firstArc;
		vexs.get(v).firstArc = arc;
	}
	
	// Get the numbers of Vertices
	public int getVexNum() {
		return vexNum;
	}

	// Get the numbers of Edges
	public int getArcNum() {
		return arcNum;
	}

	// Get the value of Vertex
	public T getVex(int v) throws Exception {
		if(v<0 || v>=vexNum)
			throw new Exception("第"+v+"个顶点不存在");
		return vexs.get(v).data;
	}

	// Get the vertex's location by given its value,not exists then return -1
	public int locateVex(T vex) {
		for(int v=0;v<vexNum;v++)
			if(vexs.get(v).data.equals(vex))
				return v;
		return -1;
	}

	// Get the first adjacent point,if not exists,then return -1
	public int firstAdjVex(int v) throws Exception {
		if(v<0 || v>=vexNum)
			throw new Exception("第"+v+"个顶点不存在");
		VNode<T> vex = vexs.get(v);
		if(vex.firstArc!=null)
			return vex.firstArc.adjVex;
		else
			return -1;
	}

	// Get the next adjacent point according to w,if w is the last,then return -1
	public int nextAdjVex(int v, int w) throws Exception {
		if(v<0 || v>=vexNum)
			throw new Exception("第"+v+"个顶点不存在");
		VNode<T> vex = vexs.get(v);ArcNode arcvw = null;
		for(ArcNode arc = vex.firstArc;arc!=null;arc =arc.nextArc)
			if(arc.adjVex == w) {
				arcvw = arc;
				break;
			}
		if(arcvw!=null && arcvw.nextArc != null)
			return arcvw.nextArc.adjVex;
		else 
			return -1;
		
	}
	
	
	public GraphKind getKind() {
		return kind;
	}

	public ArrayList<VNode<T>> getVexs() {
		return vexs;
	}
	
	//Test
	public static void main(String[] args) throws Exception {
		
		Adjacency<Integer> adj = new Adjacency<>();
		adj.createGraph();
		ArrayList<VNode<Integer>> arr = adj.getVexs();
		System.out.println("----Adjacency Graph----");
		for(int i = 0;i<arr.size();i++) {
			System.out.print(arr.get(i).data+" ");
			
			for(ArcNode j = arr.get(i).firstArc;j!=null;j = j.nextArc)
				System.out.print("->"+arr.get(j.adjVex).data+"("+j.value+")");
			
			System.out.println();
		}
		
	}

}

测试结果：（DN）