数据结构课内实验2
本文最后更新于 379 天前,其中的信息可能已经有所发展或是发生改变。

建立所给  无向带权图  的  邻接矩阵存储 并输出该矩阵
/*
 * @Author: Vastsea(lyx8851@qq.com)
 * @Date: 2023-05-31 11:58:17
 * @LastEditors: Vastsea(lyx8851@qq.com)
 * @LastEditTime: 2023-06-05 08:45:08
 * @FilePath: \Development\Cpp\3_SecondSemesterCollege\Experiment\InClass_Experiment_2\1_邻接矩阵.cpp
 * @Description: 建立所给  无向带权图  的  邻接矩阵存储
 *               并输出该矩阵
 * Link:https://59888888.xyz/
 * Phone:18893558104
 */
#include <iostream>
using namespace std;
#define MAXN 100
int G[MAXN][MAXN];
int n, m,u, v, w;
int main()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            G[i][j] = 0;
        }
    }
    cout<<"请输入节点数和边数"<<endl;
    cin >> n >> m;
    cout<<"请依次输入边的起点、终点和权值"<<endl;
    for (int i = 0; i < m; i++)
    {
        cin >> u >> v >> w;
        G[u][v] = G[v][u] = w;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << G[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

建立所给无向图的邻接表 并输出该图的深度和广度优先遍历结果

这个写的好像有些问题,再看吧

/*
 * @Author: Vastsea(lyx8851@qq.com)
 * @Date: 2023-05-31 11:58:43
 * @LastEditors: Vastsea(lyx8851@qq.com)
 * @LastEditTime: 2023-06-05 09:47:53
 * @FilePath: \Development\Cpp\3_SecondSemesterCollege\Experiment\InClass_Experiment_2\2_邻接表.cpp
 * @Description: 建立所给无向图的邻接表
 *                  并输出该图的深度和广度优先遍历结果
 * Link:https://59888888.xyz/
 * Phone:18893558104
 */
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
typedef int ElemType;
struct ArcNode
{
    int adjvex;
    struct ArcNode *next;
};
struct VertexNode
{
    ElemType vertex;
    ArcNode *firstedge;
};
struct Graph
{
    VertexNode vertex[100];
    int n, m;
};
// 用邻接表创建一个无向图
void createGraph(Graph &G)
{
    cout << "请输入节点数和边数" << endl;
    cin >> G.n >> G.m;
    cout << "将对点进行顺序编号" << endl;
    for (int i = 0; i < G.n; i++)
    {
        G.vertex[i].vertex = i+1;
        G.vertex[i].firstedge = NULL;
    }
    cout << "请依次输入边" << endl;
    for (int i = 0; i < G.m; i++)
    {
        int u, v;
        cin >> u >> v;
        ArcNode *p = new ArcNode;
        p->adjvex = v-1;
        p->next = G.vertex[u-1].firstedge;
        G.vertex[u-1].firstedge = p;

        p = new ArcNode;
        p->adjvex = u-1;
        p->next = G.vertex[v-1].firstedge;
        G.vertex[v-1].firstedge = p;
    }
}
void DFS(Graph G, int v, bool visited[])
{
    visited[v] = true;
    cout << v+1 << " ";
    ArcNode *p = G.vertex[v].firstedge;
    while (p)
    {
        int w = p->adjvex;
        if (!visited[w])
        {
            DFS(G, w, visited);
        }
        p = p->next;
    }
}
void BFS(Graph G, int v, bool visited[])
{
    queue<int> q;
    q.push(v);
    visited[v] = true;

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        cout << u+1 << " ";
        ArcNode *p = G.vertex[u].firstedge;
        while (p)
        {
            int w = p->adjvex;
            if (!visited[w])
            {
                visited[w] = true;
                q.push(w);
            }
            p = p->next;
        }
    }
}

int main()
{
    Graph G;
    createGraph(G);
    bool visited[100] = { false };
    cout<<"深度优先遍历结果为:";
    for (int i = 0; i < G.n; i++)
    {
        if (!visited[i])
        {
            DFS(G, i, visited);
        }
    }
    cout << endl;

    cout<<"广度优先遍历结果为:";
    for (int i = 0; i < G.n; i++)
    {
        visited[i] = false;
    }
    for (int i = 0; i < G.n; i++)
    {
        if (!visited[i])
        {
            BFS(G, i, visited);
        }
    }
    cout << endl;
    return 0;
}

以无向网表示n个城市之间通信网络的建设计划 顶点表示城市 边上的权表示该线路的造价
设计一个方案,使这个通信网的总造价最低

转,略有修改,原文链接

/*
 * @Author: Vastsea(lyx8851@qq.com)
 * @Date: 2023-05-31 11:59:11
 * @LastEditors: Vastsea(lyx8851@qq.com)
 * @LastEditTime: 2023-06-05 13:53:44
 * @FilePath: \Development\Cpp\3_SecondSemesterCollege\Experiment\InClass_Experiment_2\3_通信网络建设.cpp
 * @Description: 以无向网表示n个城市之间通信网络的建设计划
 *                  顶点表示城市
 *                  边上的权表示该线路的造价
 *                  设计一个方案,使这个通信网的总造价最低
 * Link:https://59888888.xyz/
 * Phone:18893558104
 */
#include <bits/stdc++.h>
using namespace std;

struct Edge
{
    int x;
    int y;
    int weight;
} edge[100];
int ans = 0, n, e;
int father[100];

bool compare(Edge n1, Edge n2)
{
    return n1.weight < n2.weight;
}

int findFather(int num)
{
    while (father[num] != num)
    {
        num = father[num];
    }
    return num;
}

void kruskal()
{
    for (int i = 0; i < e; i++)
    {
        int a = findFather(edge[i].x);
        int b = findFather(edge[i].y);
        if (a != b)
        {
            ans += edge[i].weight;
            father[a] = b;
        }
    }
}

int main()
{
    cout << "输入点和边的个数:" << endl;
    cin >> n >> e;
    cout << "依次输入边:" << endl;
    for (int i = 0; i < e; i++)
    {
        cin >> edge[i].x >> edge[i].y >> edge[i].weight;
    }
    for (int i = 1; i <= n; i++)
    {
        father[i] = i;
    }
    sort(edge, edge + e, compare);
    kruskal();
    cout << "最少花费为:" << ans;
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇