#include<iostream>
#include<string>
using namespace std;
#define MAX_VEX 50
template<class T> //邻接表的链表结构
struct LNode{
int Index;
LNode<T> *next;
LNode():Index(0),next(NULL){}
};
template<class T> //邻接表的数组结构
struct VexNode{
T data;
LNode<T> *first;
VexNode():data(T()),first(NULL){}
};
template<class T>
class Graph
{
public:
Graph()
{
vex=new VexNode<T>[MAX_VEX];
vexcount=0;
edgecount=0;
}
void addVex(T element); //增加顶点
void addEdge(T start,T end); //增加边
void display();
~Graph()
{
delete[] vex;
}
private:
VexNode<T> *vex;
int vexcount;
int edgecount;
};
template<class T>
void Graph<T>::addVex(T element)
{
if((vexcount+1)<=MAX_VEX)
{
VexNode<T> *p=new VexNode<T>;
p->data=element;
p->first=NULL;
vex[vexcount++]=*p;
}
else
{
cout<<"图的顶点已满,不能再添加顶点!"<<endl;
return ;
}
}
template<class T>
void Graph<T>::addEdge(T start,T end)
{
int i,j;
for(i=0;i<vexcount;i++)
{
if(start==vex[i].data)
break;
}
for(j=0;j<vexcount;j++)
{
if(end==vex[j].data)
break;
}
LNode<T> *p=vex[i].first,*q=vex[i].first;
LNode<T> *s=new LNode<T>;
s->Index=j;
s->next=NULL;
if(vex[i].first==NULL)
{
vex[i].first=s;
}
else
{
while(p)
{
q=p;
p=p->next;
}
q->next=s;
}
}
template<class T>
void Graph<T>::display()
{
cout<<"图:"<<endl<<endl;
LNode<T> *p;
for(int i=0;i<vexcount;i++)
{
if(vex[i].first==NULL)
{
cout<<vex[i].data<<endl;
}
else
{
p=vex[i].first;
while(p)
{
cout<<vex[i].data<<"—"<<vex[(p->Index)].data<<endl;
p=p->next;
}
}
}
}
int main()
{
Graph<string> gs;
gs.addVex("v0");
gs.addVex("v1");
gs.addVex("v2");
gs.addVex("v3");
gs.addEdge("v0","v1");
gs.addEdge("v0","v2");
gs.addEdge("v0","v3");
gs.addEdge("v1","v2");
gs.addEdge("v2","v3");
gs.display();
return 0;
}
分享到:
相关推荐
图的邻接矩阵存储和邻接表存储 代码完整 有注释,有需要的可以下载看看,基本是图的邻接矩阵存储和邻接表存储 代码完整
程序设计任务: 设计一个程序,实现以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。基本要求:以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的...
头歌数据结构图的邻接表存储及遍历操作 第1关图的邻接表存储及求邻接点操作 第2关图的深度遍历 第3关图的广度遍历 稳过
假设图中各边的权值都相等,以邻接矩阵和邻接表为存储结构,分别写出算法: (1)求顶点vi到顶点vj(i<>j)的最短路径 (2)求源点vi到其余各顶点的最短路径 要求输出路径上的所有顶点(利用BFS遍历的思想)
2、 按照建立一个带权有向图的操作需要,编写在邻接矩阵或邻接表存储结构下,带权有向图基本操作的实现函数(如初始化图、在图中插入一个结点、在图中插入一条边、在图中寻找序号为v的结点的第一个邻接结点、在图中...
里面有数据结构的一些详细信息,有关邻接表的广度和深度的测试以及怎么用C语言编写邻接表
数据结构那本书上的图的邻接表存储 struct node { int vertex; struct node * nextnode; };
自行实现图的邻接矩阵和邻接表存储结构 邻接矩阵类和邻接表类的实现及测试函数 功能全 代码易理解 可直接运行
领会图的两种主要存储结构、图基本运算算法和两种遍历算法设计内容:编写一个程序,设计带权图的邻接矩阵与邻接表的创建和输出运算,并在此基础上设计一个主程序完成如下功能:(1)建立如图所示的有向图G的邻接矩阵...
分别采用邻接矩阵、邻接表存储结构实现图的遍历
用邻接表实现无向图的存储结构,并进行深度优先搜索及广度优先搜索。
基于邻接表存储的图的拓扑排序算法,学习C++和理解数据结构很有帮助
是图的着色问题的基础 用邻接表存储图的结构
2、 按照建立一个带权有向图的操作需要,编写在邻接矩阵或邻接表存储结构下,带权有向图基本操作的实现函数(如初始化图、在图中插入一个结点、在图中插入一条边、在图中寻找序号为v的结点的第一个邻接结点、在图中...
实现了用邻接矩阵创建邻接表 包括创建UDG 输出UDG 等一系列操作
c语言写的有向图的邻接表的实现,通过使用图的邻接表实现图的存储结构存储。
《数据结构与算法(C++版)》先关 邻接表表示的图的广度优先遍历的动画演示
1、 定义邻接表存储的图类。 2、 实验验证如下算法的正确性、各种功能及指标: 1)创建一个邻接表存储的图; 2)返回图中指定边的权值; 3)返回图中某顶点的第一个邻接顶点; 4)返回图中某顶点关于另一个顶点的下...
数据结构中图的邻接表存储以及其遍历算法!
编译原理的作业,有了一点数据结构的知识编的,可能有遗漏,请提点意见!