什么是图|ω・`)

图G是一个有序二元组(V,E),其中V称为顶集(Vertices
Set),E称为边集(Edges set),E与V不相交。它们亦可写成V(G)和E(G)。

E的元素都是二元组,用(x,y)表示,其中x,y∈V。 (摘自百度百科)

 

简单来说,图就是由点和边组成的东西。也可以理解为若干个元素之间关系的抽象表示,边即代表着对应顶点之间的相互关系。

有向图 在有向图中,结点对<x
,y>是有序的,结点对<x,y>称为从结点x到结点y的一条有向边,因此,<x,y>与<y,x>是两条不同的边。有向图中的结点对<x,y>用一对尖括号括起来,x是有向边的始点,y是有向边的终点,有向图中的边也称作弧。

图的分类|ω・`)

无向图
在无向图中,结点对(x,y)是无序的,结点对(x,y)称为与结点x和结点y相关联的一条边。(x,y)等价于<x,y>和<y,x>。

1.有向图与无向图:

如果我们给图中的每个边规定了方向,即边<
x,y
>中顶点x和y的顺序不能随便颠倒,那这个图就叫做有向图,反之即为无向图。

完全图
在有n个结点的无向图中,若有n(n-1)/2条边,即任意两个结点之间有且只有一条边,则称此图为无向完全图。在有n个结点的有向图中,若有n(n-1)条边,即任意两个结点之间有且只有方向相反的两条边,则称此图为有向完全图。

2.单图:

一个图如果任意两顶点之间只有一条边(在有向图中为两顶点之间每个方向只有一条边);边集中不含环,则称为单图。

邻接结点
在无向图G中,若(u,v)是E(G)中的一条边,则称u和v互为邻接结点,并称边(u,v)依附于结点u和v。在有向图G中,若<u,v>是E(G)中的一条边,则称结点u邻接到结点v,结点v邻接自结点u,并称边<u,v>和结点u和结点v相关联。

3.连通图、非连通图与强连通图:

在无向图中,如果从顶点vi到顶点vj有路径,则称vi和vj连通。如果图中任意两个顶点之间都连通,则称该图为连通图,否则,将其中的极大连通子图称为连通分量。在有向图中,如果对于每一对顶点vi和vj,从vi到vj和从vj到vi都有路径,则称该图为强连通图;否则,将其中的极大连通子图称为强连通分量。

*没有环的有向图叫做DAG。

结点的度 结点v的度是与它相关联的边的条数,记作TD(v)。
路径
在图G=(V,E)中,若从结点vi出发有一组边使可到达结点vj,则称结点vi到结点vj的结点序列为从结点vi到结点vj的路径。

4.简单图与树:

如果对于任意的顶点x和y,最多只有一条边把他们相连,也就是说边集中不含两个或以上的(x,y),那么图G称为简单图。简单图可以用矩阵表示。

没有环的无向连通图叫做无向树。

如果把一个有向图变为无向图后成为无向树,那么称这个有向图为一棵有向树。

特别的:一个点也叫作一棵树,如果有很多树就叫做森林。

如果有向树中存在一个顶点x使得从x能够到达其余所有顶点,那么有向树G=(V,E)称为根在x的树形图。


有些图的边附带有数据信息,这些附带的数据信息称为权。第i条边的权用符号wi表示。
路径长度
对于不带权的图,一条路径的路径长度是指该路径上的边的条数;对于带权的图,一条路径的路径长度是指该路径上各个边权值的总和。

有关图的定义|ω・`)

  • 阶(Order):
    图G的顶集V的大小(即顶点的数量)。
  • 度(Degree):一个顶点的度是指与该顶点相连的边的条数,顶点v的度记作d(v)。

    *入度和出度:有向图中,一个点的入度为以该点为终点的路径数量,出度为以该点为起点的路径数量。

  • 子图(Sub-Graph):当图G’=(V’,E’)
    其中V‘含于V,E’含于E,则G’称作图G=(V,E)的子图。每个图都是本身的子图。

  • 生成子图(Spanning
    Sub-Graph):如果图g的点集与G的点集相同,g的边集含于G的边集,那么称g为G的生成子图。特别的,如果g为无向树,那么称g为图G的生成树。
  • 导出子图(Induced
    Subgraph):顶集V1为V的非空子集,以两端点均在V1中的(E中的)全体边为边集的G的子图,称为V1导出的导出子图;边集E1为E的非空子集,以E1中边关联的顶点的全体为顶点集的G的子图,称为E1导出的导出子图。

    *可知,图G的任何子图,都可以看作是图G的某个导出子图的生成子图。

  • 路径(Path):从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,…ek,vk,(A–1–>B–2–>C…),其中ei的顶点为vi及vi

    1,k称作路径长度。如果它的起止顶点相同,该路径是“闭”的,反之,则称为“开”的。如果这条路径除了u和w以外其余顶点都各不相等,那么称这条路径为简单路径。

    *路径长度:
    一条路径所经过的边的数量。

    *长度:路径中所有边的权值的和(可能为负)。

  • 行迹(Trace):如果路径P(u,v)中的边各不相同,则该路径称为u到v的一条行迹。

  • 轨道(Track):如果路径P(u,v)中的顶点各不相同,则该路径称为u到v的一条轨道。
\*闭的行迹称作回路(Circuit),闭的轨称作圈(Cycle)
  • 环:如果一条路径的起点和终点相等,那么这条路径称为环(回路)。

  • 自环(Loop):若一条边的两个顶点为同一顶点,则此边称作自环。

  • 桥(Bridge):若去掉一条边,便会使得整个图不连通,该边称为桥。
  • 割点:若去掉一个点,便会使得整个图不连通,则该顶点成为割点。

(参考百度百科)

最小生成树 一个有 n
个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n
个结点,并且有保持图联通的最少的边。(n-1)条边。

图的储存|ω・`)

1.列表:开三个数组分别记录每条边的起点,终点和权值。

2.邻接矩阵:f[i][j]=d表示一条从i到j的权值为d的边。

3.邻接表:用链表和结构体存每一条边,并记下每个点连出的边。
4.有向图的十字链表存储表示。
5.无向图的邻接多重表存储表示。

*一个不带权图中若两点不相邻,邻接矩阵相应位置为0,对带权图(网),相应位置为∞。一个图的邻接矩阵表示是唯一的,但其邻接表表示不唯一。

*在有向图中,通常将边称作弧,含箭头的一端称为弧头,另一端称为弧尾,记作<
vi,vj
>,它表示从顶点vi到顶点vj有一条边。若有向图中有n个顶点,则最多有n(n-1)条弧,我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度,以顶点v为弧头的弧的数目称作顶点v的入度。

*在无向图中,边记作(vi,vj),它蕴涵着存在<
vi,vj >和< vj,vi
>两条弧。若无向图中有n个顶点,则最多有n(n-1)/2条弧,我们又将具有n(n-1)/2条弧的无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。

(摘自百度百科)

图的邻接矩阵存储结构
假设图G=(V,E)有n个结点,即V={v0,v1,…,vn-1},E可用如下形式的矩阵A描述,对于A中的每一个元素aij,满足:aij=1表示i和j节点有边相连,aij=0表示i和j没有边相连。
由于矩阵A中的元素aij表示了结点vi和结点vj之间边的关系,或者说,A中的元素aij表示了结点vi和结点vj(0≤j≤n-1)的邻接关系,所以矩阵A称作邻接矩阵。
aij=多少的数表示i和j的路径权值。

图的遍历|ω・`)

深度优先搜索(dfs)和广度优先搜索(bfs)。

 

树中的边|ω・`)

  • 树边指的是从父节点找到子结点所用的边
  • 前向边指的是从祖先结点指向其子孙结点的非树边
  • 后向边指的是从子孙结点往回指向祖先结点的边
  • 横叉边指的是没有祖孙关系的两个结点之间的边,起点的遍历顺序在终点之后。

PS:就先整理这些吧,以后再补充2333ヾノ≧∀≦)o

 

 

 

import java.util.ArrayList;

//邻接矩阵类
public class MyAdjGraphic {

    static final int maxWeight=-1; //如果两个结点之间没有边,权值为-1;
    ArrayList vertices = new ArrayList();//存放结点的集合
    int[][] edges; //邻接矩阵的二维数组
    int numOfEdges; //边的数量

    public MyAdjGraphic(int n)
    {
        edges = new int[n][n];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==j) //对角线上的元素为0
                {
                   edges[i][j]=0;    
                }
                else
                {
                   edges[i][j]=maxWeight;
                }
            }
        }
        numOfEdges = 0;
    }

    //返回边的数量
    public int getNumOfEdges()
    {
        return this.numOfEdges;
    }

    //返回结点的数量
    public int getNumOfVertice()
    {
        return this.vertices.size();
    }

    //返回结点的值
    public Object getValueOfVertice(int index)
    {
        return this.vertices.get(index);    
    }

    //获得某条边的权值
    public int getWeightOfEdges(int v1,int v2) throws Exception
    {
       if((v1 < 0 || v1 >= vertices.size())||(v2 < 0||v2 >= vertices.size()))
       {
           throw new Exception("v1或者v2参数越界错误!");
       }
       return this.edges[v1][v2];

    }

    //插入结点
    public void insertVertice(Object obj)
    {
        this.vertices.add(obj);
    }

    //插入带权值的边
    public void insertEdges(int v1,int v2,int weight) throws Exception
    {
        if((v1 < 0 || v1 >= vertices.size())||(v2 < 0||v2 >= vertices.size()))
        {
          throw new Exception("v1或者v2参数越界错误!");
        }

        this.edges[v1][v2]=weight;
        this.numOfEdges++;
    }

    //删除某条边
    public void deleteEdges(int v1,int v2) throws Exception
    {
        if((v1 < 0 || v1 >= vertices.size())||(v2 < 0||v2 >= vertices.size()))
        {
          throw new Exception("v1或者v2参数越界错误!");
        }
        if( v1==v2 || this.edges[v1][v2]==maxWeight)//自己到自己的边或者边不存在则不用删除。    
        {
            throw new Exception("边不存在!");
        }

        this.edges[v1][v2]=maxWeight;
        this.numOfEdges--;   
    }

    //打印邻接矩阵
    public void print()
    {
        for(int i=0;i<this.edges.length;i++ )
        {
            for(int j=0;j<this.edges[i].length;j++)
            {
                System.out.print(edges[i][j]+" ");    
            }
            System.out.println();
        }
    }
}





//插入的边的类
public class Weight {

    int row;  //起点
    int col;  //终点
    int weight; //权值

    Weight(int row,int col,int weight)
    {
        this.row = row;
        this.col = col;
        this.weight = weight;
    }

    public static void createAdjGraphic(MyAdjGraphic g, Object[] vertices, int n,Weight[] weight,int e)
    throws Exception
    {
       //初始化结点
       for(int i=0;i<n;i++)
       {
           g.insertVertice(vertices[i]);
       }
       //初始化所有的边
       for(int i=0;i<e;i++)
       {
           g.insertEdges(weight[i].row, weight[i].col, weight[i].weight);
       }
    }
}






public class Test {

    public static void main(String[] args) {

        int n=5; //5个结点
        int e=5; //5条边

        MyAdjGraphic g = new MyAdjGraphic(n);
        Object[] vertices = new Object[]{new Character('A'),new Character('B'),new Character('C'),new Character('D'),new Character('E')};
        Weight[] weights = new Weight[]{new Weight(0,1,10),new Weight(0,4,20),new Weight(2,1,40),new Weight(1,3,30),new Weight(3,2,50)};
        try
        {
           Weight.createAdjGraphic(g, vertices, n, weights, e);
           System.out.println("--------该临街矩阵如下---------");
           g.print();
           System.out.println("结点的个数:"+g.getNumOfVertice());
           System.out.println("边的个数:"+g.getNumOfEdges());
           g.deleteEdges(0, 4);
           System.out.println("--------删除之后---------");
           g.print();
           System.out.println("结点的个数:"+g.getNumOfVertice());
           System.out.println("边的个数:"+g.getNumOfEdges());
        }
        catch(Exception ex)
        {

        }
    }

}
/*--------该临街矩阵如下---------
0 10 -1 -1 20 
-1 0 -1 30 -1 
-1 40 0 -1 -1 
-1 -1 50 0 -1 
-1 -1 -1 -1 0 
结点的个数:5
边的个数:5
--------删除之后---------
0 10 -1 -1 -1 
-1 0 -1 30 -1 
-1 40 0 -1 -1 
-1 -1 50 0 -1 
-1 -1 -1 -1 0 
结点的个数:5
边的个数:4*/

 

admin

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注