锐格与C语言|[NEFU锐格 数据结构]实验五六 图有关的操作
[NEFU锐格 数据结构]实验五六 图有关的操作 推荐阅读：[数据结构]NEFU 大二上 锐格实验参考 目录
知识点
| 题目 | 知识点 |
|---|---|
| 7043 | 无向图广度优先遍历 |
| 7039 | 有向图DFS和打印邻接表 |
| 7040 | 建图，求度数 |
| 7042 | 无向图非递归DFS |
| 7041 | 求拓扑序列 |
利用邻接表实现无向图的广度优先遍历
#include
#include
#includeusing namespace std;
const int MAXN=105;
typedef struct ArcNode{int adjvex;
struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode{int data;
ArcNode *firstarc;
}VNode,AdjList[MAXN];
typedef struct{AdjList verlist;
int vexnum,arcnum;
}Graph;
void CreateUDG(Graph &G){cin>>G.vexnum>>G.arcnum;
for(int i=1;
i<=G.vexnum;
i++){cin>>G.verlist[i].data;
//没有其他数据啊这题，data没啥意义的只是应付输入而已
G.verlist[i].firstarc=NULL;
}
for(int i=1;
i<=G.arcnum;
i++){int x,y;
cin>>x>>y;
ArcNode * p1= new ArcNode;
ArcNode * p2= new ArcNode;
p1->adjvex=y;
p1->nextarc=G.verlist[x].firstarc;
G.verlist[x].firstarc=p1;
p2->adjvex=x;
p2->nextarc=G.verlist[y].firstarc;
G.verlist[y].firstarc=p2;
}
}void BFS(Graph G){queueQ;
bool vis[MAXN];
memset(vis,0,sizeof(vis));
cout<<"v1 ";
Q.push(1);
vis[1]=true;
while(!Q.empty()){int u=Q.front();
Q.pop();
ArcNode* p=G.verlist[u].firstarc;
while(p!=NULL){if(!vis[p->adjvex]){cout<<"v"adjvex]=true;
Q.push(p->adjvex);
}
p=p->nextarc;
}
}
}int main(){Graph G;
CreateUDG(G);
BFS(G);
return 0;
}
7039
有向图DFS和打印邻接表
#include
#include
#includeusing namespace std;
const int MAXN=105;
typedef struct ArcNode{int adjvex;
struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode{int data;
ArcNode *firstarc;
}VNode,AdjList[MAXN];
typedef struct{AdjList verlist;
int vexnum,arcnum;
}Graph;
void CreateUDG(Graph &G){cin>>G.vexnum>>G.arcnum;
for(int i=1;
i<=G.vexnum;
i++){cin>>G.verlist[i].data;
G.verlist[i].firstarc=NULL;
}
for(int i=1;
i<=G.arcnum;
i++){int x,y;
cin>>x>>y;
ArcNode * p1= new ArcNode;
p1->adjvex=y;
p1->nextarc=G.verlist[x].firstarc;
G.verlist[x].firstarc=p1;
}
}void Print(Graph G){for(int i=1;
i<=G.vexnum;
i++){ArcNode* p=G.verlist[i].firstarc;
cout<nextarc!=NULL)cout<<" ";
p=p->nextarc;
}
cout<adjvex]){DFS(G,p->adjvex);
}
p=p->nextarc;
}
}int main(){Graph G;
CreateUDG(G);
Print(G);
DFS(G,1);
return 0;
}
7040
求度数相关的，写麻烦了，直接建图的时候统计就行了。可以看拓扑序列那里的建图操作。
#include
#include
#includeusing namespace std;
const int MAXN=105;
typedef struct ArcNode{int adjvex;
struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode{int data;
ArcNode *firstarc;
}VNode,AdjList[MAXN];
typedef struct{AdjList verlist;
int vexnum,arcnum;
}Graph;
void CreateUDG(Graph &G){cin>>G.vexnum>>G.arcnum;
for(int i=1;
i<=G.vexnum;
i++){cin>>G.verlist[i].data;
G.verlist[i].firstarc=NULL;
}
for(int i=1;
i<=G.arcnum;
i++){int x,y;
cin>>x>>y;
ArcNode * p1= new ArcNode;
p1->adjvex=y;
p1->nextarc=G.verlist[x].firstarc;
G.verlist[x].firstarc=p1;
}
}
int in[MAXN],out[MAXN];
void GetInfo(Graph G){for(int i=1;
i<=G.vexnum;
i++){ArcNode* p=G.verlist[i].firstarc;
while(p!=NULL){in[p->adjvex]++;
out[i]++;
p=p->nextarc;
}
}
}int main(){Graph G;
CreateUDG(G);
GetInfo(G);
for(int i=1;
i<=G.vexnum;
i++){cout< 7042
【锐格与C语言|[NEFU锐格 数据结构]实验五六 图有关的操作】无向图非递归DFS
#include
#include
#includeusing namespace std;
const int MAXN=105;
typedef struct ArcNode{int adjvex;
struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode{int data;
ArcNode *firstarc;
}VNode,AdjList[MAXN];
typedef struct{AdjList verlist;
int vexnum,arcnum;
}Graph;
void CreateUDG(Graph &G){cin>>G.vexnum>>G.arcnum;
for(int i=1;
i<=G.vexnum;
i++){cin>>G.verlist[i].data;
G.verlist[i].firstarc=NULL;
}
for(int i=1;
i<=G.arcnum;
i++){int x,y;
cin>>x>>y;
ArcNode * p1= new ArcNode;
ArcNode * p2= new ArcNode;
p1->adjvex=y;
p1->nextarc=G.verlist[x].firstarc;
G.verlist[x].firstarc=p1;
p2->adjvex=x;
p2->nextarc=G.verlist[y].firstarc;
G.verlist[y].firstarc=p2;
}
}bool vis[MAXN];
void DFS(Graph G,int u){stackstk;
stk.push(u);
vis[u]=true;
cout<<"v1 ";
while(!stk.empty()){int tt=stk.top();
ArcNode *p=G.verlist[tt].firstarc;
while(p&&vis[p->adjvex]){p=p->nextarc;
}
while(p&&!vis[p->adjvex]){cout<<"v"adjvex]=true;
stk.push(p->adjvex);
p=G.verlist[p->adjvex].firstarc;
}
if(p==NULL)stk.pop();
}
}int main(){Graph G;
CreateUDG(G);
DFS(G,1);
return 0;
}
7041
求拓扑序列，但是这玩意我感觉不是很好吧，不唯一的东西。可能你弄出来的拓扑序列也对的但是题目没加
Special Judge#include
#include
#include
#include
using namespace std;
const int MAXN=105;
typedef struct ArcNode{int adjvex;
struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode{int data;
ArcNode *firstarc;
}VNode,AdjList[MAXN];
typedef struct{AdjList verlist;
int vexnum,arcnum;
}Graph;
int deg[MAXN];
void CreateUDG(Graph &G){cin>>G.vexnum>>G.arcnum;
for(int i=1;
i<=G.vexnum;
i++){cin>>G.verlist[i].data;
G.verlist[i].firstarc=NULL;
}
for(int i=1;
i<=G.arcnum;
i++){int x,y;
cin>>x>>y;
deg[y]++;
ArcNode * p1= new ArcNode;
p1->adjvex=y;
p1->nextarc=G.verlist[x].firstarc;
G.verlist[x].firstarc=p1;
}
}void TopSort(Graph G){stacks;
for(int i=1;
i<=G.vexnum;
i++)
if(!deg[i])s.push(i);
while(!s.empty()){int tt=s.top();
s.pop();
cout<<"v"<adjvex]--;
if(deg[p->adjvex]==0)s.push(p->adjvex);
p=p->nextarc;
}
}
}int main(){Graph G;
CreateUDG(G);
TopSort(G);
return 0;
}
推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- Docker应用:容器间通信与Mariadb数据库主从复制
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 第326天
- Shell-Bash变量与运算符
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- 逻辑回归的理解与python示例
- Guava|Guava RateLimiter与限流算法
- 一起来学习C语言的字符串转换函数
- C语言字符函数中的isalnum()和iscntrl()你都知道吗