图的基本操作与实现

摘要：

图（Graph）是⼀种⾮线性结构，它的每⼀个顶点可以与多个其它顶点相关联，各顶点之间的关系是任意的。这种结构的灵活性很强，可以⽤来描述和求解更多的实际问题，因此得到⼴泛的应⽤。最典型的应⽤领域有电路分析、寻找最短路线、项⽬规划、鉴别化合物、统计⼒学、遗传学、控制论、语⾔学，以及⼀些社会科学中。反过来，也正是由于其限制很少，已不再属于线性结构，因此运⽤这类结构时需要有更多的技巧。本课题是在VC++环境下，运⽤图的性质完成各种基本操作的实现。关键词：邻接矩阵；邻接表；深度（⼴度）优先遍历；连通分量；递归⽬录

1需求分析 (1)1.1课程设计题⽬ (1)1.2课程设计任务及要求 (1)1.3课程设计思想 (1)2概要设计 (2)

2.1程序的整体功能结构 (2)2.2数据结构的设计 (3)3详细设计和实现 (5)3.1算法流程图 (5)

3.2 各个要求的实现⽅法 (5)3.3主程序设计 (7)4调试与操作说明 (20)4.1程序调试与体会 (20)4.2程序运⾏结果 (21)总结 (23)致谢 (24)参考⽂献 (25)1需求分析1.1课程设计题⽬

(1)⾃选存储结构,输⼊含n个顶点（⽤字符表⽰顶点）和e条边的图G；(2)求每个顶点的度,输出结果；

(3)指定任意顶点x为初始顶点,对图G作DFS遍历,输出DFS顶点序列(提⽰:使⽤⼀个栈实现DFS)；

(4)指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶点序列(提⽰:使⽤⼀个队列实现BFS)；

(5)输⼊顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历(执⾏操作3)；否则输出信息“⽆x”；(6)判断图G是否是连通图，输出信息“YES”/“NO”；

(7)如果选⽤的存储结构是邻接矩阵,则⽤邻接矩阵的信息⽣成图G的邻接表,即复制图G,然再执⾏操作(2)；反之亦然。1.2课程设计任务及要求1.搜集图⽅⾯的资料；

2.负责设计数据结构，画好流程图，编写代码；3.撰写课程设计报告；4.参加答辩。1.3课程设计思想1.3.1 图的邻接表表⽰

在第i⾏的单链表中，各结点分别存放与同⼀个顶点vi关联的各条边。

各结点配有标识dest，指⽰该边的另⼀个顶点；还配有指针link，指向同⼀链表中的下⼀条边的边结点。对于带权图，结点中还要保存该边的权值cost。

通过在顶点表的第i个顶点信息中保存的指针adj，可以找到与顶点i对应的边链表的第⼀个边结点；此外，该记录还保存有该顶点的其他信息。1.3.2 图的深度优先搜索

深度优先搜索是个不断探查和回溯的过程。在探查的每⼀步，算法都有⼀个当前顶点。最初的当前顶点，也就是指定的起始顶点。每⼀步探查过程中，⾸先对当前顶点v进⾏访问，并⽴即设置该顶点的访问标志visited[v]=true。接着在v的所有邻接顶点中，找出尚未访问过的⼀个，将其作为下⼀步探查的当前顶点。倘若当前顶点的所有邻接顶点都已经被访问过，则退回⼀步，将前⼀步所访问的顶点重新取出，当作探查的当前顶点。

重复上述过程，直到最初指定起始顶点的所有邻接顶点都被访问到，此时连通图中的所有顶点也必然都被访问过了。1.3.3 图的⼴度优先搜索

⼴度优先搜索时⼀个逐层遍历的过程，在此过程中，图中有多少顶点就要重复多少步。每⼀步都有⼀个当前顶点。最初的当前顶点是主过程指定的起始顶点。在每⼀步中，⾸先访问当前顶点v，并设置该顶点的访问标志visited[v]=true。接着依次访问v的各个未曾被访问过的邻接顶点w1，w2，…，wt，然后再顺序访问w1，w2，…，wt的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，如此做下去，直到图中所有顶点都被访问为⽌。2概要设计

2.1程序的整体功能结构

输⼊1个图先求出每个顶点的度,输出结果；然后指定任意顶点x为初始顶点,对图G作DFS遍历,输出DFS顶点序列；接着指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶点序列；其次输⼊顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历(执⾏操作

3)；否则输出信息“⽆x”；下⼀步是判断图G是否是连通图，输出信息

“YES”/“NO”；最后如果选⽤的存储结构是邻接矩阵,则⽤邻接矩阵的信息⽣成图G的邻接表,即复制图G,然再执⾏操作(2)；反之亦然。

2.2数据结构的设计2.2.1边节点类的定义struct Edge //边结点的定义{

int dest; //边的另⼀顶点位置E cost; //边上的权值Edge *link; //下⼀条边链指针

};

2.2.2顶点类的定义template //顶点的定义struct Vertex{

T data; //顶点的名字Edge *adj; //边链表的头指针};

2.2.3图类的定义template

class Graph //图的类定义{

protected:

int maxVertices;//图中最⼤的顶点数int numEdges; //当前边数int numVertices; //当前顶点数T *output; //存放遍历的数组T *input; //存放输⼊数组

Vertex *NodeTable;//顶点表(各边链表的头结点)

int getVertexPos (const T vertx)// 取顶点v在数组中的位置{int j=-1;for(int i=0;i{

if(NodeTable[i].data==vertx)j=i;}return j;}

void DFS(Graph& G, int v, bool visited[]) //图的深度优先搜索{cout<

visited[v] = true; //作访问标记

int w = G.getFirstNeighbor (v); //第⼀个邻接顶点while (w != -1)//若邻接顶点w存在

{

if ( !visited[w] )

DFS(G, w, visited); //若w未访问过, 递归访问顶点ww = G.getNextNeighbor (v, w); //下⼀个邻接顶点}}public:

Graph (); //构造函数~Graph(); //析构函数

T getValue (int i) //取顶点i 的值{

return (i>=0 && i}

bool insertVertex(const T &vertex); //插⼊顶点vertex

bool insertEdge (int v1, int v2, E cost); //插⼊边(v1, v2),权值为costbool removeVertex(int v); //删除指定的顶点bool removeEdge(int v1,int v2); //删除⼀条边

int getFirstNeighbor (int v);//取顶点v 的第⼀个邻接顶点

int getNextNeighbor (int v, int w); //取v 的邻接顶点w 的下⼀邻接顶点int getFirstCost (int v);//取顶点v 的第⼀个邻接顶点的cost值

int getNextCost (int v, int w); //取v 的邻接顶点w 的下⼀邻接顶点的cost值void DFS(Graph& G,const T& v);//从顶点v出发对图G进⾏深度优先遍历的主过程int BFS(Graph& G, const T& v); //图的⼴度优先搜索void WheCan(Graph& G);//判断是否为连通图void OutPut();//输出

void HaveEdge(Graph& G);//求顶点的度

void SerachVertex(Graph& G);//输⼊顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历void ChangeGraph(Graph& G); //将⽤邻接表表⽰的数转换为邻接矩阵表⽰void Input();//输⼊};

3详细设计和实现3.1算法流程图

程序主要设计了六个功能：⾸先是求每个顶点的度，然后可以选择对图G作DFS （或BFS ）搜索，接着可以判断此图是否连通，接着可以将图G 转换为临街矩阵存储⽅式退出，最后可以对图G 作查找顶点。

主函数流程如下：

图3.1.1主函数流程图 3.2 各个要求的实现⽅法

3.2.1⾃选存储结构,输⼊含n 个顶点（⽤字符表⽰顶点）和e 条边的图G

采⽤邻接表的存储结构Y

N个顶点的输⼊存储到顶点节点链表（Vertex ）中

如果第n个节点和第m个节点之间含有⼀条边e，就将n和m的顶点链表中指向的边链表中存储⼊n和m在顶点表中的下标和权值3.2.2求每个顶点的度,输出结果顶点的度指与该顶点相关联的边的条数

在⽤邻接链表做为图的存储⽅式中，要求⼀个顶点n的度只要去搜索存放顶点n的边节点链表，其中存放了多少条边的信息，这个顶点的度就为多少。

3.2.3指定任意顶点x为初始顶点,对图G作DFS遍历,输出DFS顶点序列

DFS遍历指的是深度优先搜索深度优先搜索的基本思想：

DFS 在访问图中某⼀起始顶点v 后, 由v 出发, 访问它的任⼀邻接顶点w1; 再从w1 出发, 访问与w1邻接但还没有访问过的顶点w2; 然后再从w2 出发, 进⾏类似的访问, …如此进⾏下去, 直⾄到达所有的邻接顶点都被访问过的顶点u 为⽌。接着, 退回⼀步,退到前⼀次刚访问过的顶点, 看是否还有其它没有被访问的邻接顶点。如果有, 则访问此顶点, 之后再从此顶点出发, 进⾏与前述类似的访问; 如果没有, 就再退回⼀步进⾏搜索。重复上述过程, 直到连通图中所有顶点都被访问过为⽌。3.2.4指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶点序列

BFS指的是⼴度优先搜索BFS基本思想：

BFS在访问了起始顶点v 之后, 由v 出发, 依次访问v 的各个未被访问过的邻接顶点w1, w2, …, wt, 然后再顺序访问w1, w2, …, wt的所有还未被访问过的邻接顶点。

再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，…如此做下去，直到图中所有顶点都被访问到为⽌。

⼴度优先搜索是⼀种分层的搜索过程, 每向前⾛⼀步可能访问⼀批顶点, 不像深度优先搜索那样有往回退的情况。因此, ⼴度优先搜索不是⼀个递归的过程。

3.2.5输⼊顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历(执⾏操作3)；否则输出信息“⽆x”；

输⼊顶点，在顶点表中所搜是否含有这个顶点，如果没有，就输出“⽆x”。如果含有，搜索存放顶点n的边节点链表，找出其中存放的顶点m，然后将这个顶点m链表中的存放n的那个节点删除，同时将n中存放m的节点删除。然后在顶点链表中存放顶点n 的节点删除。

3.2.6判断图G是否是连通图，输出信息“YES”/“NO”；

对图做BFS遍历，如果遍历到的顶点数等于当前的顶点数的个数，这个图就是联通图，反之就不是连通图3.2.7如果选⽤的存储结构是邻接矩阵,则⽤邻接矩阵的信息⽣成图G

的邻接表,即复制图G,然再执⾏操作(2)；反之亦然

我采⽤的是邻接矩阵做为图的存储结构。将⽤邻接表存储的图转化为邻接矩阵的存储的基本思想是：（1）将图的顶点表中存放的顶点的信息都存放在⼀个顶点矩阵中

（2）逐个搜索各个顶点的边节点链表，如果含有节点，将邻接矩阵中对应⼆维数组的值赋值为cost的值。顶点的度为：统计第i ⾏(列) 不为0 的个数可得顶点i 的度。3.3主程序设计

///////////////////////////////////////////////////Graph.h#include#include

#include\"Queue.h\"using namespace std;template

struct Edge //边结点的定义{

int dest; //边的另⼀顶点位置E cost; //边上的权值Edge *link; //下⼀条边链指针Edge(){} //构造函数

Edge(int num,E cost):dest(num),weight(cost),link(NULL){} //构造函数bool operator!=(Edge& R) const //判边等否{

return dest != R.dest;}};

template //顶点的定义struct Vertex{

T data; //顶点的名字Edge *adj; //边链表的头指针};template

class Graph //图的类定义{

protected:

int maxVertices;//图中最⼤的顶点数int numEdges; //当前边数

int numVertices; //当前顶点数T *output; //存放遍历的数组T *input; //存放输⼊数组

Vertex *NodeTable;//顶点表(各边链表的头结点)

int getVertexPos (const T vertx)// 取顶点v在数组中的位置{int j=-1;for(int i=0;i{

if(NodeTable[i].data==vertx)j=i;}return j;}

void DFS(Graph& G, int v, bool visited[]) //图的深度优先搜索{cout<

visited[v] = true; //作访问标记

int w = G.getFirstNeighbor (v); //第⼀个邻接顶点while (w != -1)//若邻接顶点w存在{

if ( !visited[w] )

DFS(G, w, visited); //若w未访问过, 递归访问顶点ww = G.getNextNeighbor (v, w); //下⼀个邻接顶点}}public:

Graph (); //构造函数~Graph(); //析构函数

T getValue (int i) //取顶点i 的值{

return (i>=0 && i}

bool insertVertex(const T &vertex); //插⼊顶点vertex

bool insertEdge (int v1, int v2, E cost); //插⼊边(v1, v2),权值为costbool removeVertex(int v); //删除指定的顶点

bool removeEdge(int v1,int v2); //删除⼀条边

int getFirstNeighbor (int v);//取顶点v 的第⼀个邻接顶点

int getNextNeighbor (int v, int w); //取v 的邻接顶点w 的下⼀邻接顶点int getFirstCost (int v);//取顶点v 的第⼀个邻接顶点的cost值

int getNextCost (int v, int w); //取v 的邻接顶点w 的下⼀邻接顶点的cost 值void DFS(Graph& G,const T& v);//从顶点v出发对图G进⾏深度优先遍历的主过程int BFS(Graph& G, const T& v); //图的⼴度优先搜索void WheCan(Graph& G);//判断是否为连通图void OutPut();//输出

void HaveEdge(Graph& G);//求顶点的度

void SerachVertex(Graph& G);//输⼊顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历void ChangeGraph(Graph& G); //将⽤邻接表表⽰的数转换为邻接矩阵表⽰void Input();//输⼊};#includetemplate

Graph::Graph() //构造函数：建⽴⼀个空的邻接表{

maxVertices=100;numVertices=0;numEdges=0;

NodeTable = new Vertex[maxVertices]; //创建顶点表数组if (NodeTable == NULL){

cerr<<\"存储分配错!\"for (int i=0;i{

NodeTable[i].adj = NULL;}

output=new T[maxVertices];}template

Graph::~Graph()//析构函数：删除⼀个邻接表

{

for (int i=0;i{

Edge *p = NodeTable[i].adj;while (p != NULL){

NodeTable[i].adj = p->link;delete p;

p = NodeTable[i].adj;}}

delete[]NodeTable; //删除顶点表数组}template

bool Graph::insertVertex(const T &vertex) //插⼊顶点{

if(numVertices==maxVertices)return false;

NodeTable[numVertices].data=vertex;numVertices++;return true;}template

bool Graph::insertEdge (int v1, int v2, E cost)//插⼊边(v1, v2),权值为cost {if(v1>=0&&v1<=numVertices&&v2>=0&&v2<=numVertices){

Edge*q, *p=NodeTable[v1].adj; //v1对应的边链表头z指针while(p!=NULL&&p->dest!=v2) //寻找邻接顶点v2p=p->link;

if(p!=NULL) //找到此边不插⼊return false;

p=new Edge; //否则创建新节点q=new Edge;p->dest=v2;p->cost=cost;

p->link=NodeTable[v1].adj;//链⼊v1的边链表NodeTable[v1].adj=p;q->dest=v1;q->cost=cost;

q->link=NodeTable[v2].adj;//链⼊v2的边链表NodeTable[v2].adj=q;numEdges++;return true;}else{

cerr<<\"参数有误!请重新输⼊!\"bool Graph::removeVertex(int v){

if(numVertices==1||v<0||v>=numVertices){

cerr<<\"参数有误，请重新输⼊！\"return false; //表空或顶点超出范围}Edge *p,*s,*t;int k;

while(NodeTable[v].adj!=NULL){

p=NodeTable[v].adj;k=p->dest;

s=NodeTable[k].adj;t=NULL;

while(s!=NULL&&s->dest!=v){t=s;

s=s->link;}

if(s!=NULL){

if(t==NULL)

NodeTable[k].adj=s->link;else

t->link=s->link;delete s;}

NodeTable[v].adj=p->link;delete p;numEdges--;}

numVertices--;

NodeTable[v].data=NodeTable[numVertices].data;p=NodeTable[v].adj=NodeTable[numVertices].adj;while(p!=NULL){

s=NodeTable[p->dest].adj;while(s!=NULL)

if(s->dest==numVertices){

s->dest=v;break;}elses=s->link;}

return true;}template

bool Graph::removeEdge(int v1,int v2){

if(v1!=-1&&v2!=-1)

{

Edge *p=NodeTable[v1].adj,*q=NULL,*s=p;while(p!=NULL&&p->dest!=v2){q=p;p=p->link;}

if(p!=NULL){if(p==s)

NodeTable[v1].adj=p->link;else

q->link=p->link;delete p;}elsereturn false;

p=NodeTable[v2].adj;q=NULL;s=p;

while(p->dest!=v1){q=p;p=p->link;}if(p==s)

NodeTable[v2].adj=p->link;else

q->link=p->link;delete p;return true;}

return false;}template

int Graph::getFirstNeighbor (int v)//给出顶点位置为v 的第⼀个邻接顶点的位置,如果找不到, 则函数返回-1{if (v!=-1){ //顶点v存在

Edge *p=NodeTable[v].adj; //对应边链表第⼀个边结点if (p!=NULL) //存在, 返回第⼀个邻接顶点return p->dest;}

return -1; //第⼀个邻接顶点不存在}template

int Graph::getNextNeighbor (int v, int w) //给出顶点v的邻接顶点w的下⼀个邻接顶点的位置,若没有下⼀个邻接顶点, 则函数返回-1{if(v!=-1){ //顶点v存在

Edge *p = NodeTable[v].adj;while (p!=NULL && p->dest!=w)p = p->link;

if (p!=NULL && p->link!=NULL) //返回下⼀个邻接顶点return p->link->dest;}

return -1; //下⼀邻接顶点不存在}template

int Graph::getFirstCost (int v)//给出顶点位置为v 的第⼀个邻接顶点的位置,如果找不到, 则函数返回-1{if (v!=-1){ //顶点v存在

Edge *p=NodeTable[v].adj; //对应边链表第⼀个边结点的cost值if (p!=NULL) //存在, 返回第⼀个邻接顶点return p->cost;}

return -1; //第⼀个邻接顶点不存在}template

int Graph::getNextCost(int v, int w) //给出顶点v的邻接顶点w的下⼀个邻接顶点的位置,若没有下⼀个邻接顶点, 则函数返回-1{if(v !=-1){ //顶点v存在

Edge *p = NodeTable[v].adj;while (p!=NULL && p->dest!=w)p = p->link;

if (p!=NULL && p->link!=NULL) //返回下⼀个邻接顶点的cost值return p->link->cost;}

return -1; //下⼀邻接顶点不存在//下⼀邻接顶点不存在}template

void Graph::DFS(Graph& G,const T& v){

int i, loc, n = numVertices; //顶点个数bool *visited = new bool[n]; //创建辅助数组for (i = 0; i < n; i++) //辅助数组visited初始化visited [i] = false;loc=v;

DFS(G, loc, visited); //从顶点0开始深度优先搜索delete [] visited;}template

int Graph::BFS (Graph& G, const T& v){

int i, w, n=numVertices,m=0; //图中顶点个数bool *visited = new bool[n];for (i=0;ivisited[i]=false;int loc=v; //取顶点号

output[m]=G.getValue(loc); //访问顶点vvisited[loc]=true; //做已访问标记Queue Q(20);

Q.EnQueue (loc); //顶点进队列

while (!Q.IsEmpty()) //循环, 访问所有结点{

Q.DeQueue (loc);

w=G.getFirstNeighbor(loc); //第⼀个邻接顶点while(w!=-1) //若邻接顶点w存在{

if (!visited[w]) //若未访问过{

output[++m]=G.getValue(w); //访问visited[w]=true;

Q.EnQueue(w); //顶点w进队列}

w=G.getNextNeighbor(loc,w); //找顶点loc 的下⼀个邻接顶点}

} //外层循环，判队列空否delete [] visited;return m;}template

void Graph::WheCan(Graph& G) //判断是否为连通图{int x=0;x=BFS(G,0);if(x==numVertices)cout<<\"YES\"cout<<\"NO\"<}template

void Graph::OutPut(){

for(int i=0;icouttemplate //得到每个顶点的度void Graph::HaveEdge(Graph& G)

{

for(int i=0;i{int n=0;

int m=getFirstNeighbor(i);if(m!=-1)n++;

int a=getNextNeighbor(i,m);if(a!=-1){do{n++;

a=getNextNeighbor(i,a);}

while(a=!-1);}

cout<<\"顶点\"<}}template

void Graph:: SerachVertex(Graph& G)//输⼊顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历{T ver;

T *n=new T[numVertices];int i,m=0;int a;

cout<<\"请输⼊要查询的定点的数值!!\">ver;

i=getVertexPos(ver);if(i==-1)

cout<<\"你要查找的顶点不存在\"n[m]=getFirstNeighbor(i);

a=n[m];m++;

if(getNextNeighbor(i,n[m])!=-1){

n[m]=getNextNeighbor(i,a);a=n[m];m++;}

for(int j=0;jremoveEdge(i,n[j]);cout<<\"删除\"void Graph::ChangeGraph(Graph& G){int i,j,m;

T *VerticesList=new T[numVertices]; //顶点表for(i=0;i

VerticesList[i]=getValue(i);

E **Edge=(E**)new E*[numVertices]; //邻接矩阵for(i=0;i

Edge[i]=new E[numVertices];for(i=0;ifor(j=0;jEdge[i][j]=0;for(i=0;i{

int m=getFirstNeighbor(i);if(m!=-1)

Edge[i][m]=Edge[m][i]=getFirstCost(i);int a=getNextNeighbor(i,m);if(a!=-1){

Edge[i][a]=Edge[a][i]=getNextCost(i,m);a=getNextNeighbor(i,a);}}

cout<<\"邻接矩阵为：\"for(int j=0;jcoutif(Edge[i][j]!=0)m++;}

cout<<\"顶点\"<}}template

void Graph::Input(){int i,j;

int numv,nume;input=new T[100];int a,b,c;

cout<<\"请输⼊顶点总数和边的总数！！\">numv>>nume;