第七天--------图的基本操作附源码

电玩女神 2022-05-21 09:54 139阅读 0赞

**一、 目的**

1．掌握图的存储思想及其存储实现。

2．掌握图的深度、广度优先遍历算法思想及其程序实现。

**二、内容**

1、内容

a)      键盘输入数据，分别建立一个有向图和一个无向图的邻接表。

b)      输出该邻接表。

c)      在有向图的邻接表的基础上计算各顶点的度，并输出。

d)      采用邻接表存储实现无向图的深度优先遍历。

e)      采用邻接表存储实现无向图的广度优先遍历。

f)       在主函数中设计一个简单的菜单，分别调试上述算法。

g)      \*综合训练

地下迷宫探索：假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点？

输入格式：

输入第一行给出三个正整数，分别表示地下迷宫的节点数N（1<N≤1000，表示通道所有交叉点和端点）、边数M（M≤3000，表示通道数）和探索起始节点编号S（节点从1到N编号）。随后的M行对应M条边（通道），每行给出一对正整数，分别是该条边直接连通的两个节点的编号。

输出格式：

若可以点亮所有节点的灯，则输出从S开始并以S结束的包含所有节点的序列，序列中相邻的节点一定有边（通道）；否则虽然不能点亮所有节点的灯，但还是输出点亮部分灯的节点序列，最后输出0，此时表示迷宫不是连通图。

由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以节点小编号优先的次序访问（点灯）。在点亮所有可以点亮的灯后，以原路返回的方式回到起点。

输入样例：

6 8 1

1 2

2 3

3 4

4 5

5 6

6 4

3 6

1 5

输出样例：

1 2 3 4 5 6 5 4 3 2 1

2、主要数据类型与变量

a)      1．类型定义（邻接表存储）

b)              \#define MAX\_VERTEX\_NUM 20  //顶点最大个数

c)              typedef struct ArcNode\{

d)                 int            adjvex;

e)                 struct ArcNode \*nextarc;

f)                  int            weight;  //边的权值

g)              \}ArcNode;  //表结点

g)        \#define VertexType int  //顶点元素类型

h)              typedef struct VNode\{

i)                   VertexType data;

j)                   ArcNode \*firstarc;

k)              \}VNode,AdjList\[MAX\_VERTEX\_NUM\]; //

l)                typedefstruct\{

m)      AdjListvertices;

n)                int vexnum, arcnum; //顶点的实际数，边的实际数

o)                int kind;

p)             \}ALGraph;

q)      2．上述类型定义可以根据实际情况适当调整。

r)       3．算法4、5分别利用栈、队列实现非递归算法。

3、算法思想描述

**三、系统测试**

1、测试方案

**通过输入图的定点数和边数，来确定出整个图的大致变化，当然是自己现在草稿纸上画出这个图，然后写出答案。在执行程序，看看程序的答案与自己的答案是否相同。**

**附：程序源代码**

**ALGraph.cpp**

\#include "ALGraph.h"

int visited\[N\];

/\*创建一个无向图的邻接表\*/

int CreateUDG(ALGraph &G)

int m, n, k;

char v1, v2;

printf("请输入图G的顶点数和边数：");

scanf("%d %d", &G.vexnum, &G.arcnum);

printf("请输入%d个顶点名字(以空格区分)：", G.vexnum);

for(m = 0; m < G.vexnum; m++)

scanf(" %c", &G.vertices\[m\].data);  /\*请注意输入格式\*/

G.vertices\[m\].firstarc = NULL; /\*邻接表初始化为空\*/

for(k = 1; k <= G.arcnum; k++)

printf("请输入第%d条边的两个顶点(以字符表示，字符间以空格区分)：", k);

scanf(" %c %c", &v1, &v2);  /\*请注意输入格式\*/

m = LocateVex(G, v1);

n = LocateVex(G, v2);

InsertList(G, m, n,0);   /\*生成各自的邻接表\*/

InsertList(G, n, m,0);

return OK;

/\*请写出有向图的邻接表的生成函数\*/

int CreateDG(ALGraph &G)

int m, n, k;

char v1, v2;

printf("请输入图G的顶点数和边数：");

scanf("%d %d", &G.vexnum, &G.arcnum);

printf("请输入%d个顶点名字(以空格区分)：", G.vexnum);

for(m = 0; m < G.vexnum; m++)

scanf(" %c", &G.vertices\[m\].data);  /\*请注意输入格式\*/

G.vertices\[m\].firstarc = NULL; /\*邻接表初始化为空\*/

for(k = 1; k <= G.arcnum; k++)

printf("请输入第%d条边的两个顶点(以字符表示，字符间以空格区分,第一个为尾，第二个为头)：", k);

scanf(" %c %c", &v1, &v2);  /\*请注意输入格式\*/

m = LocateVex(G, v1);       /\*确定v1和v2的下标\*/

n = LocateVex(G, v2);

InsertList(G, m, n,0);   /\*生成各自的邻接表\*/

return OK;

/\*请写出无向带权图的邻接表的生成函数\*/

int CreateUDN(ALGraph &G)

int m, n, k,w;

char v1, v2;

printf("请输入图G的顶点数和边数：");

scanf("%d %d", &G.vexnum, &G.arcnum);

printf("请输入%d个顶点名字(以空格区分)：", G.vexnum);

for(m = 0; m < G.vexnum; m++)

scanf(" %c", &G.vertices\[m\].data);  /\*请注意输入格式\*/

G.vertices\[m\].firstarc = NULL; /\*邻接表初始化为空\*/

for(k = 1; k <= G.arcnum; k++)

printf("请输入第%d条边的两个顶点和权值(以字符表示，字符间以空格区分)：", k);

scanf(" %c %c %d", &v1, &v2, &w);  /\*请注意输入格式\*/

m = LocateVex(G, v1);       /\*确定v1和v2的下标\*/

n = LocateVex(G, v2);

InsertList(G, m, n,w);   /\*生成各自的邻接表\*/

InsertList(G, n, m,w);

return OK;

/\*请写出有向带权图的邻接表的生成函数\*/

int CreateDN(ALGraph &G)

intm, n, k,w;

char v1, v2;

printf("请输入图G的顶点数和边数：");

scanf("%d %d", &G.vexnum, &G.arcnum);

printf("请输入%d个顶点名字(以空格区分)：", G.vexnum);

for(m = 0; m < G.vexnum; m++)

scanf(" %c", &G.vertices\[m\].data);  /\*请注意输入格式\*/

G.vertices\[m\].firstarc = NULL; /\*邻接表初始化为空\*/

for(k = 1; k <= G.arcnum; k++)

printf("请输入第%d条边的两个顶点和权值(以字符表示，字符间以空格区分,第一个为尾，第二个为头)：", k);

scanf(" %c %c %d", &v1, &v2, &w);  /\*请注意输入格式\*/

m = LocateVex(G, v1);       /\*确定v1和v2的下标\*/

n = LocateVex(G, v2);

InsertList(G, m, n, w);   /\*生成各自的邻接表\*/

return OK;

/\*查找顶点v在邻接表存储法中的下标\*/

int LocateVex(ALGraph G, char v)

int m;

for(m = 0; m < G.vexnum; m++)

if(G.vertices\[m\].data == v)

return m;

return ERROR;

/\*在邻接表中插入顶点v的邻接点w\*/

int InsertList(ALGraph &G, int m, intn,int w)

\{    // 给新加入的节点分配内存；

ArcNode \*p;

p = (ArcNode\*)malloc(sizeof(ArcNode));

p->adjvex = n;

p->weight = w;

p->nextarc = G.vertices\[m\].firstarc;

G.vertices\[m\].firstarc = p;

return OK;

/\*遍历顶点v的邻接表\*/

void TraverseList(ALGraph G, int v)

ArcNode \*p;

int m;

p= G.vertices\[v\].firstarc;

while(p)

m = p->adjvex;

printf("%c ", G.vertices\[m\].data);

p = p->nextarc;

/\*计算顶点v的邻接表长度\*/

int LengthList(ALGraph G, int v)

ArcNode \*p;

int m = 0;

if(G.vertices\[v\].firstarc == NULL)\{

return 0;

p= G.vertices\[v\].firstarc; m++;

while(p->nextarc != NULL)\{

m++;

p = p->nextarc;

return m;

/\*深度优先遍历\*/

void DFSTraverse(ALGraph G)

int m;

for(m = 0; m < G.vexnum; m++)

visited\[m\] = FALSE;

for(m = 0; m < G.vexnum; m++)

if(!visited\[m\])  DFS(G, m);

printf("\\n");

void DFS(ALGraph G, int v)

int w;

visited\[v\] = TRUE; /\*访问顶点v， 并置访问标志数组相应分量值\*/

printf("%c ", G.vertices\[v\].data);

for(w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))

if(!visited\[w\])  DFS(G, w);   /\*递归调用DFS\*/

\} /\*DFS\*/

/\*在图G中查找顶点v的第一个邻接点\*/

int FirstAdjVex(ALGraph G, int v)

if(G.vertices\[v\].firstarc)

return G.vertices\[v\].firstarc->adjvex;  /\*邻接表的第一个结点信息\*/

else

return ERROR;

/\*在图G中查找顶点v的邻接点w之后的下一个邻接点\*/

int NextAdjVex(ALGraph G, int v, int w)

ArcNode \*p;

int m;

p = G.vertices\[v\].firstarc;

while(p)\{

if(p->nextarc == NULL) return ERROR;

m = p->adjvex;

if(m == w)\{

w = p->nextarc->adjvex;

break;

p = p->nextarc;

return w;

void BFSTraverse(ALGraph G)

int m;

for(m = 0; m < G.vexnum; m++)

visited\[m\] = FALSE;

for(m = 0; m < G.vexnum; m++)

if(!visited\[m\])  BFS(G, m);

printf("\\n");

\} //BFSTraverse

void BFS(ALGraph G, int v)\{

QElemType e;

ArcNode \*p;

LinkQueue q;

InitQueue(q);

EnQueue(q,v);

visited\[v\] = TRUE;

while(!QueueEmpty(q))\{

DeQueue(q,e); printf("%c ",G.vertices\[e\].data);

p = G.vertices\[e\].firstarc;

while(p)\{

if(!visited\[p->adjvex\])\{

EnQueue(q,p->adjvex); visited\[p->adjvex\] = TRUE;

p = p->nextarc;

/\*计算有向图中各顶点的度\*/

void CountNum(ALGraph G, int \*ID)

ArcNode \*p;

int r\[G.vexnum\],c\[G.vexnum\];//c为出度，r为入度。

for(int m=0;m<G.vexnum;m++)\{

c\[m\] = LengthList(G,m);

for(int m=0;m<G.vexnum;m++)\{

r\[m\] = 0;

for(int m=0;m<G.vexnum;m++)\{

p = G.vertices\[m\].firstarc;

while(p)\{

r\[p->adjvex\]++;

p = p->nextarc;

for(int m=0;m<G.vexnum;m++)\{

ID\[m\] = c\[m\]+r\[m\];

**ALGraph.h**

\#include "DS.h"

\#include "LinkQueue.h"

\#ifndef ALGRAPH\_H\_INCLUDED

\#define ALGRAPH\_H\_INCLUDED

\#define N  10

typedef char  VertexType;

typedef struct ArcNode

int   adjvex;

int weight;

struct ArcNode  \*nextarc;

\}ArcNode;

typedef struct  VNode

VertexType   data;

ArcNode     \*firstarc;

\}VNode,AdjList\[N\];

typedef struct

AdjList   vertices;

int      vexnum, arcnum;

\}ALGraph;

\#endif // ALGRAPH\_H\_INCLUDED

int CreateUDG(ALGraph &G);

int CreateDG(ALGraph &G);

int CreateUDN(ALGraph &G);

int CreateDN(ALGraph &G);

int LocateVex(ALGraph G, char v);

int InsertList(ALGraph &G, int i, intj,int w);

void TraverseList(ALGraph G, int v);

int LengthList(ALGraph G, int v);

int FirstAdjVex(ALGraph G, int v);

int NextAdjVex(ALGraph G, int v, int w);

void DFSTraverse(ALGraph G);

void DFS(ALGraph G, int v);

void BFSTraverse(ALGraph G);

void BFS(ALGraph G, int v);

void CountNum(ALGraph G, int \*ID);

**main.cpp**

\#include "ALGraph.h"

int main()

ALGraph G;

int i;

//创建无向图

CreateUDG(G);

int Num\[G.vexnum\];

printf("无向图的邻接表为：\\n");

for(i = 0; i < G.vexnum; i++)

printf("%c  ——>  ", G.vertices\[i\].data);

TraverseList(G, i);

printf("\\n");

printf("DFS序列：");

DFS(G,0);

printf("\\n");

DFSTraverse(G);

printf("BFS序列：");

BFSTraverse(G);

printf("图中各顶点的度为：\\n");

CountNum(G, Num);

for(i = 0;i<G.vexnum;i++)\{

printf("图中%d点的度为:%d\\n",i+1,Num\[i\]);

return 0;

发表评论取消回复

表情：

评论列表（有 0 条评论，139人围观）

第七天--------图的基本操作附源码

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关七天带你入门Mybatis源码第四天，MappedStatement

相关七天带你入门Mybatis源码第三天，mybatis的Mapper生成

相关第八天------最小生成树附源码

相关第七天--------图的基本操作附源码

相关第六天-------哈夫曼编码附源码

相关二叉树的基本操作附源码

相关第四天-------队列的基本操作附源码

相关第一天--------顺序表的基本操作（付源码）

相关第二天-------单链表的基本操作，源码

相关第七章--图--基本概念选择题