什么是简单图

在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点与终点相同(也就是它们的的方向相同)，称这些边为平行边。含平行边的图称为多重图，既不含平行边也不含环的图称为简单图。

稠密图和稀疏图的定义

图可以用哪些数据结构进行存储表示

• 数组（邻接矩阵）存储表示（有向或无向）
• 邻接表存储表示
• 前向星存储表示
• 有向图的十字链表存储表示
• 无向图的邻接多重表存储表示

稠密图适合用邻接矩阵，稀疏图适合用邻接表表示

讯享网

示例代码

用邻接矩阵表示稠密图

package GraphBasics; import java.util.Vector; / * @ Description: 用邻接矩阵表示稠密图 * @ Date: Created in 11:35 2018/8/1 * @ Author: Anthony_Duan */ public class DenseGraph implements Graph { 
    //节点数 private int n; //边数 private int m; //是否为有向图 private boolean directed; //图的具体数据 private boolean[][] g; public DenseGraph(int n, boolean directed) { assert n >= 0; this.n = n; //初始化没有任何边 this.m = 0; this.directed = directed; //g初始化为n*n的布尔矩阵，每一个g[i][j]均为false，表示没有任何边 //false为Boolean型的变量的默认值 g = new boolean[n][n]; } //返回节点个数 @Override public int V(){ return n; } //返回边的个数 @Override public int E(){ return m; } //向图中添加一个边 @Override public void addEdge(int v, int w) { assert v >= 0 && v < n; assert w >= 0 && w < n; //首先判断边是否存在，如果存在什么都不做 if (hasEdge(v, w)) { return; } g[v][w] = true; //如果不是有向图 if (!directed) { g[w][v] = true; } m++; } // 验证图中是否有从v到w的边 @Override public boolean hasEdge(int v, int w) { assert v >= 0 && v < n; assert w >= 0 && w < n; return g[v][w]; } @Override public void show() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.println(g[i][j] + "\t"); } System.out.println(); } } / * 返回图中一个顶点的所有邻边 * 由于java使用引用机制，返回一个Vector不会带来额外开销 * @param v * @return */ @Override public Iterable<Integer> adj(int v) { assert v >= 0 && v < n; Vector<Integer> adjV = new Vector<Integer>(); for (int i = 0; i < n; i++) { if (g[v][i]) { adjV.add(i); } } return adjV; } }

用邻接表表示稀疏图

讯享网package GraphBasics; import java.util.Vector; / * @ Description: 用邻接表表示稀疏图 * @ Date: Created in 11:35 2018/8/1 * @ Author: Anthony_Duan */ public class SparseGraph implements Graph { 
    //节点数 private int n; //边数 private int m; //是否为有向图 private boolean directed; //图的具体数据 private Vector<Integer>[] g; public SparseGraph(int n, boolean directed) { assert n >= 0; this.n = n; //初始化没有任何边 this.m = m; this.directed = directed; //g初始化为n个空vector 表示每一个g[i]都表示为空，即没有任何边 g = (Vector<Integer>[]) new Vector[n]; for (int i = 0; i < n; i++) { g[i] = new Vector<Integer>(); } } //返回节点个数 @Override public int V(){ return n; } //返回边的个数 @Override public int E(){ return m; } / * 向图中添加一个边 * 这里并没有处理平行边的情况 * 因为邻接表如果要考虑没有平行边，每次添加边都需要遍历一次g[v] * 效率太低，所以一般是先添加，最后一次性处理， * 这里就暂时允许有平行边 * @param v * @param w */ @Override public void addEdge(int v, int w) { assert v >= 0 && v < n; assert w >= 0 && w < n; g[v].add(w); if (v != w && !directed) { g[w].add(v); } m++; } @Override public void show() { for( int i = 0 ; i < n ; i ++ ){ System.out.print("vertex " + i + ":\t"); for( int j = 0 ; j < g[i].size() ; j ++ ) { System.out.print(g[i].elementAt(j) + "\t"); } System.out.println(); } } @Override public boolean hasEdge(int v, int w) { assert v >= 0 && v < n; assert w >= 0 && w < n; for (int i = 0; i < g[v].size(); i++) { if (g[v].elementAt(i) == w) { return true; } } return false; } / * 返回图中一个顶点的所有邻边 * 由于java使用引用机制所以返回一个Vector不会带来额外开销 * @param v * @return */ public Iterable<Integer> adj(int v) { assert v >= 0 && v < n; return g[v]; } }