一、图的相关概念

图的相关概念包括顶点、边、有向图和无向图等。图是计算机科学中一个核心的数据结构,用于描述对象之间的关系。它由顶点(节点)的集合和连接这些顶点的边的集合组成。具体分析如下:

  1. 顶点:图中的基本构成单位,也称为节点或顶点
  2. :连接两个顶点的线段,可以是有向的或无向的,代表两个顶点之间的关系
  3. 有向图:边具有方向性,即从一个顶点指向另一个顶点,表示关系的非对称性
  4. 无向图:边没有方向,表示两个顶点之间的相互关系
  5. 完全图:每对不同顶点之间都恰好有一条边相连的图,分为有向完全图和无向完全图
  6. 邻接顶点:在无向图中,如果存在一条边直接连接两个顶点,则这两个顶点互为邻接顶点;在有向图中,如果存在一条边从顶点A指向顶点B,则称顶点B邻接自顶点A
  7. 顶点的度:与某个顶点相关联的边的总数,对于有向图来说,顶点的度等于其入度和出度之和
  8. 路径:一系列的顶点和边交替出现形成的序列,表示从一个顶点到另一个顶点的路线
  9. 简单路径与回路:路径上不重复访问同一个顶点的路径称为简单路径;如果起点和终点相同的路径称为回路
  10. 子图:如果一个图的顶点集和边集都是另一个图的子集,那么这个图就是另一个图的子图

除了上述基本概念外,图还有一些存储结构,如邻接矩阵和邻接表,以及遍历算法,如深度优先搜索(DFS)和广度优先搜索(BFS)。此外,图论中的一些经典问题包括最短路径问题、最小生成树问题、网络流问题等,它们都有对应的算法来解决。

综上所述,图是一种强大的数据结构,能够有效地模拟和解决现实世界中的许多问题,如社交网络分析、推荐系统、交通规划等。通过学习和掌握图的相关概念和算法,可以在多个领域内应用图的理论来优化问题解决方案。、

图的存储结构主要有邻接矩阵、邻接表、十字链表和邻接多重表。这些存储方法各有特点,适应不同类型的图和不同的操作需求。下面将具体介绍这几种存储结构:

  1. 邻接矩阵
    • 无向图的邻接矩阵:在这种表示法中,矩阵是对称的,即arcs[i][j]等于arcs[j][i],因为无向图中边没有方向
    • 有向图的邻接矩阵:在有向图的情况下,矩阵不对称,arcs[i][j]表示从顶点i到顶点j的边。
    • 网(有权图)的邻接矩阵:如果图中的边有权值,则邻接矩阵中的元素表示相应顶点之间边的权值
    • 邻接矩阵的存储表示:通常使用二维数组来实现,其中行和列代表图中的顶点,交叉点的值表示这两个顶点之间是否有边或权的值
  1. 邻接表
    • 无向图的邻接表表示:每个顶点对应一个链表,链表中包含与该顶点相邻的所有顶点。
    • 有向图的邻接表表示:在有向图中,邻接表显示为从每个顶点出发可以到达的顶点列表
    • 图的邻接表的存储定义:需要为每个顶点定义一个链表头节点,然后通过链表实现各顶点之间的连接关系
  1. 十字链表
    • 弧结点的结构:每个弧有一个结构来表示,其中包括弧的信息以及弧尾和弧头的位置信息。
    • 顶点结点的结构:每个顶点也有一个结构来表示,包括顶点信息及与该顶点相关联的弧的指针。
  1. 邻接多重表
    • 边结点的结构:在邻接多重表中,每条边使用一个结点表示[1]。
    • 图的结构定义:图的结点不仅包含顶点信息,还包括一个指向所有依附于该顶点的边的列表的头指针

针对上述分析,提出以下补充内容:

  • 邻接矩阵适合稠密图,可以快速判断两个顶点间是否有边。
  • 邻接表适合稀疏图,只存储存在的边,节省空间
  • 十字链表和邻接多重表提供了更加灵活的图表示方式
  • 对于带权图,存储结构需要扩展以保存权值信息

综上所述,图的存储结构根据图的类型和实际应用场景的不同而有所选择。在实际应用中,选择合适的存储结构对于提高算法效率和节约存储空间至关重要。

二、邻接矩阵

邻接矩阵是图的一种存储方式,适用于稠密图和小规模的图,它直接在矩阵中存储顶点间的邻接关系。具体分析如下:

  1. 存储方式
    • 创建一个二维数组(矩阵),其大小为顶点数乘以顶点数
    • 矩阵的行和列分别代表图中的所有顶点,相交的单元格表示两个顶点之间是否有边
  1. 无向图邻接矩阵
    • 邻接矩阵是对称的,如果顶点i与顶点j相连,则arcs[i][j]arcs[j][i]相等且均不为
  1. 有向图邻接矩阵
    • 邻接矩阵不对称,如果从顶点i到顶点j有一条边,那么arcs[i][j]等于1(或边的权值),而arcs[j][i]可能为0
  1. 网(有权图)的邻接矩阵
    • 邻接矩阵中的每个元素值代表对应顶点间边的权值,如果没有边则为无穷大或其他特殊值
  1. 空间复杂度
    • 空间复杂度为V^2,其中V是顶点的数量
  1. 时间复杂度
    • 判断任意两点是否相邻的时间复杂度为O(1),因为直接索引矩阵即可
  1. 优缺点
    • 优点包括容易实现,能快速判断顶点间是否存在边,易于编程
    • 缺点是占用空间大,尤其是对于稀疏图,会浪费很多存储空间
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 5;
const int MAX_VALUE = INT_MAX;

typedef char ElemType;
typedef struct GraphMatrix {
    ElemType arrayV[N];  // 顶点数组
    int matrix[N][N];    // 邻接矩阵
    bool isDirect;       // 是否是有向图
    int size;            // 顶点个数
} GraphMatrix,* Graph;

/**
 * 初始化
 * @param V 要构建的图的顶点数组
 * @param isDirect 是否为有向图
 * @param size 顶点个数
 * @return 这个图的地址
 */
Graph initGraphMatrix(ElemType* V, bool isDirect, int size) {
    // 1. 创建图
    auto graph = (Graph) malloc(sizeof(GraphMatrix));
    // 2. 初始化字段
    graph->isDirect = isDirect;
    graph->size = size;
    for (int i = 0; i < size; i++) {
        graph->arrayV[i] = V[i];
    }
    // 3. 初始化邻接矩阵
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            graph->matrix[i][j] = MAX_VALUE;
        }
    }
    // 4. 返回地址
    return graph;
}

/**
 * 获取这个顶点的下标
 * @param graph
 * @param src
 */
int getIndexOfV(Graph& graph, ElemType src) {
    // 1. 循环遍历,可以使用map进行优化
    for (int i = 0; i < graph->size; i++) {
        if (graph->arrayV[i] == src) {
            return i;
        }
    }
    return -1;
}

/**
 * 添加一条变
 * @param graph 操作的图
 * @param src  起点
 * @param dest 终点
 * @param weight 权重
 */
void addEdge(Graph& graph, ElemType src, ElemType dest, int weight) {
    // 1. 合法检验
    if (graph == nullptr) return;
    // 2. 查询两个顶点对应的邻接矩阵下标
    int srcIndex = getIndexOfV(graph, src);
    int destIndex = getIndexOfV(graph, dest);
    // 3. 判断下标合法
    if (srcIndex < 0 || destIndex < 0 || srcIndex > graph->size || destIndex > graph->size) return;
    // 4. 添加一条边
    graph->matrix[srcIndex][destIndex] = weight;
    // 5. 如果这是无向图则添加dest到src
    if (!graph->isDirect) graph->matrix[destIndex][srcIndex] = weight;
}

/**
 * 获取边的度
 * @param graph 图
 * @param V 边
 * @return
 */
int getDevOfV(Graph& graph, ElemType V) {
    // 1. 合法判断
    if (graph == nullptr) return -1;
    // 2. 获取下标
    int index = getIndexOfV(graph, V);
    if (index < 0 || index > graph->size) return -1;
    // 2. 遍历邻接矩阵
    int cnt = 0;
    for (int i = 0; i < graph->size; i++) {
        if (graph->matrix[index][i] != MAX_VALUE) cnt++;
        if (!graph->isDirect && graph->matrix[i][index]) cnt++;
    }
    // 3. 返回度
    return cnt;
}

/**
 * 打印矩阵
 * @param graph 图
 */
void printGraph(Graph& graph) {
    for (int i = 0; i < graph->size; i++) {
        for (int j = 0; j < graph->size; j++) {
            if (graph->matrix[i][j] == MAX_VALUE) cout << "-" << "   ";
            else cout << graph->matrix[i][j] << "   ";
        }
        cout << "\n";
    }
    cout << "----------------------\n";
}

/**
 * bfs
 * @param graph
 */
void bfs(Graph& graph, ElemType src) {
    // 1. 合法校验
    if (graph == nullptr) return;
    // 2. 创建队列与visited数组
    bool visited[graph->size];
    int queue[graph->size << 1];
    int front = 0, rear = 0;
    // 3. 入队顶点
    int index = getIndexOfV(graph,src);
    if (index < 0 || index > graph->size) return;
    queue[rear++] = index;
    // 4. 开始bfs
    while (front < rear) {
        int top = queue[front++];
        cout << graph->arrayV[top] << "->";
        for (int i = 0; i < graph->size; i++) {
            if (graph->matrix[top][i] != MAX_VALUE && !visited[i]) {
                queue[rear++] = i;
                visited[top] = true;
            }
        }
    }
    cout << "\n----------------------\n";
}

/**
 * dfs
 * @param graph
 * @param src
 * @param visited
 */
void dfsFun(Graph& graph, int src, bool* visited) {
    cout << graph->arrayV[src] << "->";
    visited[src] = true;

    for (int i = 0; i < graph->size; i++) {
        if (!visited[i] && graph->matrix[src][i] != MAX_VALUE) {
            dfsFun(graph, i, visited);
        }
    }
}

/**
 * dfs
 * @param graph
 * @param src
 */
void dfs(Graph& graph, ElemType src) {
    // 1. 合法校验
    if (graph == nullptr) return;
    // 2. dfs准备
    bool visited[graph->size];
    int index = getIndexOfV(graph, src);
    if (index < 0 || index > graph->size) return;
    // 3. dfs
    dfsFun(graph, index, visited);
    cout << "\n----------------------\n";
}

/**
 * 克鲁斯卡尔算法  最小生成树
 * @param graph 图
 * @param ans graph的最小生成树
 * @return 最小生成树的权值和
 */
int kruskal(Graph& graph, Graph& ans) {
    return -1;
}

/**
 * Prim算法
 * @param graph 图
 * @param ans 最小生成树
 * @return 最小生成树的权值之和
 */
int prim(Graph& graph, Graph& ans) {
    return -1;
}

/**
 * 迪杰斯特拉算法
 * @param graph 图
 * @param src 起始顶点
 * @param dist 距离数组--最短路
 * @param path 路径数组--最短路
 */
void dijkstra(Graph& graph, ElemType src, int* dist, int* path) {

}

/**
 * 贝尔曼算法
 * @param graph 图
 * @param src 起始顶点
 * @param dist 距离数组--最短路
 * @param path 路径数组--最短路
 * @return
 */
bool bellmanFord(Graph& graph, ElemType src, int* dist, int *path) {
    return 0;
}

/**
 * floyd算法
 * @param graph 图
 * @param dist 距离数组--多源最短路
 * @param path 距离数组--多源最短路
 */
void floydWarShall(Graph& graph, int** dist, int** path) {

}


int main() {
    auto* V = (ElemType*) malloc(sizeof(ElemType) * 4);
    V[0] = 'A', V[1] = 'B', V[2] = 'C', V[3] = 'D';
    Graph graph = initGraphMatrix(V, true, 4);
    //    printGraph(graph);
    //
    //    addEdge(graph, 'A', 'B', 1);
    //    addEdge(graph, 'A', 'C', 2);
    //
    //    printGraph(graph);
    addEdge(graph, 'A', 'B', 1);
    addEdge(graph, 'B', 'D', 1);
    addEdge(graph, 'D', 'A', 1);

    printGraph(graph);
    bfs(graph, 'A');
    dfs(graph, 'A');
    return 0;
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部