【数据结构6】图

  • 图存储结构的定义
    • 1 图的邻接矩阵定义法
    • 2 图的邻接表定义法
    • 3 有向图的十字链表定义法
    • 4 无向图的邻接多重表定义法
  • 图的遍历
    • 1 深度优先搜索
    • 2广度优先搜索
  • 图的基本应用
    • 1 最小生成树
      • 11 Prim算法
      • 12 Kruskal算法
    • 2 最短路径
      • 21 Dijkstra算法
      • 22 Floyd-Warshall算法
    • 3 拓扑排序
    • 4 关键路径
  • 图的实例

1 图存储结构的定义

1.1 图的邻接矩阵定义法

用一个一维数组存储图中顶点（vertex）的信息，用一个二维数组存储图中边（弧arc）的信息（即各顶点之间的邻接关系）。存储顶点之间的邻接关系的二维数组称为邻接矩阵。
 对于有向图，如果vi到vj有边，arc[vi][vj] = 1；如果vi到vj无边，arc[vi][vj] = 0。
 对于无向图，如果vi到vj有边，arc[vi][vj] = arc[vj][vi] = 1；如果vi到vj无边，arc[vi][vj] = arc[vj][vi] = 0。

 对于带权图（网），若顶点vi和vj之间有边相连，则邻接矩阵中对应项存放着对应的权值；若不相连，则用∞来表示两个顶点之间不存在的边。 

#define MaxVertexNum 100
#define VertexType int

//## 1.1 图的邻接矩阵定义法
typedef struct{
    VertexType vexs[MaxVertexNum];          //顶点信息
    int arc[MaxVertexNum][MaxVertexNum];    //边（弧）信息
    int vexnum,arcnum;                      //顶点数和边数
}MGraph;    //以邻接矩阵存储的图类型

图的邻接矩阵存储表示法的特点：
1. 无向图的邻接矩阵一定是个对称矩阵，并且唯一。因此，在实际存储邻接矩阵只需存储上（下）三角矩阵的元素即可。
2. 对于无向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。对于有向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的出度（或入度）。
3. 容易确定图中任意两个顶点是否有边，但要确定图中有多少条边则按行（列）对每个元素检测，时间开销很大。
4. 空间复杂度为O(n^2)，适合存储稠密图。
5. 非带权图的邻接矩阵n次方值，就是对应顶点间路径长度为n的路径条数。

1.2 图的邻接表定义法

邻接表法是对图G中的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，这个单链表就称为顶点vi的边表（对于有向图则称为出边表），边表的头指针(firstarc)和顶点信息采用顺序存储，称为顶点表。所以，在邻接表中存在两种结点：顶点表（头）结点和边表结点。 

#define MaxVertexNum 100
#define VertexType int
#define WeightType double

//## 1.2 图的邻接表定义法
typedef struct ArcNode{ //弧（边表）结点
    int adjvex;         //弧所指顶点的位置（下标）
    WeightType cost;    //带权图的边权值(info)
    struct ArcNode *nextarc;//下一条弧指针
    //ArcNode *nextarc; //is also ok
}ArcNode;
typedef struct{         //顶点表（顶点/头）结点
    VertexType data;        //顶点数据
    ArcNode *firstarc;      //指向第一条依附该顶点的弧指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;       //邻接表
    int vexnum,arcnum;      //顶点数和边数
}ALGraph;           //以邻接表存储的图类型

图的邻接表存储表示法的特点：
1. 对于图G=(V,E)，如果G为无向图，则所需存储空间为O(|V|+2|E|)；如果G为有向图，则所需存储空间为O(|V|+|E|)。
2. 对于稀疏图，采用邻接表表示将大大节省存储空间。
3. 求某个顶点的所有邻边，只需读取它的邻接表。其效率O(ViE)一般比邻接矩阵O(n)所实现的优。
4. 确定两个顶点是否有边，需在邻接表相应的边表中查找另一个结点。其效率O(ViE)不如邻接矩阵O(1)所实现的。
5. 在有向图的邻接表中，求某个顶点的出度只需计算其边表结点个数；但求其入度，则需要遍历全部边表，因此可以设计逆邻接表实现快速求其入度，也可以设计下面的有向图的十字链表来实现。
6. 图的邻接表表示并不唯一，但可表示一个确定的图。因为每个顶点的边结点链接次序可以是任意的，取决于建立邻接表的算法和边的输入次序。

1.3 有向图的十字链表定义法


#define MaxVertexNum 100
#define VertexType int
#define InfoType double

//## 1.3 有向图的十字链表定义法
typedef struct XArcNode{
    int tailvex,headvex;
    struct XArcNode *hlink,*tlink;
    //XArcNode *hlink,*tlink;//Successful
    //InfoType info;
}XArcNode;
typedef struct{
    VertexType data;
    XArcNode *firstin,*firstout;
}XVNode;
typedef struct{
    XVNode xlist[MaxVertexNum];
    int vernum,arcnum;
}XLGraph;

1.4 无向图的邻接多重表定义法

2 图的遍历

2.1 深度优先搜索

#include<stdio.h>
#define MaxVertexNum 100
#define VertexType int
#define WeightType double
#define InfoType double

int visited[MaxVertexNum];

//## 1.1 图的邻接矩阵定义法
typedef struct{
    VertexType vexs[MaxVertexNum];
    int arc[MaxVertexNum][MaxVertexNum];
    int vexnum,arcnum;
}MGraph;

//## 1.2 图的邻接表定义法
typedef struct ArcNode{
    int nodeindex;
    WeightType cost;
    struct ArcNode *nextarc;
    //ArcNode *nextarc;//Successful
    //AdjNode *nextarc;//[Error] 'AdjNode' does not name a type
}AdjNode;
typedef struct{
    VertexType data;
    AdjNode *firstarc;
}VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph,Graph;

void DFS_M(MGraph G,int i){
    visited[i]=1;
    printf("%d ",i);//
    for(int j=0;j<G.vexnum;j++){
        if(visited[j]==0&&G.arc[i][j]==1){
            DFS_M(G,j);
        }
    }
}
void DFS_AL(ALGraph G,int i){
    visited[i]=1;
    printf("%d ",i);//
    for(ArcNode *p=G.vertices[i].firstarc;p;p=p->nextarc){
        int ind=p->nodeindex;
        if(visited[ind]==0){
            DFS_AL(G,ind);
        }
    }
}

void DFSTraverse(Graph G){
    for(int i=0;i<G.vexnum;i++){
        visited[i]=0;
    }
    for(int i=0;i<G.vexnum;i++){
        if(visited[i]==0){
            //DFS_M(G,i);//邻接矩阵
            DFS_AL(G,i); //邻接表
        }
    }
}

int main(){
    return 0;
}

2.2广度优先搜索

#include<stdio.h>
#define MaxVertexNum 100
#define VertexType int
#define WeightType double
#define InfoType double

int visited[MaxVertexNum];

//## 1.1 图的邻接矩阵定义法
typedef struct{
    VertexType vexs[MaxVertexNum];
    int arc[MaxVertexNum][MaxVertexNum];
    int vexnum,arcnum;
}MGraph;

//## 1.2 图的邻接表定义法
typedef struct ArcNode{
    int nodeindex;
    WeightType cost;
    struct ArcNode *nextarc;
    //ArcNode *nextarc;//Successful
    //AdjNode *nextarc;//[Error] 'AdjNode' does not name a type
}AdjNode;
typedef struct{
    VertexType data;
    AdjNode *firstarc;
}VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph,Graph;

void BFS_AL(ALGraph G,int i){
    visited[i]=1;
    printf("%d ",i);
    InitQueue(Q);
    EnQueue(Q,i);
    while(!IsEmpty(Q)){
        int v;
        DeQueue(Q,v);
        for(ArcNode* p=G.vertices[v].firstarc;p;p=p->nextarc){
            int ind=p->nodeindex;
            if(visited[ind]==0){
                printf("%d ",ind);
                visited[ind]=1;
                EnQueue(Q,ind);
            }
        }
    }
}
void BFS_M(MGraph G,int i){
    visited[i]=1;
    printf("%d ",i);
    InitQueue(Q);
    EnQueue(Q,i);
    while(!IsEmpty(Q)){
        int v;
        DeQueue(Q,v);
        for(int ind=0;ind<G.vexnum;ind++){
            if(visited[ind]==0&&G.arc[v][ind]==1){
                printf("%d ",ind);
                visited[ind]=1;
                EnQueue(Q,ind);
            }
        }
    }
}
void BFSTraverse(Graph G){
    for(int i=0;i<G.vexnum;i++){
        visited[i]=0;
    }
    for(int i=0;i<G.vexnum;i++){
        if(!visited[i]){
            //BFS_M(G,i);//邻接矩阵
            BFS_AL(G,i); //邻接表
        }
    }
}

int main(){
    return 0;
}

3 图的基本应用

3.1 最小生成树

3.1.1 Prim算法

3.1.2 Kruskal算法

#include<stdio.h>
#include<algorithm>
#define MaxVertexNum 100
//## 1.1 图的邻接矩阵定义法
using namespace std;
typedef struct{
    int a,b,w;
}Road;
typedef struct{
    int vexnum,arcnum;
    Road road[MaxVertexNum];
}MGraph;
    int sum=0;
    MGraph G;
    int v[MaxVertexNum];
int getRoot(int n){
    while(n!=v[n])
        n=v[n];
    return n;
}
bool cmp(Road r1,Road r2){
    return r1.w<r2.w;
}
void Kruskal(MGraph g,int &sum,Road road[]){
    int N=g.vexnum,E=g.arcnum;
    sum=0;
    for(int i=1;i<=N;i++){
        v[i]=i;
    }
    sort(road+1,road+E+1,cmp);
    //sort(v,v+MaxVertexNum);
    for(int i=1;i<=E;i++){
        int a1=road[i].a;
        int b1=road[i].b;
        int ra=getRoot(a1);
        int rb=getRoot(b1);
        if(ra!=rb){
            v[ra]=rb;sum+=road[i].w;
        }
    }
}
void input(){
    printf("input vexnum arcnum:");
    scanf("%d %d",&G.vexnum,&G.arcnum);
    for(int i=1;i<=G.arcnum;i++){
        scanf("%d %d %d",&G.road[i].a,&G.road[i].b,&G.road[i].w);
    }
}
int main(){
    input();
    Kruskal(G,sum,G.road);
    printf("%d\n",sum);
    for(int i=1;i<=G.arcnum;i++){
        printf("%d ",G.road[i].w);
    }
    return 0;
}
/*
input
6 10
1 2 6
1 4 5
2 3 5
2 5 3
4 3 5
4 6 2
3 5 6
3 6 4
5 6 6
1 3 1
*/

3.2 最短路径

3.2.1 Dijkstra算法

/**
 * Copyright ? 2016 Authors. All rights reserved.
 *
 * FileName: .cpp
 * Author: Wu_Being <1040003585@qq.com>
 * Date/Time: 10-12-16 10:34
 * Description:
 */
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include<vector>
#include<queue>
#include <algorithm>
#define MAX_V 20000

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> Pii;

const int inf  = 0x7e7e7e7e;
const LL infLL = 0x7e7e7e7e7e7e7e7eLL;
const unsigned uinf  = 0xfcfcfcfc;
const ULL uinfLL = 0xfcfcfcfcfcfcfcfcLL;

using namespace std;
struct edge{
    int to,cost;
};
typedef pair<int,int>P;
int V;
vector<edge>G[MAX_V];
int d[MAX_V];

void dijkstra(int s){
    priority_queue<P,vector<P>,greater<P> >que;
    fill(d,d+V,inf);
    d[s]=0;//!!!!!!!!!!!
    que.push(P(0,s));
    while(!que.empty()){
        P p=que.top();que.pop();
        int v=p.second;
        if(d[v]<p.first)
            continue;
        for(int i=0;i<G[v].size();i++){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}
void input(){
    struct edge e;
    int E,f,t,c;
    cin>>V>>E;
    for(int i=0;i<E;i++){
        cin>>f>>t>>c;
        e.cost=c;
        e.to=t-1;   G[f-1].push_back(e);
        //e.to=f;   G[t].push_back(e);
    }
}
int main(int argc,char* argv[])
{
    input();
    dijkstra(0);
    for(int i=1;i<V;i++){
        cout<<d[i]<<endl;
    }
    return 0;
}
/*
样例输入
3 3
1 2 -1
2 3 -1
3 1 2
样例输出
-1
-2
数据规模
*/

3.2.2 Floyd-Warshall算法


void Floyd(int n)
{
    int i, j, k;

    for (k=0; k<n; k++)
    for (i=0; i<n; i++)
    for (j=0; j<n; j++)
        if (dist[i][k] != INF && dist[k][j] !=INF
            && dist[i][j] > dist[i][k] + dist[k][j])
        {
            dist[i][j] = dist[i][k] + dist[k][j];
            path[i][j] = k;       //i到j要经过K节点
        }
}

3.3 拓扑排序

3.4 关键路径

4 图的实例

Wu_Being 博客声明：本人博客欢迎转载，请标明博客原文和原链接！谢谢！
《【数据结构6】图》
http://blog.csdn.net/u014134180/article/details/55506259

如果你看完这篇博文，觉得对你有帮助，并且愿意付赞助费，那么我会更有动力写下去。

时间： 2024-10-10 19:22:38

【数据结构6】图的相关文章

图 数据结构-关于“图”的绘制，点和边的位置分配！

问题描述 关于"图"的绘制,点和边的位置分配! 遇到了一个问题,即在想根据输入的图的这个数据结构,根据其点和边的关系,绘出直观的图来.问题是不知道如何来解决其点和边的位置问题,烦恼了好久,得从哪里入手呢.希望得到一些指导和思路!~~求帮助~~!!

数据结构例程——图的遍历

本文是[数据结构基础系列(7):图]中第6课时[图的遍历]的例程. 1.深度优先遍历--DFS(程序中graph.h是图存储结构的"算法库"中的头文件,详情请单击链接-) #include <stdio.h> #include <malloc.h> #include "graph.h" int visited[MAXV]; void DFS(ALGraph *G, int v) { ArcNode *p; int w; visited[v]=

数据结构例程——图的邻接矩阵存储结构及算法

本文是[数据结构基础系列(7):图]中第4课时[图的邻接矩阵存储结构及算法]的例程. #include <stdio.h> #include <malloc.h> #define MAXV 100 /*最大顶点数设为100*/ #define LIMITLESS 9999 typedef struct { int no; //顶点编号 char info[20]; //顶点其他信息,类型视应用而定 } VertexType; //顶点类型 typedef struct //图的定义

C语言版的数据结构求图的遍历，但是调试时为什么会出现已停止工作？

问题描述 #include<stdio.h>#include<stdlib.h>#include<conio.h>#include<malloc.h>#defineNULL0#defineFALSE0#defineTRUE1#definemaxsize100structarcnode{intadjvex;intinfo;structarcnode*nextarc;};structvexnode{intdata;structarcnode*firstarc;}

数据结构学习(C++)之图

图的应用恐怕是所有数据结构中最宽泛的了,但这也注定了在讲"数据结构的图"的时候没什么好讲的--关于图的最重要的是算法,而且相当的一部分都是很专业的,一般的人几乎不会接触到:相对而言,结构就显得分量很轻.你可以看到关于图中元素的操作很少,远没有单链表那里列出的一大堆"接口".--一个结构如果复杂,那么能确切定义的操作就很有限. 基本储存方法 不管怎么说,还是先得把图存起来.不要看书上列出了好多方法,根本只有一个--邻接矩阵.如果矩阵是稀疏的,那就可以用十字链表来储存矩

《数据结构与算法：Python语言描述》一1.2　问题求解：交叉路口的红绿灯安排

1.2 问题求解:交叉路口的红绿灯安排 本节展示一个具体问题的计算机求解过程,以此说明在这种过程中可能出现的一些情况,需要考虑的一些问题,以及一些可能的处理方法. 交叉路口是现代城市路网中最重要的组成部分,繁忙的交叉路口需要用红绿灯指挥车辆通行与等待,正确的红绿灯调度安排对于保证交通安全.道路运行秩序和效率都非常重要.交叉路口的情况多种多样,常见形式有三岔路口.十字路口,也有较为少见的更复杂形式的路口.进一步说,有些道路是单行线,在中国的交叉路口还有人车分流和专门的人行/自行车红绿灯等许多情况,

算法-数据结构C语言版 求助

问题描述 数据结构C语言版 求助 设顺序表L中的数据元素非递减有序,试编写一个算法,将e插入L的适当位置,以保持线性表的有序性 定义一个实现以上算法的函数: 数据结构菜鸟,求各位大神相助 解决方案 非递减有序,不就是递增么,说的那么绕干嘛. 既然是有序表,自然是二分查找或者顺序查找,然后插入. 解决方案二: http://zhidao.baidu.com/link?url=pDydQmKmMDqttsXL4CV7byP_o_8m_oRqZhgk_5eCKXDKqwsk1QJathKBqTcxNU

c-B-树的删除问题，数据结构

问题描述 B-树的删除问题,数据结构 如图5阶B-树,删除d之后,引起了两次合并.如果原来第二行的第二个结点有3个元素mtz怎么办?两次合并之后根结点不就溢出了吗?如果是我说的这种情况,d要怎么删除? 解决方案 http://download.csdn.net/detail/minimicall/2367690

一步一步写算法（之图添加和删除）

原文:一步一步写算法(之图添加和删除) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     前面我们谈到的图的数据结构.图的创建,今天我们就来说一说如何在图中添加和删除边.边的添加和删除并不复杂,但是关键有一点需要记住,那就是一定要在小函数的基础之上构建大函数,否则很容易出现错误.     一.边的创建     边的创建一般来说可以分为下面以下几个步骤:     1)判断当前图中是否有节点,如果没有,那么在pGraph->head处添

Lua数据结构 &amp;#8212; Table（三）

作者: 罗日健 前面(一).(二)里面其实已经把一些常用的数据类型(数值.布尔.字符串)说明了,这次要描述的是Table,Table在Lua里是一种常用的数据类型,是Lua里的精髓之一,其效率必须得到保证,而实现这种支持任意类型key和value的Table也是较为复杂的. 一, Table的设计思想: 1, 首先,讲一下Lua要设计的Table是怎么样子的: Lua就是想做这种支持任意类型的key和任意类型val的table,并且要高效和节约内存. 2, 基本的实现(基于链表的实现): 基于链