邻接表方式对图进行DFS,BFS和拓扑排序
第一步：定义邻接表的储存方式（结构体）：
data 那边放的是顶点集合
右边放的是边的集合，其实也是点，只不过，两个点就可以看成一个边了是吧，比如第一行，左边表示 v0这个点，，右边就表示 v0 和 v1所构成的边， v0 和 v3点 所构成的边，
边的结构体：
#include<bits/stdc++.h>
#define MVNum 20 //最大顶点数
using namespace std;
const int maxn = 100;
bool visted[maxn];
int topu[maxn];
typedef struct ArcNode{
int adjvex; // 该边所指向顶点的位置
struct ArcNode *nextarc; // 指向下一条边的指针
int info; // 和边相关的信息
}ArcNode;点的结构体：
typedef struct VNode{ // 顶点信息
int data;
int indegree; // 入度
int falg; // 序号
ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode , AdjList[MVNum]; 图的结构体：
typedef struct {
AdjList vertices;
int vexnum, arcnum; // 图的当前顶点数和边数
}ALGraph;前面不理解先别往下看
第二步：创建图：
int LocateVex(ALGraph &G, VNode v,int flag){
int cnt = -1;
for (int i= 0;i < G.vexnum ;i++){
if(v.data == G.vertices[i].data && flag == G.vertices[i].falg){
cnt = i;
break;
}
}
return cnt;
}
void CreateHDG (ALGraph &G){
VNode v1, v2;
int flag1,flag2;
cout << "请输入有向连通图的总顶点数和总边数："<< endl;
cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数
for (int i= 0;i < G.vexnum ; i++ ){ //输入各点，构造表头节点表
cout << "请输入当前所创建顶点的值" << endl;
cin >> G.vertices[i].data; // 输入顶点值
G.vertices[i].firstarc = NULL; // 初始化表头节点的指针域为NULL
G.vertices[i].indegree = 0;
G.vertices[i].falg = i+1;
}
for (int k = 0 ; k < G.arcnum ; k++){ // 输入各边，构造邻接表
cout << "请分别输入当前所创建边所连接的两个顶点的值和序号（请输入四个数）"<<endl;
cin >> v1.data >> flag1 >> v2.data >> flag2; // 输入一条边依附的两个顶点,和标志，防止两个顶点有相同值的情况，下面的locate函数不起作用
int i =LocateVex(G, v1,flag1) ,j = LocateVex(G, v2,flag2);
G.vertices[j].indegree++;
// cout << i << " "<< j << endl;
//确定v1和v2在G中的位置，即顶点在G.vertices中的序号
ArcNode *p1 = new ArcNode; // 生成一个新的边节点*p1
p1->adjvex = j; // 临界点序号为j
p1->nextarc = G.vertices[i] .firstarc;
G.vertices[i].firstarc = p1;
// 将新节点*p1,插入到顶点vj的边表头部
}
}第三步： DFS:
注意，因为这个dfs没有回朔，所以只能遍历连通图
void DfS(ALGraph G, int v){
cout << G.vertices[v].data<<" ";
visted[v] = true;
ArcNode *p = G.vertices[v] .firstarc;
while(p!=NULL){
int w = p->adjvex;
if(!visted[w]) DfS(G, w);
p = p -> nextarc;
}
}第四步：BFS :
void NextAdjVex(ALGraph G , int u, int &w){
ArcNode *p = G.vertices[u].firstarc;
int flag =0;
while(p!=NULL){
w = p ->adjvex;
if(!visted[w]) {
flag = 1;
break;
}
p = p->nextarc;
}
if(flag == 0) w = -1;
}
queue<int> qu; // 定义一个对列，c++ stl 内置了队列的数据结构，直接拿来用
void Bfs(ALGraph G, int v){
cout << G.vertices[v].data<<" ";
visted[v] = true;
qu.push(v);
while(!qu.empty()){
int u =qu.front();
qu.pop();
ArcNode *p = G.vertices[u].firstarc;
int w;
if(!p){
w = -1;
}
else w = p ->adjvex;
for( ; w >= 0 ;NextAdjVex(G, u, w) )
if(!visted[w]){
cout<< G.vertices[w].data <<" ";
visted[w] = true;
qu.push(w);
}
}
}第五步：计算某个顶点的度：
int CountDegree(ALGraph G,int v){
int cnt = 0;
ArcNode *p = G.vertices[v].firstarc;
while(p != NULL){
cnt ++;
p = p->nextarc;
}
return cnt;
}第六步：拓扑排序：
bool TUPUSort(ALGraph G){
stack<int >s;
for(int i=0;i < G.vexnum ;i++){
if(!G.vertices[i].indegree) s.push(i);
}
int cnt =0;
while(!s.empty()){
int i = s.top();
s.pop();
topu[cnt] = i;
++cnt;
ArcNode *p = G.vertices[i].firstarc;
while(p!=NULL){
int k = p->adjvex;
--G.vertices[k].indegree;
if( G.vertices[k].indegree== 0) s.push(k);
p = p->nextarc;
}
}
if(cnt < G.vexnum) return false;
else return true;
}完工
完整代码
//
// main.cpp
// 第六次实验
//
// Created by 宋玉良 on 2020/12/2.
//
#include<bits/stdc++.h>
#define MVNum 20 //最大顶点数
using namespace std;
const int maxn = 100;
bool visted[maxn];
int topu[maxn];
int cntt = 0,cnt1 = 0;
typedef struct ArcNode{
int adjvex; // 该边所指向顶点的位置
struct ArcNode *nextarc; // 指向下一条边的指针
int info; // 和边相关的信息
}ArcNode;
typedef struct VNode{ // 顶点信息
int data;
int indegree;
int falg;
ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode , AdjList[MVNum]; //AdjList 表示邻接表类型
typedef struct {
AdjList vertices;
int vexnum, arcnum; // 图的当前顶点数和边数
}ALGraph;
int LocateVex(ALGraph &G, VNode v,int flag){
int cnt = -1;
for (int i= 0;i < G.vexnum ;i++){
if(v.data == G.vertices[i].data && flag == G.vertices[i].falg){
cnt = i;
break;
}
}
return cnt;
}
void CreateHDG (ALGraph &G){
VNode v1, v2;
int flag1,flag2;
cout << "请输入有向连通图的总顶点数和总边数："<< endl;
cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数
for (int i= 0;i < G.vexnum ; i++ ){ //输入各点，构造表头节点表
cout << "请输入当前所创建顶点的值" << endl;
cin >> G.vertices[i].data; // 输入顶点值
G.vertices[i].firstarc = NULL; // 初始化表头节点的指针域为NULL
G.vertices[i].indegree = 0;
G.vertices[i].falg = i+1;
}
for (int k = 0 ; k < G.arcnum ; k++){ // 输入各边，构造邻接表
cout << "请分别输入当前所创建边所连接的两个顶点的值和序号（请输入四个数）"<<endl;
cin >> v1.data >> flag1 >> v2.data >> flag2; // 输入一条边依附的两个顶点,和标志，防止两个顶点有相同值的情况，下面的locate函数不起作用
int i =LocateVex(G, v1,flag1) ,j = LocateVex(G, v2,flag2);
G.vertices[j].indegree++;
// cout << i << " "<< j << endl;
//确定v1和v2在G中的位置，即顶点在G.vertices中的序号
ArcNode *p1 = new ArcNode; // 生成一个新的边节点*p1
p1->adjvex = j; // 临界点序号为j
p1->nextarc = G.vertices[i] .firstarc;
G.vertices[i].firstarc = p1;
// 将新节点*p1,插入到顶点vj的边表头部
}
}
void DfS(ALGraph G, int v){
cntt ++;
cout << G.vertices[v].data<<" ";
visted[v] = true;
ArcNode *p = G.vertices[v] .firstarc;
while(p!=NULL){
int w = p->adjvex;
if(!visted[w]) DfS(G, w);
p = p -> nextarc;
}
}
void NextAdjVex(ALGraph G , int u, int &w){
ArcNode *p = G.vertices[u].firstarc;
int flag =0;
while(p!=NULL){
w = p ->adjvex;
if(!visted[w]) {
flag = 1;
break;
}
p = p->nextarc;
}
if(flag == 0) w = -1;
}
queue<int> qu; // 定义一个对列，c++ stl 内置了队列的数据结构，直接拿来用
void Bfs(ALGraph G, int v){
cnt1++;
cout << G.vertices[v].data<<" ";
visted[v] = true;
qu.push(v);
while(!qu.empty()){
int u =qu.front();
qu.pop();
ArcNode *p = G.vertices[u].firstarc;
int w;
if(!p){
w = -1;
}
else w = p ->adjvex;
for( ; w >= 0 ;NextAdjVex(G, u, w) )
if(!visted[w]){
cnt1++;
cout<< G.vertices[w].data <<" ";
visted[w] = true;
qu.push(w);
}
}
}
int CountDegree(ALGraph G,int v){
int cnt = 0;
ArcNode *p = G.vertices[v].firstarc;
while(p != NULL){
cnt ++;
p = p->nextarc;
}
return cnt;
}
bool TUPUSort(ALGraph G){
stack<int >s;
for(int i=0;i < G.vexnum ;i++){
if(!G.vertices[i].indegree) s.push(i);
}
int cnt =0;
while(!s.empty()){
int i = s.top();
s.pop();
topu[cnt] = i;
++cnt;
ArcNode *p = G.vertices[i].firstarc;
while(p!=NULL){
int k = p->adjvex;
--G.vertices[k].indegree;
if( G.vertices[k].indegree== 0) s.push(k);
p = p->nextarc;
}
}
if(cnt < G.vexnum) return false;
else return true;
}
int main()
{
ALGraph G;
CreateHDG(G);
memset(visted, false, sizeof(visted));
int v;
cout << "请输入遍历开始点的序号："<<endl;
cin >> v;
cout << "深度优先遍历序列为：" <<endl;
DfS(G, v-1);
cout << endl;
if(cntt < G.vexnum){
cout <<"请从未遍历过的顶点开始遍历"<< endl;
int v1;
cout << "请输入遍历开始点的序号："<<endl;
cin >> v1;
DfS(G, v1-1);
}
cout << endl;
memset(visted, false, sizeof(visted));
cout << "广度优先遍历序列为： "<< endl;
Bfs(G, v-1);
cout << endl;
if(cnt1 < G.vexnum){
cout <<"请从未遍历过的顶点开始遍历"<< endl;
int v2;
cout << "请输入遍历开始点的序号："<<endl;
cin >> v2;
Bfs(G, v2-1);
}
cout << endl;
if(TUPUSort(G)){
cout << "拓扑排序成功，拓扑序列为："<<endl;
for(int i = 0; i<G.vexnum ;i++){
cout << topu[i]<<" ";
}
}
else{
cout << "此图无法构成拓扑序列";
}
cout << endl;
}
//7 10
//0 1 2 3 4 5 6
//0 2
//0 4
//1 2
//1 3
//2 5
//3 5
//2 4
//2 6
//5 6
//4 6
//0
/*输入样例和输出样例：
请输入有向连通图的总顶点数和总边数：
4 4
请输入当前所创建顶点的值
2
请输入当前所创建顶点的值
3
请输入当前所创建顶点的值
5
请输入当前所创建顶点的值
4
请分别输入当前所创建边所连接的两个顶点的值和序号（请输入四个数）
2 1
3 2
请分别输入当前所创建边所连接的两个顶点的值和序号（请输入四个数）
2 1 5 3
请分别输入当前所创建边所连接的两个顶点的值和序号（请输入四个数）
5 3 4 4
请分别输入当前所创建边所连接的两个顶点的值和序号（请输入四个数）
4 4 2 1
请输入遍历开始点的序号：
0
深度优先遍历序列为：
2 5 4 3
2 5 3 4
此图无法构成拓扑序列
*/
投递华为等公司10个岗位 >
