图数据结构-图结构的描述

一   图

1，图的描述

       在计算机应用中，我们为了表示相连结点所表示的关系建立模型，并且这些结点之间连接很自然而然会让人产生一连串的的疑问：沿着这些连接能否从一个结点到另一个结点呢，

有多少个结点之间是相互连接着呢？两个结点之间哪一条是最短路径呢等等。

       要描述这些问题，我们使用一种抽象的数据模型-图数据模型，应用此模型我们可以解决很多现实中的问题，比如地图中的两个城市之间线路问题，电路板中各种元器件与导线的连接问题，学生与各学校的配对问题等等

      图的分类大致分为：无向图，有向图，加权图和加权有向图

      图的定义：图是由一组顶点和一组能将两个顶点相连的边组成的

     图的特殊形式：（1） 自环，即一条连接一个顶点和其自身的边 （2） 两条连接两个顶点的平行边 

    不过我们不会讨论这种特殊形式的，我们用两个顶点表示边就可以了。

    图的一些术语

   （1）相邻：两个顶点用一条边相连就是相邻，也叫两个顶点依附于这条边

   （2）度数：所有依附于某个顶点的所有边的数量就是某个顶点的度数

   （3）子图：是由所有边组成的一个子集

   （4）路径：由边顺序连接的一系列顶点，简单路径就是没有重复的定点的路径

  图的几种表示方法

  （1）邻接矩阵，我们可以使用v乘v的布尔矩阵，顶点v和顶点w之间相连的边定义值为true 否则为false

      但是这种条件不能够满足成千上万数百万的顶点需求

    （2）边的数组，我们可以使用一个类Edge类，它含有两个顶点的实例变量，但是这种表示方法要实现邻接边操作时非常不方便

    （3） 邻接表数组，我们可以使用一个顶点为索引的列表数组，其中每个元素都是和该顶点的相连的顶点列表

     下面就是我的一用邻接表示一种方式

2，无向图的代码表示

        

    

import com.lxy.datastructure.bag.Bag;

import edu.princeton.cs.introcs.In;

/**
 * 无向图
 * @author lxy
 *
 */
public class Graph {
 private static final String NEWLINE = System.getProperty("line.separator");
 private  int V;//顶点数目
 private  int E;//边的数目
 private  Bag<Integer>[] adj;//邻接表
 
 public Graph(int V) {
    this.V=V;
    adj=(Bag<Integer>[])new Bag[V];
    for(int v=0;v<V;v++)
    	adj[v]=new Bag<Integer>();
 }
 public Graph(In in) {
    this(in.readInt());
    int E=in.readInt();
    for(int i=0;i<E;i++){
      int v=in.readInt();
      int w=in.readInt();
      addEdge(v,w);
    }
 }
 /**
  * 添加一条边 v-w
  * @param v
  * @param w
  */
 public void addEdge(int v, int w) {
   adj[v].add(w);
   adj[w].add(v);
   E++;
 }
public int getE() {
	return E;
 }
 public int getV() {
	return V;
 }
 /**
  * 和v顶点相邻的所有边
  * @param v
  * @return
  */
 public Iterable<Integer> adj(int v){
	 return adj[v];
 }
 public String toString() {
     StringBuilder s = new StringBuilder();
     s.append(V + " vertices, " + E + " edges " + NEWLINE);
     for (int v = 0; v < V; v++) {
         s.append(v + ": ");
         for (int w : adj[v]) {
             s.append(w + " ");
         }
         s.append(NEWLINE);
     }
     return s.toString();
 }
}

 

 

package com.lxy.datastructure.bag;

import java.util.Arrays;
import java.util.Iterator;

public class Bag<T> implements Iterable<T>{
  private int N;
  private T[] elementData;
  public Bag() {
       elementData=(T[])new Object[16]; 
  }
 public void add(T object) {
    if(elementData.length==N)resize(N*2);
     elementData[N++]=object;
 }

 public void resize(int m){
	 T[] newElementData=(T[]) new Object[m];
     System.arraycopy(elementData,0,newElementData,0,N);
     this.elementData=newElementData;
 }
 
 
@Override
public Iterator<T> iterator() {
	return Arrays.asList(elementData).subList(0,N).iterator();
} 
public boolean isEmpty(){

	return size()==0;
}
public int size(){
	return N;
}

}

 

public class GraphTest {
	String basePath=System.getProperty("user.dir");
    File file1=null;
    File file2=null;
    Graph g1 =null;
    @Before
	public void setup(){
		file1=new File(basePath,"data/graph/mediumG.txt");
		file2=new File(basePath,"data/graph/tinyG.txt");
		In in = new In(file2);
		g1=new Graph(in);
		
		
	}  
    @Test
    public void testPrintGraph(){
    	System.out.println(g1.toString());
    }
    
	
}

13 vertices, 13 edges 
0: 5 1 2 6 
1: 0 
2: 0 
3: 4 5 
4: 3 6 5 
5: 0 4 3 
6: 4 0 
7: 8 
8: 7 
9: 12 10 11 
10: 9 
11: 12 9 
12: 9 11 

 第三方jar，测试用例数据 其中附件中