石 家 庄 铁 道 大 学
实 验 报 告
课程名称： 信2305-3 任课教师： 刘 丹 实验日期： 2024.12.15
班 级： 信2305-3 姓 名： 徐戌 学 号： 20234316
实验项目名称：实验四
一、 实验目的
1）掌握图的邻接矩阵、邻接表存储结构表示及其创建算法
2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法；
3）掌握图的最短路径的算法。
二、 实验内容
三、 设计文档
四、 源程序
7-1 邻接表存储实现图的深度优先遍历
include
using namespace std;
define MVNum 100
typedef char OtherInfo;
int visited[MVNum]={0};//visited数组
//邻接表：顶点表、边表、邻接表
typedef struct ArcNode{
int adjvex;//下标信息
OtherInfo info;//其他信息
struct ArcNode* next;
}ArcNode;
typedef struct VNode{
char vex;//顶点信息
ArcNode* first;
}VNode,AdjList[MVNum];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
int LocateVex(ALGraph G,char v){
for(int i=0;i<G.vexnum;++i){
if(G.vertices[i].vexv)return i;
}
return -1;
}
void CreatALGraph(ALGraph &G,int &err)
{
cin>>G.vexnum>>G.arcnum;//输入的点数和边数
for(int i=0;i<G.vexnum;++i){//输入顶点信息，初始化first边表
cin>>G.vertices[i].vex;
G.vertices[i].first=NULL;
}
for(int k=0;k<G.arcnum;++k){//边表
char v1,v2;
cin>>v1>>v2;
int i,j;
i=LocateVex(G,v1);j=LocateVex(G,v2);
if(i-1||j-1)err=1;
else{
ArcNode * p1=new ArcNode;//不要忘记new
p1->adjvex=j;
p1->next=G.vertices[i].first;
G.vertices[i].first=p1;
ArcNode * p2=new ArcNode;//不要忘记new
p2->adjvex=i;
p2->next=G.vertices[j].first;
G.vertices[j].first=p2;
}
}
}
void DFS_ALGraph(ALGraph G,int adj)
{
cout<<G.vertices[adj].vex<<" ";
visited[adj]=1;
ArcNode* p=G.vertices[adj].first;
while(p!=NULL){
if(visited[p->adjvex]!=1)DFS_ALGraph(G,p->adjvex);//不要忘记还要判断visited数组
p=p->next;
}
}
int main()
{
ALGraph G;
int err=0;
char star;
CreatALGraph(G,err);
cin>>star;//输入起始点
int adj=LocateVex(G,star);
if(adj-1||err==1) cout<<"error";
else{
DFS_ALGraph(G,adj);
}
return 0;
}
7-2 迪杰斯特拉方法实现最短路径
include
include
include
using namespace std;
const int N=1010;
struct edge{
int v,w;
edge* next;
};
struct node{
int k;
edge* next;
}a[1010];
int n;
int find(int u){
for(int i=0;i<n;i++){
if(a[i].k==u){
return i;
}
}
return -1;
}
void add(int u,int v,int w){
edge* e=new edge();
e->v=v;
e->w=w;
e->next=a[u].next;
a[u].next=e;
}
int dis[N],pre[N];
bool st[N];
void dijkstra(int u){
memset(pre,-1,sizeof pre);
memset(dis,0x3f,sizeof dis);
dis[u]=0;
for(int i=0;i<n-1;i++){
int k=-1;
for(int j=0;j<n;j++){
if(st[j]0&&(k-1||dis[j]<dis[k])){
k=j;
}
}
if(dis[k]==0x3f3f3f3f){
continue;
}
st[k]=1;
for(edge* j=a[k].next;j!=NULL;j=j->next){
int v=j->v,w=j->w;
if(dis[v]>dis[k]+w){
dis[v]=dis[k]+w;
pre[v]=k;
}
}
}
}
void showRoad(int v){
if(pre[v]!=-1){
showRoad(pre[v]);
cout<<"-->"<<a[v].k;
}else{
cout<<a[v].k;
}
}
int main(){
int m;
cin>>n>>m;
for(int i=0;i<n;i++){
int k;
cin>>k;
a[i].k=k;
}
for(int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
int uu=find(u),vv=find(v);
add(uu,vv,w);
}
int u,v;
cin>>u>>v;
dijkstra(u);
showRoad(v);
return 0;
}
五、 个人体会
多个连通分量的处理在使用邻接表存储的图中，如果图包含多个连通分量，从一个节点开始的深度优先遍历（DFS）可能只能访问到该节点所在的连通分量，而无法访问到其他连通分量中的节点。解决方法: 为了确保所有节点都被访问到，需要在外层添加一个循环，遍历所有节点，对于每个未访问的节点启动一次DFS。
实验感想
通过这次实验，我深刻体会到了图的深度优先遍历算法在实际应用中的复杂性和灵性。最初，我在实现DFS时只考虑了从一个起点出发的情况，忽略了图可能包含多个连通分量的问题。这导致了一些节点未能被访问到，影响了算法的完整性和准确性。
通过引入一个外层循环来遍历所有节点，并对每个未访问的节点启动一次DFS，我成功解决了这个问题。这一改进不仅提高了算法的健壮性，也让我认识到在设计算法时需要全面考虑各种边界情况和特殊情况。
此外，这次实验还让我意识到数据结构的选择对算法性能的影响。邻接表作为一种高效的数据结构，能够很好地支持图的遍历操作，但在处理大规模图时仍需注意内存管理和优化。总的来说，这次实验不仅提升了我的编程能力，也加深了我对图算法的理解。