图的邻接表表示的各种算法

  • R2_570219
    了解作者
  • 2.4KB
    文件大小
  • 7z
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-06-03 06:50
    上传日期
图的邻接表表示的克鲁斯卡尔算法 迪杰斯特拉算法 普里姆算法 c++实现 codeblocks编译通过
图的邻接表表示.7z
  • 邻接表表示的迪杰斯特拉算法.cpp
    5.3KB
  • 邻接表表示的普里姆算法.cpp
    4.7KB
  • 邻接表的克鲁斯卡尔算法.cpp
    4.7KB
内容介绍
#include<iostream> #include<queue> using namespace std; #define MaxVertexNum 100 #define TRUE 1 #define FALSE 0 #define INT_MAX 9999 //边 typedef struct ArcNod{ int adjvex; int num; struct ArcNod *next; }ArcNod; //顶点 typedef struct VNode { char data; ArcNod *firstarc; }VNode,AdjList[MaxVertexNum]; //顶点数组 typedef struct{ AdjList vertices; int vexnum,arcnum; }ALGraph; int visite[MaxVertexNum]; //无向图的邻接表创建 void CreatGraphAL(ALGraph *T) { int i,j,k,n; ArcNod *s; cout<<"请输入顶点数和边数"<<endl; cin>>T->vexnum>>T->arcnum; cout<<"请输入顶点的信息"<<endl; for(i = 0;i < T->vexnum;i++) { cin>>T->vertices[i].data; T->vertices[i].firstarc = NULL; } cout<<"请输入边的信息(输入格式为 i j n),每条边用回车结束,用升序输入"<<endl; for(k = 0;k < T->arcnum;k++) { cin>>i>>j>>n; s = new ArcNod; s->adjvex = j; s->num = n; s->next = T->vertices[i].firstarc; T->vertices[i].firstarc = s; } } //打印邻接表 void printfGraphAL(ALGraph T) { int i; cout<<"邻接表为:"<<endl; for(i = 0;i < T.vexnum;i++) { cout<<T.vertices[i].data<<"-"; ArcNod *p = T.vertices[i].firstarc; while(p) { if(p->next) cout<<p->adjvex<<"-"; else cout<<p->adjvex; p = p->next; } cout<<endl; } } void DFS(ALGraph T,int i)//深度优先遍历 { ArcNod *p; cout<<T.vertices[i].data<<" "; visite[i] = TRUE; p = T.vertices[i].firstarc; while(p) { if(visite[p->adjvex] == FALSE) DFS(T,p->adjvex); p = p->next; } } void DFSTraver(ALGraph T) { int i; for(i = 0;i < T.vexnum;i++) visite[i] = FALSE; for(i = 0;i < T.vexnum;i++) if(visite[i] == FALSE && T.vertices[i].firstarc != NULL) DFS(T,i); } void Find(ALGraph T) { int i,k = 0; for(i = 0;i < T.vexnum;i++) visite[i] = FALSE; for(i = 0;i < T.vexnum;i++) if(visite[i] == FALSE && T.vertices[i].firstarc != NULL) { k++; cout<<"第"<<k<<"个连通子图为:"; DFS(T,i); cout<<endl; } } void BFS(ALGraph T,int k)//广度优先遍历 { queue<int> q; int i; ArcNod *p; cout<<T.vertices[k].data<<" "; visite[k] = TRUE; q.push(k); while(!q.empty()) { i = q.front(); q.pop(); p = T.vertices[i].firstarc; while(p) { if(visite[p->adjvex] == FALSE) { cout<<T.vertices[p->adjvex].data<<" "; visite[p->adjvex] = TRUE; q.push(p->adjvex); } p = p->next; } } } void BFSTraver(ALGraph T) { int i; for(i = 0;i < T.vexnum;i++) visite[i] = FALSE; for(i = 0;i < T.vexnum;i++) if(visite[i] == FALSE && T.vertices[i].firstarc != NULL) BFS(T,i); } int ShortestPath(ALGraph T,int P[][100],int D[])//求最短路径,路径储存在P数组中,D数组储存最短路径长度 { int v,vnum; vnum = T.vexnum; bool Final[vnum];//Final数组表示该结点是否已经被使用 for(v = 1; v < vnum; v++)//赋初始值 Final[v] = false; ArcNod *p; p = T.vertices[0].firstarc; while(p) { D[p->adjvex] = p->num;//与0结点有直接路径的 P[p->adjvex][0] = 1; P[p->adjvex][p->adjvex] = 1; p = p->next; } Final[0] = 1; D[0] = 0; for(int i = 1; i < T.vexnum; i++)//求剩下的结点 { int min = INT_MAX; for(int w = 1;w < T.vexnum; w++)//找到当前最短的一条路 { if(!Final[w] && D[w] < min) { min = D[w]; v = w; } } Final[v] = true; p = T.vertices[v].firstarc; while(p) { if(!Final[p->adjvex] && (min + p->num) < D[p->adjvex])//找到这个结点所连接的边,当前值加边权值是否比所连接的点的D值小 { D[p->adjvex] = min + p->num;//小的话替换掉 for(int j = 0; j < T.vexnum; j++) { P[p->adjvex][j] = P[v][j]; } P[p->adjvex][p->adjvex] = 1;//到达w所经过的路径是到达v所经过的路径加w } p = p->next; } } } int main() { ALGraph T; CreatGraphAL(&T); int vnum = T.vexnum; int P[vnum][100],D[vnum]; ShortestPath(T,P,D); printfGraphAL(T); cout<<"深度优先遍历结果为"<<endl; DFSTraver(T); cout<<endl; cout<<"广度优先遍历结果为"<<endl; BFSTraver(T); cout<<endl; cout<<"此图的连通子图为: "<<endl; Find(T); for(int i = 1; i < T.vexnum ; i++) { if(D[i] > 900) { cout<<"0结点不可达"<<i<<"结点"<<endl; } else { cout<<"0结点到第"<<i<<"结点的最短路径为"<<D[i]<<endl; cout<<"最短路径为"<<endl; for(int j = 0; j < T.vexnum ;j++) { if(P[i][j] == 1) cout<<j<<" "; } cout<<endl; } } }
评论
    相关推荐
    • sift 算法 C++
      经典的sift算法,可以用于特征提取和配准,小伙伴们加油!!!
    • DES算法C++实现
      DES算法C++实现 DES算法C++实现 DES算法C++实现 DES算法C++实现
    • RSA加密算法C++
      RSA加密算法C++,密码学课上编的,128位,cmd运行
    • DES算法C++实现
      DES算法C++实现DES算法C++实现DES算法C++实现DES算法C++实现
    • AES算法C++实现
      AES算法C++实现AES算法C++实现AES算法C++实现AES算法C++实现
    • 分水岭算法c++代码
      分水岭算法C++完整代码 标记分水岭算法完整代码加解析
    • EM算法C++实现
      EM算法C++实现 EM算法C++实现 EM算法C++实现 EM算法C++实现 EM算法C++实现 EM算法C++实现 EM算法C++实现 EM算法C++实现
    • floyd算法c++
      floyd算法C++代码,可解决最小路径问题
    • 汉诺塔算法 C++
      汉诺塔算法 C++ 有截图 结果如下: 请输入盘子数:4 各步骤如下: A-->B A-->C B-->C A-->B C-->A C-->B A-->B A-->C B-->C B-->A C-->A B-->C A-->B A-->C B-->C 总步骤数为:15 Press any key to continue
    • KLT算法c++实现
      KLT算法C++实现,与大家分享 KLT An implementation of the Kanade-Lucas-Tomasi feature tracker