用邻接表法表示的双向图(改单向容易,只要修改connect,disconect方法)。
此处只是表示数据结构,没有相关算法。
其中Vertex是辅助类表示顶点,其中包含一个boolean变量isVisited表示是否遍历过。
Graph表示图,实际存储顶点,以及顶点之间的关系,用一个数组存储顶点,另一个数组中存放与对应的顶点的相连的的顶点的下标。
大部分的代码实际是辅助代码,其中包括:
Vertex:顶点,其中包含一个Boolean变量,表示是否遍历过。
Node,Link:一个单向链表,存储与当前顶点向邻的节点的下标。(单向链表的详细描述见:Link
)
Graph的另一个实现请参见Graph
。
class Vertex {
private Object value;
private boolean isVisited;
Vertex(Object value) {
this.value = value;
}
void visit() { isVisited = true; }
boolean isVisited() { return isVisited; }
}
class Node {
private int index;
private Node next;
Node(int index) { this.index = index; }
void next(Node next) { this.next = next; }
Node next() { return next; }
int index() { return index; }
}
class Link {
private Node first;
private Node current;
void add(int index) {
Node node = new Node(index);
node.next(first);
first = node;
}
boolean hasNext() {
return current == null?
first != null:
current.next() != null;
}
Node next() {
if(current == null)current = first;
else current = current.next();
return current;
}
void reset() { current = null; }
void remove(int index) {
Node previous = null;
Node current = first;
while(current != null) {
if (current.index() == index) {
if(previous == null) first = current;
else previous.next(current.next());
return;
}
previous = current;
current = current.next();
}
}
}
class Graph {
private Vertex[] vertexs;
private Link[] adjTab;
private int pos = -1;
Graph(int size) {
vertexs = new Vertex[size];
adjTab = new Link[size];
}
void add(Object obj) {
assert pos < vertexs.length;
vertexs[++pos] = new Vertex(obj);
}
void connect(int from, int to) {
adjTab[from].add(to);
adjTab[to].add(from);
}
void disConnect(int from, int to) {
adjTab[from].remove(to);
adjTab[to].remove(from);
}
}
分享到:
相关推荐
领会图的两种主要存储结构、图基本运算算法和两种遍历算法设计内容:编写一个程序,设计带权图的邻接矩阵与邻接表的创建和输出运算,并在此基础上设计一个主程序完成如下功能:(1)建立如图所示的有向图G的邻接矩阵...
(1)键盘输入数据,建立一个有向图的邻接表,并输出该邻接表。 (2)在有向图的邻接表的基础上计算各顶点的度,并输出。 (3)以有向图的邻接表为基础实现并输出它的拓扑排序序列。 (4)在主函数中设计一个...
实现图的深度和广度优先搜索 .../* 从初始点v出发深度优先遍历邻接表GL表示的图 */ void DfsAdjlist(AdjList GL,int v) /*从初始点v出发广度优先遍历邻接表GL表示的图*/ void BfsAdjlist(AdjList GL,int v)
这些代码大约三百行左右 包括了邻接矩阵图邻接表图的结构和创建,还有两种图的深度和广度优先搜索和prim最小生成树算法,本人花了一周左右时间复习了这些东西,全部手打,绝对区别于网上的一些乱代码,无错并有大量...
这是用邻接链表作存储结构的图类源代码,下面是图类的声明部分: struct ArcNode //弧节点结构 { int adjvex; ArcNode *nextarc; }; struct VexNode //顶点结构 { int vexdata; ArcNode *firstarc; }; //邻接...
Status CreateGraph(Graph *G)/*以邻接表形式创建无向连通图G*/ {int m,n,i,j,k,v1,v2,flag=0; ArcNode *p1,*q1,*p,*q; printf("Please input the number of VNode: "); scanf("%d",&m); printf("Please input the ...
JS-Adjacency-table-of-undirected-graph 数据结构实验-无向图邻接表
使用VC6.0创建邻接多重表储存无向图的简易程序
printf("图的邻接表内容:\n"); for(i = 1; i 5; i++) { printf("顶点%d => ", head[i].vertex); ptr = head[i].nextnode; while(ptr != NULL) { printf(" %d", ...
图论算法,基础类的图的储存,边的储存,用数组邻接表的形式
本文实例为大家分享了C++有向图的邻接表表示,供大家参考,具体内容如下 一、思路: 有向图的插入有向边、删除边、删除顶点和无向图的有区别。其他的和无向图的类似。 1.插入有向边 只需要插入边就行,不需要插入...
数据结构图投资组合分配使用邻接矩阵或邻接表和各种算法(例如深度优先搜索,广度优先搜索和Dijkstra算法)存储的无向和有向图抽象数据类型的Python3实现。 该项目在2021年冬季季度完成,在Tim Alcon教授的指导下,...
用邻接表和邻接矩阵表示的图的 Java 实现 基于西帕拉联邦大学教授 Efren Lopes de Souza 博士创建的代码 ( )。 对于通过 exportToDotFile(String fileName) 方法生成图形的图形版本的功能,需要在地址下载...
数据结构实验-无向图邻接表-JavaScript
提供基于邻接表的图的实现。 边缘和节点可以用额外的(用户提供的)信息修饰。 还提供了深度优先和宽度优先的算法。 其中一些功能是:-创建和配置状态Tr
" " " "三、实验环境: " "Windows 7,Visual C++6.0 " "三、实验过程描述 " "文件graph.h中定义了图的邻接矩阵表示类型和邻接表表示类型,该头文件在以下三个 " "实验中都会使用到。其代码如下: " " " " " " " " ...
主要介绍了java实现图的邻接表存储结构的两种方式及实例应用详解,邻接表构建图是必须需要一个Graph对象,也就是图对象!该对象包含属性有:顶点数、边数以及图的顶点集合,需要的朋友可以参考下
Python实作有向图(邻接表) 加权图(邻接表)遍历广度优先搜索深度优先搜索最短路径广度优先搜索最短路径(有向图) Dikstra的最短路径(加权图) 贝尔曼·福特的最短路径(加权图) 优化的Bellman Ford的最短路径...
邻接矩阵存储的结构体中,包括一个存储边的结构体,存储每条边的信息(权值)将这个边的结构体的二维数组作为图的基本存储结构,放到单个图的结构体中每个图又包含总节点数、总边数、图的类型等信息
* 基于邻接边表实现图的顶点结构 */ package dsa; public class Vertex_List implements Vertex { //变量 protected Object info;//当前顶点中存放的数据元素 protected Position vPosInV;//当前顶点在所属的...