有向图 在有向图中,结点对<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>。
完全图 在有n个结点的无向图中,若有n(n-1)/2条边,即任意两个结点之间有且只有一条边,则称此图为无向完全图。在有n个结点的有向图中,若有n(n-1)条边,即任意两个结点之间有且只有方向相反的两条边,则称此图为有向完全图。
邻接结点 在无向图G中,若(u,v)是E(G)中的一条边,则称u和v互为邻接结点,并称边(u,v)依附于结点u和v。在有向图G中,若<u,v>是E(G)中的一条边,则称结点u邻接到结点v,结点v邻接自结点u,并称边<u,v>和结点u和结点v相关联。
结点的度 结点v的度是与它相关联的边的条数,记作TD(v)。
路径 在图G=(V,E)中,若从结点vi出发有一组边使可到达结点vj,则称结点vi到结点vj的结点序列为从结点vi到结点vj的路径。
权 有些图的边附带有数据信息,这些附带的数据信息称为权。第i条边的权用符号wi表示。
路径长度 对于不带权的图,一条路径的路径长度是指该路径上的边的条数;对于带权的图,一条路径的路径长度是指该路径上各个边权值的总和。
最小生成树 一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图联通的最少的边。(n-1)条边。
图的邻接矩阵存储结构
假设图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的路径权值。
import java.util.ArrayList; //邻接矩阵类
public class MyAdjGraphic { static final int maxWeight=-; //如果两个结点之间没有边,权值为-1;
ArrayList vertices = new ArrayList();//存放结点的集合
int[][] edges; //邻接矩阵的二维数组
int numOfEdges; //边的数量 public MyAdjGraphic(int n)
{
edges = new int[n][n];
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
if(i==j) //对角线上的元素为0
{
edges[i][j]=;
}
else
{
edges[i][j]=maxWeight;
}
}
}
numOfEdges = ;
} //返回边的数量
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 < || v1 >= vertices.size())||(v2 < ||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 < || v1 >= vertices.size())||(v2 < ||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 < || v1 >= vertices.size())||(v2 < ||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=;i<this.edges.length;i++ )
{
for(int j=;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=;i<n;i++)
{
g.insertVertice(vertices[i]);
}
//初始化所有的边
for(int i=;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个结点
int e=; //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(,,),new Weight(,,),new Weight(,,),new Weight(,,),new Weight(,,)};
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(, );
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*/