图(Graph):图(Graph)是一种比线性表和树更为复杂的数据结构。 图结构:是研究数据元素之间的多对多的关系。在这种结构中,任意两个元素之间可能存在关系。即结点之间的关系可以是任意的,图中任意元素之间都可能相关。 图G由两个集合V(顶点Vertex)和E(边Edge)组成,定义为G=(V,E) 线性结构:是研究数据元素之间的一对一关系。在这种结构中,除第一个和最后一个元素外,任何一个元素都有唯一的一个直接前驱和直接后继。 树结构:是研究数据元素之间的一对多的关系。在这种结构中,每个元素对下(层)可以有0个或多个元素相联系,对上(层)只有唯一的一个元素相关,数据元素之间有明显的层次关系。
一个图(G)定义为一个偶对(V,E) ,记为G=(V,E) 。其中: V是顶点(Vertex)的非空有限集合,记为V(G);E是无序集V&V的一个子集,记为E(G) ,其元素是图的弧(Arc)。 将顶点集合为空的图称为空图。其形式化定义为:
G=(V ,E)
V={v|vdata object}
E={<v,w>| v,wV∧p(v,w)}
对于一个图,若每条边都是没有方向的,则称该图为无向图。图示如下:
因此,(Vi,Vj)和(Vj,Vi)表示的是同一条边。注意,无向图是用小括号,而下面介绍的有向图是用尖括号。 无向图的顶点集和边集分别表示为: V(G)={V1,V2,V3,V4,V5} E(G)={(V1,V2),(V1,V4),(V2,V3),(V2,V5),(V3,V4),(V3,V5),(V4,V5)} 对于一个图G,若每条边都是有方向的,则称该图为有向图。图示如下:
有向图的顶点集和边集分别表示为: V(G)={V1,V2,V3} E(G)={
我们将具有n(n-1)/2条边的无向图称为无向完全图。同理,将具有n(n-1)条边的有向图称为有向完全图。
对于无向图,若图中顶点数为n ,用e表示边的数目,则e [0,n(n-1)/2] 。具有n(n-1)/2条边的无向图称为完全无向图。 完全无向图另外的定义是: 对于无向图G=(V,E),若vi,vj V ,当vi≠vj时,有(vi ,vj)E,即图中任意两个不同的顶点间都有一条无向边,这样的无向图称为完全无向图。 #### 完全有向图 对于有向图,若图中顶点数为n ,用e表示弧的数目,则e[0,n(n-1)] 。具有n(n-1)条边的有向图称为完全有向图。 完全有向图另外的定义是: 对于有向图G=(V,E),若vi,vjV ,当vi ≠vj时,图中任意两个不同的顶点间都有一条弧,这样的有向图称为完全有向图。
设有图G=(V,E)和G’=(V’,E’),若V’V且E’E ,则称图G’是G的子图;若V’=V且E’E,则称图G’是G的一个生成子图。
连通图是指图G中任意两个顶点Vi和Vj都连通,则称为连通图。比如图(b)就是连通图。下面是一个非连通图的例子。
1) 深度优先搜索遍历 深度优先搜索DFS遍历类似于树的前序遍历。其基本思路是: a) 假设初始状态是图中所有顶点都未曾访问过,则可从图G中任意一顶点v为初始出发点,首先访问出发点v,并将其标记为已访问过。 b) 然后依次从v出发搜索v的每个邻接点w,若w未曾访问过,则以w作为新的出发点出发,继续进行深度优先遍历,直到图中所有和v有路径相通的顶点都被访问到。 c) 若此时图中仍有顶点未被访问,则另选一个未曾访问的顶点作为起点,重复上述步骤,直到图中所有顶点都被访问到为止。 图示如下:
注:红色数字代表遍历的先后顺序,所以图(e)无向图的深度优先遍历的顶点访问序列为:V0,V1,V2,V5,V4,V6,V3,V7,V8 如果采用邻接矩阵存储,则时间复杂度为O(n2);当采用邻接表时时间复杂度为O(n+e)。 2) 广度优先搜索遍历 广度优先搜索遍历BFS类似于树的按层次遍历。其基本思路是: a) 首先访问出发点Vi b) 接着依次访问Vi的所有未被访问过的邻接点Vi1,Vi2,Vi3,…,Vit并均标记为已访问过。 c) 然后再按照Vi1,Vi2,… ,Vit的次序,访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过,依此类推,直到图中所有和初始出发点Vi有路径相通的顶点都被访问过为止。 图示如下:
因此,图(f)采用广义优先搜索遍历以V0为出发点的顶点序列为:V0,V1,V3,V4,V2,V6,V8,V5,V7 如果采用邻接矩阵存储,则时间复杂度为O(n2),若采用邻接表,则时间复杂度为O(n+e)。
AdjGraph *Create_Graph(MGraph * G)
{ printf(“请输入图的种类标志:”) ;
scanf(“%d”, &G->kind) ;
G->vexnum=0 ; /* 初始化顶点个数 */
return(G) ;
}
图的顶点定位操作实际上是确定一个顶点在vexs数组中的位置(下标) ,其过程完全等同于在顺序存储的线性表中查找一个数据元素。
int LocateVex(MGraph *G , VexType *vp)
{ int k ;
for (k=0 ; k<G->vexnum ; k++)
if (G->vexs[k]==*vp) return(k) ;
return(-1) ; /* 图中无此顶点 */
}
向图中增加一个顶点的操作,类似在顺序存储的线性表的末尾增加一个数据元素。
int AddVertex(MGraph *G , VexType *vp)
{ int k , j ;
if (G->vexnum>=MAX_VEX)
{ printf(“Vertex Overflow !\n”) ; return(-1) ; }
if (LocateVex(G , vp)!=-1)
{ printf(“Vertex has existed !\n”) ; return(-1) ; }
k=G->vexnum ; G->vexs[G->vexnum++]=*vp ;
if (G->kind==DG||G->kind==AG)
for (j=0 ; j<G->vexnum ; j++)
G->adj[j][k].ArcVal=G->adj[k][j].ArcVal=0 ;
/* 是不带权的有向图或无向图 */
else
for (j=0 ; j<G->vexnum ; j++)
{ G->adj[j][k].ArcVal=INFINITY ;
G->adj[k][j].ArcVal=INFINITY ;
/* 是带权的有向图或无向图 */
}
return(k) ;
}
根据给定的弧或边所依附的顶点,修改邻接矩阵中所对应的数组元素。
int AddArc(MGraph *G , ArcType *arc)
{ int k , j ;
k=LocateVex(G , &arc->vex1) ;
j=LocateVex(G , &arc->vex1) ;
if (k==-1||j==-1)
{ printf(“Arc’s Vertex do not existed !\n”) ;
return(-1) ;
if (G->kind==DG||G->kind==WDG)
{ G->adj[k][j].ArcVal=arc->ArcVal;
G->adj[k][j].ArcInfo=arc->ArcInfo ;
/* 是有向图或带权的有向图*/
}
else
{ G->adj[k][j].ArcVal=arc->ArcVal ;
G->adj[j][k].ArcVal=arc->ArcVal ;
G->adj[k][j].ArcInfo=arc->ArcInfo ;
G->adj[j][k].ArcInfo=arc->ArcInfo ;
/* 是无向图或带权的无向图,需对称赋值 */
}
return(1) ;
一个连通图的生成树是一个极小的连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。那么我们把构造连通网的最小代价生成树称为最小生成树。 找连通网的最小生成树,经典的有两种算法,普里姆算法和克鲁斯卡尔算法。
@Test
public void Dijkstra(){
int distance[] = new int[9];
int pre[] = new int[9];
boolean finished[] = new boolean[9];
finished[0] = true;
for(int i=0;i<9;i++){
distance[i] = g1.adjMatrix[0][i];
}
int k = 0;
for(int i=1;i<9;i++){
int min = 65536;
for(int j=0;j<9;j++){
if(!finished[j]&&distance[j]<min){
min = distance[j];
k = j;
}
}
finished[k] = true;
System.out.println(pre[k]+","+k);
for(int j=1;j<9;j++){
if(!finished[j]&&(min+g1.adjMatrix[k][j])<distance[j]){
distance[j] = min+g1.adjMatrix[k][j];
pre[j] = k;
}
}
}
}
(1)栈:用来存放入度为0的节点; (2)变种邻接列表:作为图的存储结构;此邻接列表的顶点节点还需要存放入度属性;
private static String topologicalSort(Graph2 g2) {
Stack<Integer> s = new Stack<Integer>();
int count = 0;
for(int i=0;i<g2.nodes.length;i++){
if(g2.nodes[i].indegree==0){
s.push(i);
}
}
while(!s.isEmpty()){
int value = s.pop();
System.out.println(value+"、");
count++;
EdgeNode node = g2.nodes[value].next;
while(node!=null){
g2.nodes[node.idx].indegree--;
if(g2.nodes[node.idx].indegree==0){
s.push(node.idx);
}
node = node.next;
}
}
if(count<g2.nodes.length){
return "error";
}
return "ok";
}
在某些应用中,有时主要考察图中各个边的权值以及所依附的两个顶点,即图的结构主要由边来表示,称为边表存储结构。 在边表结构中,边采用顺序存储,每个边元素由三部分组成:边所依附的两个顶点和边的权值;图的顶点用另一个顺序结构的顶点表存储。如图: