摘要:
图(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
};
2.2.2顶点类的定义
template
struct Vertex
{
T data; //顶点的名字
Edge
};
2.2.3图类的定义
template
class Graph //图的类定义
{
protected:
int maxVertices;//图中最大的顶点数
int numEdges; //当前边数
int numVertices; //当前顶点数
T *output; //存放遍历的数组
T *input; //存放输入数组
Vertex
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 { cout< visited[v] = true; //作访问标记 int w = G.getFirstNeighbor (v); //第一个邻接顶点 while (w != -1)//若邻接顶点w存在 { if ( !visited[w] ) DFS(G, w, visited); //若w未访问过, 递归访问顶点w w = 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),权值为cost bool 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 int BFS(Graph void WheCan(Graph void OutPut();//输出 void HaveEdge(Graph void SerachVertex(Graph void ChangeGraph(Graph 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 Edge(){} //构造函数 Edge(int num,E cost):dest(num),weight(cost),link(NULL){} //构造函数bool operator!=(Edge { return dest != R.dest; } }; template struct Vertex { T data; //顶点的名字 Edge }; template class Graph //图的类定义 { protected: int maxVertices;//图中最大的顶点数 int numEdges; //当前边数 int numVertices; //当前顶点数 T *output; //存放遍历的数组 T *input; //存放输入数组 Vertex 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 cout< visited[v] = true; //作访问标记 int w = G.getFirstNeighbor (v); //第一个邻接顶点 while (w != -1)//若邻接顶点w存在 { if ( !visited[w] ) DFS(G, w, visited); //若w未访问过, 递归访问顶点w w = 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),权值为cost bool 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 int BFS(Graph void WheCan(Graph void OutPut();//输出 void HaveEdge(Graph void SerachVertex(Graph void ChangeGraph(Graph void Input();//输入 }; #include template Graph { maxVertices=100; numVertices=0; numEdges=0; NodeTable = new Vertex if (NodeTable == NULL) { cerr<<"存储分配错!"< exit(1); } for (int i=0;i { NodeTable[i].adj = NULL; } output=new T[maxVertices]; } template Graph { for (int i=0;i { Edge while (p != NULL) { NodeTable[i].adj = p->link; delete p; p = NodeTable[i].adj; } } delete[]NodeTable; //删除顶点表数组 } template bool Graph { if(numVertices==maxVertices) return false; NodeTable[numVertices].data=vertex; numVertices++; return true; } template bool Graph if(v1>=0&&v1<=numVertices&&v2>=0&&v2<=numVertices) { Edge while(p!=NULL&&p->dest!=v2) //寻找邻接顶点v2 p=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<<"参数有误!请重新输入!"< exit(1); return false; } } template bool Graph { if(numVertices==1||v<0||v>=numVertices) { cerr<<"参数有误,请重新输入!"< exit(1); return false; //表空或顶点超出范围} Edge 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; } else s=s->link; } return true; } template bool Graph { if(v1!=-1&&v2!=-1) { Edge 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; } else return 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 { if (v!=-1) { //顶点v存在 Edge if (p!=NULL) //存在, 返回第一个邻接顶点 return p->dest; } return -1; //第一个邻接顶点不存在 } template int Graph { if(v!=-1) { //顶点v存在 Edge while (p!=NULL && p->dest!=w) p = p->link; if (p!=NULL && p->link!=NULL) //返回下一个邻接顶点 return p->link->dest; } return -1; //下一邻接顶点不存在 } template int Graph { if (v!=-1) { //顶点v存在 Edge if (p!=NULL) //存在, 返回第一个邻接顶点 return p->cost; } return -1; //第一个邻接顶点不存在 } template int Graph { if(v !=-1) { //顶点v存在 Edge 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 { 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 { int i, w, n=numVertices,m=0; //图中顶点个数 bool *visited = new bool[n]; for (i=0;i visited[i]=false; int loc=v; //取顶点号 output[m]=G.getValue(loc); //访问顶点v visited[loc]=true; //做已访问标记 Queue 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 { int x=0; x=BFS(G,0); if(x==numVertices) cout<<"YES!!!"< else cout<<"NO!!!"< } template void Graph { for(int i=0;i cout<