图的存储结构
图的存储结构比较复杂,其复杂性主要表现在:
◆任意顶点之间可能存在联系,无法以数据元素在存储区中的物理位置来表示元素之间的关系。
◆图中顶点的度不一样,有的可能相差很大,若按度数最大的顶点设计结构,则会浪费很多存储单元,反之按每个顶点自己的度设计不同的结构,又会影响操作。
图的常用的存储结构有:邻接矩阵、邻接链表、十字链表、邻接多重表和边表,其中邻接矩阵和邻接链表是比较常用的表示方法。
邻接矩阵(数组)表示法
基本思想:对于有n个顶点的图,用一维数组vexs[n]存储顶点信息,用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中,以顶点在vexs数组中的下标代表顶点,邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系的信息。
1无向图的数组表示
(1)无权图的邻接矩阵
无向无权图G=(V,E)有n(n≧1)个顶点,其邻接矩阵是n阶对称方阵,如下图所示。其元素的定义如下:
(2)带权图的邻接矩阵
无向带权图G=(V,E)的邻接矩阵如下图所示。其元素的定义如下:
(3)无向图邻接矩阵的特性
◆邻接矩阵是对称方阵;
◆对于顶点vi,其度数是第i行的非0元素的个数;
◆无向图的边数是上(或下)三角形矩阵中非0元素个数。
2有向图的数组表示
(1)无权图的邻接矩阵
若有向无权图G=(V,E)有n(n≧1)个顶点,则其邻接矩阵是n阶对称方阵,如图7-7所示。元素定义如下:
(2)带权图的邻接矩阵
有向带权图G=(V,E)的邻接矩阵如图所示。其元素的定义如下:
⑶有向图邻接矩阵的特性
◆对于顶点vi,第i行的非0元素的个数是其出度OD(vi);第i列的非0元素的个数是其入度ID(vi)。
◆邻接矩阵中非0元素的个数就是图的弧的数目。
邻接矩阵表示法
上一节讲了图的定义和基本概念,以及接口的定义,现在对上一节中的接口进行类的实现,如下。
MatrixEdge.java
package datastructure.graph;
/**
* 邻接矩阵表示法表示的图
* @author luoweifu
*
*/
public class MatrixEdge extends Edge {
private Object v1, v2;
/**
* 构造函数
* @param weight 权值
*/
public MatrixEdge(double weight) {
v1 = null;
v2 = null;
this.info = null;
this.weight = weight;
}
/**
* 构造函数
* @param v1 第一个顶点
* @param v2 第二个顶点
* @param info 边的信息
* @param weight 权值
*/
public MatrixEdge( Object v1, Object v2, Object info, double weight ) {
super(info, weight);
this.v1 = v1;
this.v2 = v2;
}
@Override
public Object getFirstVertex() {
return v1;
}
@Override
public Object getSecondVertex() {
return v2;
}
@Override
public int compareTo(Object o) {
Edge e = (Edge)o;
if(this.weight > e.getWeight())
return 1;
else if(this.weight < e.getWeight())
return -1;
else
return 0;
}
@Override
public boolean equals(Object obj) {
return ((Edge)obj).info.equals(info) && ((Edge)obj).getWeight() == this.weight;
}
@Override
public String toString() {
//return "边信息:" + info + "\t权值:" + weight + "\t顶点1:" + getFirstVertex() + "\t顶点2:" + getSecondVertex();
return "" + weight;
}
}
MatrixGraph.java
package datastructure.graph;
import datastructure.list.ArrayList;
import datastructure.list.List;
import datastructure.queue.ArrayQueue;
import datastructure.queue.Queue;
/**
* 邻接矩阵法表示图
* @author luoweifu
*
*/
public class MatrixGraph implements Graph {
private static final int defaultSize = 10;
private int maxLen; //矩阵的最大长度
private int edgeNum; //边的条数
private List vertexs;
private Edge edges[][];
private enum Visit{unvisited, visited};
/**
* 构造函数
*/
public MatrixGraph() {
maxLen = defaultSize;
vertexs = new ArrayList();
edges = new MatrixEdge[maxLen][maxLen];
}
/**
* 构造函数
* @param vexs 顶点的数组
*/
public MatrixGraph(Object vexs[]) {
maxLen = vexs.length;
vertexs = new ArrayList();
edges = new MatrixEdge[maxLen][maxLen];
for(int i=0; i<maxLen; i++) {
vertexs.add(vexs[i]);
}
}
@Override
public void addEdge(Object v1, Object v2, double weight) {
int i1 = vertexs.indexOf(v1);
int i2 = vertexs.indexOf(v2);
//System.out.println("i1: " + i1 + " i2:" + i2);
if(i1>=0 && i1<vertexs.size() && i2 >=0 && i2<vertexs.size()) {
edges[i1][i2] = new MatrixEdge(v1, v2, null, weight);
edgeNum ++;
} else {
throw new ArrayIndexOutOfBoundsException("顶点越界或对应的边不合法!");
}
}
@Override
public void addEdge(Object v1, Object v2, Object info, double weight) {
int i1 = vertexs.indexOf(v1);
int i2 = vertexs.indexOf(v2);
if(i1>=0 && i1<vertexs.size() && i2 >=0 && i2<vertexs.size()) {
edges[i1][i2] = new MatrixEdge( v1, v2, info, weight);
edgeNum ++;
} else {
throw new ArrayIndexOutOfBoundsException("顶点越界或对应的边不合法!");
}
}
@Override
public void addVex(Object v) {
vertexs.add(v);
if(vertexs.size() > maxLen) {
expand();
}
}
private void expand() {
MatrixEdge newEdges[][] = new MatrixEdge[2*maxLen][2*maxLen];
for(int i=0; i<maxLen; i++) {
for(int j=0; j<maxLen; j++) {
newEdges[i][j] = (MatrixEdge) edges[i][j];
}
}
edges = newEdges;
}
@Override
public int getEdgeSize() {
return edgeNum;
}
@Override
public int getVertexSize() {
return vertexs.size();
}
@Override
public void removeEdge(Object v1, Object v2) {
int i1 = vertexs.indexOf(v1);
int i2 = vertexs.indexOf(v2);
if(i1>=0 && i1<vertexs.size() && i2 >=0 && i2<vertexs.size()) {
if(edges[i1][i2] == null) {
try {
throw new Exception("该边不存在!");
} catch (Exception e) {
e.printStackTrace();
}
} else {
edges[i1][i2] = null;
edgeNum --;
}
} else {
throw new ArrayIndexOutOfBoundsException("顶点越界或对应的边不合法!");
}
}
@Override
public void removeVex(Object v) {
int index = vertexs.indexOf(v);
int n = vertexs.size();
vertexs.remove(index);
for(int i=0; i<n; i++){
edges[i][n-1] = null;
edges[n-1][i] = null;
}
}
@Override
public String printGraph() {
StringBuilder sb = new StringBuilder();
int n = getVertexSize();
for (int i = 0; i < n; i++) {
for(int j=0; j<n; j++) {
sb.append(" " + edges[i][j]);
}
sb.append("\n");
}
return sb.toString();
}
@Override
public void clear() {
maxLen = defaultSize;
vertexs.clear();
edges = null;
}
@Override
public String bfs(Object o) {
Visit visit[] = new Visit[vertexs.size()];
for(int i=0; i<vertexs.size(); i++)
visit[i] = Visit.unvisited;
StringBuilder sb = new StringBuilder();
bfs(o, visit, sb);
return sb.toString();
}
private void bfs(Object o, Visit[] visit, StringBuilder sb) {
Queue queue = new ArrayQueue();
int n = vertexs.indexOf(o);
sb.append(o + "\t");
visit[n] = Visit.visited;
queue.push(o);
while(!queue.isEmpty()) {
Object u = queue.deQueue();
Object v = getFirstVertex(u);
while(null != v) {
if(Visit.unvisited == visit[vertexs.indexOf(v)]) {
sb.append(v + "\t");
visit[vertexs.indexOf(v)] = Visit.visited;
queue.push(v);
}
v = getNextVertex(u, v);
}
}
}
@Override
public String dfs(Object o) {
Visit visit[] = new Visit[vertexs.size()];
for(int i=0; i<vertexs.size(); i++)
visit[i] = Visit.unvisited;
StringBuilder sb = new StringBuilder();
dfs(o, visit, sb);
return sb.toString();
}
private void dfs(Object o, Visit[] visit, StringBuilder sb) {
int n = vertexs.indexOf(o);
sb.append(o + "\t");
visit[n] = Visit.visited;
Object v = getFirstVertex(o);
while(null != v) {
if(Visit.unvisited == visit[vertexs.indexOf(v)])
dfs(v, visit, sb);
v = getNextVertex(o, v);
}
}
@Override
public Object getFirstVertex(Object v) {
int i = vertexs.indexOf(v);
if(i<0)
throw new ArrayIndexOutOfBoundsException("顶点v不存在!");
for(int col=0; col<vertexs.size(); col++)
if(edges[i][col] != null)
return vertexs.get(col);
return null;
}
@Override
public Object getNextVertex(Object v1, Object v2) {
int i1 = vertexs.indexOf(v1);
int i2 = vertexs.indexOf(v2);
if(i1<0 || i2<0)
throw new ArrayIndexOutOfBoundsException("顶点v不存在!");
for(int col=i2+1; col<vertexs.size(); col++)
if(edges[i1][col] != null)
return vertexs.get(col);
return null;
}
}
测试程序Test.java
package datastructure.graph;
public class Test {
public static void main(String args[]) {
Object obj[] = { 'A', 'B', 'C', 'D', 'E', 'F' };
//Graph graph = new MatrixGraph(obj);
Graph graph = new MatrixGraph(obj);
//graph.addVex('F');
graph.addEdge('A','C',5);
graph.addEdge('B','A',2);
graph.addEdge('C','B',15);
graph.addEdge('E','D',4);
graph.addEdge('F','E',18);
graph.addEdge('A', 'F', 60);
graph.addEdge('C', 'F', 70);
System.out.println(graph.printGraph());
/*graph.removeEdge('A', 'C');
System.out.println(graph.printGraph());
graph.removeVex('E');
System.out.println(graph.printGraph());*/
System.out.println(graph.dfs('A'));
System.out.println(graph.bfs('A'));
}
}
分享到:
相关推荐
图的邻接矩阵的表示及各种操作,比如找图中第 i 个结点的第一个邻结点,深度优先遍历(递规),以结点P为根创建深度优先生成树(递归),建立深度优先生成森林,前序输出生成森林(孩子兄弟表示法),PRIM算法构造...
本程序实现了数据结构课本中有关有向图的两个基本操作——拓扑排序和关键路径的求法,在求关键路径的算法中由于路径的不唯一性故只给出关键活动,在拓扑排序中则具体实现排序的过程及结果。
C# 图的各种数学表达 有向图的关联矩阵、边列表、正向表、邻接表的表示 各种表达的相互转换 最短路径求法
2. 将矩阵表示的迷宫转换成无向图,用邻接表存储; 3. 对无向图从入口结点开始广度优先搜索; 4. 用一个一维数组存储各个结点的前驱结点的编号; 5. 通过出口结点Vn找到其前驱结点Vn-1,再通过Vn-1找到Vn-2; 6. 依次...
例如,数组的连续存储,链表的动态分配节点,树和图的邻接矩阵或邻接表表示等。 基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和...
例如,数组的连续存储,链表的动态分配节点,树和图的邻接矩阵或邻接表表示等。 基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和...
例如,数组的连续存储,链表的动态分配节点,树和图的邻接矩阵或邻接表表示等。 基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和...
2. 二分图最大匹配(hungary邻接表形式,邻接阵接口) 10 3. 二分图最大匹配(hungary邻接阵形式) 10 4. 二分图最大匹配(hungary正向表形式) 11 5. 二分图最佳匹配(kuhn_munkras邻接阵形式) 11 6. 一般图匹配(邻接表形式...
16.7.2 邻接矩阵类 16.7.3 扩充chain类 16.7.4 链表类 16.8 图的遍历 16.8.1 广度优先搜索 16.8.2 广度优先搜索的实现 16.8.3 方法graph::bfs的复杂性分析 16.8.4 深度优先搜索 16.8.5 深度优先搜索的实现 16.8.6 ...
(2)快速矩阵转置 (Fast_Transpos) (3)矩阵乘法 (Multiply_Sparmat) 6. 广义表 (1)求广义表的深度(Ls_Depth) (2)复制广义表(Ls_Copy) (3)创建广义表的存储结构(Crt_Lists) 7. 二叉树 (1)遍历...
数据结构算法演示(Windows版...窗口下方显示图的邻接表,演示过程中以红色框边表示已访问过的弧。图示窗口的下方显示遍历后输出的顶点序列。 22. 图的广度优先搜索 与深度优先不同的是,在窗口的下方增加一个队列,...
2.4.4 用N-S 流程图表示算法 29 2.4.5 用伪代码表示算法 30 2.4.6 用计算机语言表示算法 31 2.5 结构化程序设计方法 31 3 数据类型、运算符与表达式 3.1 C语言的数据类型 32 3.2 常量与变量 33 23.2.1 常量和符号...
2.4.4 用N-S 流程图表示算法 29 2.4.5 用伪代码表示算法 30 2.4.6 用计算机语言表示算法 31 2.5 结构化程序设计方法 31 3 数据类型、运算符与表达式 3.1 C语言的数据类型 32 3.2 常量与变量 33 23.2.1 常量和符号...
右上是邻接矩阵;左上是无向网的逻辑结构,图中顶点的初始状态为黄色,算法执行过程中,红色覆盖的顶点和边则表示已加入生成树的顶点和生成树上的边;窗口的下方则显示 closedge 数组中的值。 28. 克鲁斯卡尔算法 ...
1.7.6 图的遍历(2)——广度优先搜索 1.7.7 实例与分析 第2章 常用的查找与排序方法 2.1 顺序查找 2.2 折半查找 2.3 排序的概述 2.4 直接插入排序 2.5 选择排序 2.6 冒泡排序 2.7 希尔排序 2.8 快速排序 第3章 ...