现在的位置: 首页 > 面试题 > 正文

图论基础和表示

2022年01月10日 面试题 ⁄ 共 2243字 ⁄ 字号 暂无评论
博客主机

一、概念及其介绍

图论(Graph Theory)是离散数学的一个分支,是一门研究图(Graph)的学问。

 

图是用来对对象之间的成对关系建模的数学结构,由"节点"或"顶点"(Vertex)以及连接这些顶点的"边"(Edge)组成。

 

值得注意的是,图的顶点集合不能为空,但边的集合可以为空。图可能是无向的,这意味着图中的边在连接顶点时无需区分方向。否则,称图是有向的。下面左图是一个典型的无向图结构,右图则属于有向图。本章节介绍的图都是无向图。

 

 

 

图的分类:无权图和有权图,连接节点与节点的边是否有数值与之对应,有的话就是有权图,否则就是无权图。

 

图的连通性:在图论中,连通图基于连通的概念。在一个无向图 G 中,若从顶点 i 到顶点 j 有路径相连(当然从j到i也一定有路径),则称 i 和 j 是连通的。如果 G 是有向图,那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。如果此图是有向图,则称为强连通图(注意:需要双向都有路径)。图的连通性是图的基本性质。

 

完全图:完全是一个简单的无向图,其中每对不同的顶点之间都恰连有一条边相连。

 

自环边:一条边的起点终点是一个点。

 

平行边:两个顶点之间存在多条边相连接。

 

二、适用说明

图可用于在物理、生物、社会和信息系统中建模许多类型的关系和过程,许多实际问题可以用图来表示。因此,图论成为运筹学、控制论、信息论、网络理论、博弈论、物理学、化学、生物学、社会科学、语言学、计算机科学等众多学科强有力的数学工具。在强调其应用于现实世界的系统时,网络有时被定义为一个图,其中属性(例如名称)之间的关系以节点和或边的形式关联起来。

 

三、图的表达形式

邻接矩阵:1 表示相连接,0 表示不相连。

 

 

 

邻接表:只表达和顶点相连接的顶点信息

 

 

 

邻接表适合表示稀疏图 (Sparse Graph)

 

邻接矩阵适合表示稠密图 (Dense Graph)

 

Java 实例代码

源码包下载:Download

 

(1) 邻接矩阵

 

src/runoob/graph/DenseGraph.java 文件代码:

package runoob.graph;

 

/**

* 邻接矩阵

*/

public class DenseGraph {

// 节点数

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];

}

// 返回节点个数

public int V(){ return n;}

// 返回边的个数

public int E(){ return m;}

 

// 向图中添加一个边

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的边

boolean hasEdge( int v , int w ){

assert v >= 0 && v < n ;

assert w >= 0 && w < n ;

return g[v][w];

}

}

(2)邻接表

 

src/runoob/graph/SparseGraph.java 文件代码:

package runoob.graph;

 

import java.util.Vector;

 

/**

* 邻接表

*/

public class SparseGraph {

// 节点数

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 = 0;

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>();

}

// 返回节点个数

public int V(){ return n;}

// 返回边的个数

public int E(){ return m;}

// 向图中添加一个边

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 ++;

}

 

// 验证图中是否有从v到w的边

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;

}

}

Wopus问答

Wopus问答

给我留言

留言无头像?


×