好资源#include <iostream>
#include <string>
#include <queue>
using namespace std;
//表结点
typedef struct ArcNode{
int adjvex;//该弧所指向的顶点的位置
ArcNode *nextarc;//指向下一条弧的指针
}ArcNode;
//头结点
typedef struct VNode{
string data;//顶点信息
ArcNode* firstarc;//第一个表结点的地址，指向第一条依附该顶点的弧的指针
}VNode, AdjList[10];
typedef struct{
AdjList vertices;
int vexnum, arcnum;//图的顶点数和弧数
}ALGraph;
int LocateVex(ALGraph G, string u)//返回顶点u在图中的位置
{
for(int i=0; i<G.vexnum; i++)
if(G.vertices[i].data==u)
return i;
return -1;
}
void CreateUDG(ALGraph &G)//构造无向图
{
string v1, v2;
int i, j, k;
cout<<"请输入顶点数和边数：";
cin>>G.vexnum>>G.arcnum;
cout<<"请输入顶点：";
for(i=0; i<G.vexnum; i++)
{
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL;
}
cout<<"请输入边：";
cout<<endl;
for(k=0; k<G.arcnum; k++)
{
cin>>v1>>v2;
i=LocateVex(G, v1);
j=LocateVex(G, v2);
//插入v1的邻接表,为了提高效率，总在表头插入结点。
ArcNode *arc=new ArcNode;
arc->adjvex=j;
arc->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=arc;
//插入v2的邻接表,为了提高效率，总在表头插入结点。
arc=new ArcNode;
arc->adjvex=i;
arc->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=arc;
}
}
void Print(ALGraph G)//打印邻接表
{
cout<<"打印邻接表如下：";
cout<<endl;
for(int i=0; i<G.vexnum; i++)//遍历每个顶点的邻接表
{
cout<<G.vertices[i].data;
ArcNode *p=G.vertices[i].firstarc;
while(p)
{
cout<<"->"<<G.vertices[p->adjvex].data;
p=p->nextarc;
}
cout<<endl;
}
}
int FirstAdjVex(ALGraph G, int v)//返回顶点v的第一个邻接点序号
{
ArcNode *p=G.vertices[v].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G, int v, int w)//返回顶点v的相对于w的下一个邻接点序号
{
ArcNode* p=G.vertices[v].firstarc;
while(p)
{
if(p->adjvex==w)
break;
p=p->nextarc;
}
if(p->adjvex!=w || !p->nextarc)//如果没找到w或者w是最后一个邻接点
return -1;
return p->nextarc->adjvex;
}
bool visited[10];
void DFS(ALGraph G, int v)
{
visited[v]=true;
cout<<G.vertices[v].data<<" ";
for(int w=FirstAdjVex(G, v); w>=0; w=NextAdjVex(G, v, w) )
if(!visited[w])
DFS(G, w);
}
void DFSTraverse(ALGraph G)//深搜
{
for(int i=0; i<G.vexnum; i++)
visited[i]=false;
for(i=0; i<G.vexnum; i++)
if(!visited[i])
DFS(G, i);
}
void BFSTraverse(ALGraph G)//广搜
{
queue<int> q;
for(int i=0; i<G.vexnum; i++)
visited[i]=false;
for(i=0; i<G.vexnum; i++)
{
if(!visited[i])
{
q.push(i);
visited[i]=true;
while(!q.empty())
{
int v=q.front();
q.pop();
cout<<G.vertices[v].data<<" ";
for(int w=FirstAdjVex(G, v); w>=0; w=NextAdjVex(G, v, w))
{
if (!visited[w])
{
q.push(w);
visited[w]=true;
}
}
}
}
}
}
void main()
{
ALGraph G;
CreateUDG(G);
Print(G);
cout<<"深搜：";
DFSTraverse(G);
cout<<endl;
cout<<"广搜：";
BFSTraverse(G);
cout<<endl;
}
在计算机科学中，图是一种数据结构，用于表示对象之间的关系，通常由顶点（或节点）和边（或连接）组成。在这个特定的程序中，我们处理的是无向图（Undirected Graph，UDG），其中边没有方向性，即任何两个顶点之间的边都可以双向通行。程序使用邻接表（Adjacency List）来存储图的信息，这是一种节省空间的图表示方法，特别是对于稀疏图（边的数量远小于顶点数量的平方）。
`ArcNode` 结构体代表图中的一条边，包含两个属性：`adjvex` 表示边所连接的相邻顶点的位置，`nextarc` 是一个指针，指向与当前边相连的下一条边。
`VNode` 结构体表示图中的一个顶点，包含一个 `data` 字符串存储顶点信息，以及一个 `firstarc` 指针，它指向该顶点的第一个邻接边。
`ALGraph` 结构体定义了一个无向图，包括一个 `AdjList` 数组（存储顶点信息）和两个整型变量 `vexnum` 和 `arcnum`，分别表示图的顶点数和边数。
`LocateVex` 函数用于查找给定顶点在图中的位置，通过遍历 `vertices` 数组找到匹配的顶点信息并返回其索引，若未找到则返回 -1。
`CreateUDG` 函数用于构建无向图，用户输入顶点数和边数，然后依次输入顶点和边。在构建过程中，对于每条边，会在两个顶点的邻接表中都添加对方，因为无向图的每条边连接两个顶点，所以两个顶点之间都是相互邻接的。
`Print` 函数用于打印邻接表，遍历每个顶点及其邻接顶点。
`FirstAdjVex` 和 `NextAdjVex` 函数分别用于获取给定顶点的第一个邻接顶点序号和相对于给定邻接顶点的下一个邻接顶点序号，用于遍历顶点的邻接列表。
`DFS`（深度优先搜索，Depth-First Search）函数实现了深度优先遍历算法，通过递归访问所有未访问过的邻接顶点。`DFSTraverse` 函数初始化 `visited` 数组并调用 `DFS` 对图进行全局深度优先遍历。
`BFSTraverse`（广度优先搜索，Breadth-First Search）函数实现了广度优先遍历算法，使用队列数据结构逐层访问所有未访问的邻接顶点。`BFSTraverse` 同样初始化 `visited` 数组，并通过队列对图进行全局广度优先遍历。
在 `main` 函数中，先创建无向图，打印邻接表，然后分别执行深度优先和广度优先遍历，输出遍历结果。
这个程序提供了图的基本操作，包括创建、打印、深度优先遍历和广度优先遍历，这些都是图论和算法学习中的核心概念，常用于解决诸如路径查找、拓扑排序等问题。
- 1
- 2
前往页