东北林业大学锐格测试题（图）-白红宇的个人博客

发布日期：2021-05-07 23:24:17 浏览次数：23 分类：精选文章

本文共 7089 字，大约阅读时间需要 23 分钟。

1、键盘输入数据，建立一个有向图的邻接表。

#include 
   
    
#include 
    
     
using namespace std;
#define MAX_VERTEXT_NUM 20
typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;
typedef struct VNode {
    int data;
    ArcNode *firstarc;
} VNode;
typedef struct ALgraph {
    VNode AdjList[MAX_VERTEXT_NUM];
    int vexnum, arcnum;
} ALGraph;
void creatArc(ALGraph &G) {
    int from, to;
    scanf("%d %d", &G.vexnum, &G.arcnum);
    
    for (int i = 1; i <= G.vexnum; i++) {
        cin >> G.AdjList[i].data;
        G.AdjList[i].firstarc = NULL;
    }
    
    for (int i = 1; i <= G.arcnum; i++) {
        scanf("%d %d", &from, &to);
        ArcNode *s = new ArcNode;
        s->adjvex = to;
        s->nextarc = G.AdjList[from].firstarc;
        G.AdjList[from].firstarc = s;
    }
}

2、在有向图的邻接表的基础上计算各顶点的度，并输出。

#include 
   
    
#include 
    
     
using namespace std;
#define MAX_VERTEXT_NUM 20
typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;
typedef struct VNode {
    int data;
    ArcNode *firstarc;
} VNode;
typedef struct ALgraph {
    VNode AdjList[MAX_VERTEXT_NUM];
    int vexnum, arcnum;
} ALGraph;
int IN[MAX_VERTEXT_NUM] = {0};
int OUT[MAX_VERTEXT_NUM] = {0};
void creatArc(ALGraph &G) {
    int from, to;
    scanf("%d %d", &G.vexnum, &G.arcnum);
    
    for (int i = 1; i <= G.vexnum; i++) {
        cin >> G.AdjList[i].data;
        G.AdjList[i].firstarc = NULL;
    }
    
    for (int i = 1; i <= G.arcnum; i++) {
        scanf("%d %d", &from, &to);
        OUT[from]++;
        IN[to]++;
        ArcNode *s = new ArcNode;
        s->adjvex = to;
        s->nextarc = G.AdjList[from].firstarc;
        G.AdjList[from].firstarc = s;
    }
}
void Print(ALGraph &G) {
    for (int i = 1; i <= G.vexnum; i++) {
        cout << G.AdjList[i].data << ":";
        cout << " In: " << IN[i] << " Out: " << OUT[i] << " Total: " << (IN[i] + OUT[i]);
        cout << endl;
    }
}
int main() {
    ALGraph G;
    int i;
    creatArc(G);
    Print(G);
    return 0;
}

3、以有向图的邻接表为基础实现输出它的拓扑排序序列。

#include 
   
    
#include 
    
     
using namespace std;
#define MAX_VERTEXT_NUM 20
#define MVNum 100 // 最大顶点数
typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;
typedef struct VNode {
    int data;
    ArcNode *firstarc;
} VNode;
typedef struct {
    VNode AdjList[MAX_VERTEXT_NUM];
    int vexnum, arcnum;
} ALGraph;
int IN[MAX_VERTEXT_NUM] = {0};
int OUT[MAX_VERTEXT_NUM] = {0};
int visited[MAX_VERTEXT_NUM] = {0};
void creatArc(ALGraph &G) {
    int from, to;
    scanf("%d %d", &G.vexnum, &G.arcnum);
    
    for (int i = 1; i <= G.vexnum; i++) {
        cin >> G.AdjList[i].data;
        G.AdjList[i].firstarc = NULL;
    }
    
    for (int i = 1; i <= G.arcnum; i++) {
        scanf("%d %d", &from, &to);
        OUT[from]++;
        IN[to]++;
        ArcNode *s = new ArcNode;
        s->adjvex = to;
        s->nextarc = G.AdjList[from].firstarc;
        G.AdjList[from].firstarc = s;
    }
}
void TOPSORT(ALGraph G) {
    int i, j, n = 0;
    int Stack[MVNum], top = -1;
    ArcNode *p;
    
    for (i = 1; i <= G.vexnum; i++) {
        if (IN[i] == 0) {
            Stack[++top] = i;
        }
    }
    
    while (top != -1) {
        i = Stack[top--];
        n++;
        cout << "v" << i << " ";
        
        p = G.AdjList[i].firstarc;
        while (p != NULL) {
            j = p->adjvex;
            IN[j]--;
            if (IN[j] == 0) {
                Stack[++top] = j;
            }
            p = p->nextarc;
        }
    }
}
int main() {
    ALGraph G;
    creatArc(G);
    TOPSORT(G);
    return 0;
}

4、采用邻接表存储实现无向图的深度优先遍历。

#include 
   
    
#include 
    
     
using namespace std;
#define MAX_VERTEXT_NUM 20
typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;
typedef struct VNode {
    int data;
    ArcNode *firstarc;
} VNode;
typedef struct {
    VNode AdjList[MAX_VERTEXT_NUM];
    int vexnum, arcnum;
} ALGraph;
void creatArc(ALGraph &G) {
    int from, to;
    scanf("%d %d", &G.vexnum, &G.arcnum);
    
    for (int i = 1; i <= G.vexnum; i++) {
        cin >> G.AdjList[i].data;
        G.AdjList[i].firstarc = NULL;
    }
    
    for (int i = 1; i <= G.arcnum; i++) {
        scanf("%d %d", &from, &to);
        ArcNode *s1, *s;
        s = new ArcNode;
        s->adjvex = to;
        s->nextarc = G.AdjList[from].firstarc;
        G.AdjList[from].firstarc = s;
        
        s1 = new ArcNode;
        s1->adjvex = from;
        s1->nextarc = G.AdjList[to].firstarc;
        G.AdjList[to].firstarc = s1;
    }
}
void DFS(ALGraph G, int v) {
    cout << "v" << v << " ";
    visited[v] = 1;
    
    ArcNode *p = G.AdjList[v].firstarc;
    while (p != NULL) {
        int w = p->adjvex;
        if (!visited[w]) {
            DFS(G, w);
        }
        p = p->nextarc;
    }
}
void DFSTraversse(ALGraph G) {
    int v;
    for (v = 1; v <= G.vexnum; v++) {
        visited[v] = 0;
    }
    
    for (v = 1; v <= G.vexnum; v++) {
        if (!visited[v]) {
            DFS(G, v);
        }
    }
}
int main() {
    ALGraph G;
    creatArc(G);
    DFSTraversse(G);
    return 0;
}

5、采用邻接表存储实现无向图的广度优先遍历。

#include 
   
    
#include 
    
     
using namespace std;
#define MAX_VERTEXT_NUM 20
#define MVNum 100 // 最大顶点数
typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;
typedef struct VNode {
    int data;
    ArcNode *firstarc;
} VNode;
typedef struct {
    VNode AdjList[MAX_VERTEXT_NUM];
    int vexnum, arcnum;
} ALGraph;
void creatArc(ALGraph &G) {
    int from, to;
    scanf("%d %d", &G.vexnum, &G.arcnum);
    
    for (int i = 1; i <= G.vexnum; i++) {
        cin >> G.AdjList[i].data;
        G.AdjList[i].firstarc = NULL;
    }
    
    for (int i = 1; i <= G.arcnum; i++) {
        scanf("%d %d", &from, &to);
        ArcNode *s1, *s;
        s = new ArcNode;
        s->adjvex = to;
        s->nextarc = G.AdjList[from].firstarc;
        G.AdjList[from].firstarc = s;
        
        s1 = new ArcNode;
        s1->adjvex = from;
        s1->nextarc = G.AdjList[to].firstarc;
        G.AdjList[to].firstarc = s1;
    }
}
int visit[MVNum];
void DFS(ALGraph G, int v) {
    cout << "v" << v << " ";
    visit[v] = 1;
    
    int Front = 0, Rear = 0, j;
    ArcNode *p;
    int que[MVNum];
    
    Rear = (Rear + 1) % MVNum;
    que[Rear] = v;
    
    while (Front != Rear) {
        Front = (Front + 1) % MVNum;
        j = que[Front];
        p = G.AdjList[j].firstarc;
        
        while (p != NULL) {
            int w = p->adjvex;
            if (visit[w] == 0) {
                cout << "v" << w << " adjvex ";
                visit[w] = 1;
                
                Rear = (Rear + 1) % MVNum;
                que[Rear] = w;
            }
            p = p->nextarc;
        }
    }
}
void DFSTraversse(ALGraph G) {
    int v;
    for (v = 1; v <= G.vexnum; v++) {
        visit[v] = 0;
    }
    
    for (v = 1; v <= G.vexnum; v++) {
        if (!visit[v]) {
            DFS(G, v);
        }
    }
}
int main() {
    ALGraph G;
    creatArc(G);
    DFSTraversse(G);
    return 0;
}

上一篇：数据结构课设（线性表，栈和队列，链表，图，排序查找）

下一篇：大二数据结构（排序）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章