数据结构与算法- 图

图（Graph）是一种较线性表和树更复杂的数据结构。在图形结构中，结点之间的关系可以是任一的，图中任意两个数据元素之间都可能相关。

图的存储结构

邻接矩阵

邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn} 。G的邻接矩阵是一个具有下列性质的n阶方阵：

  • 对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。
  • 在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。
  • 用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。
#define INFINITYC 0
#define MAX_VERTEX_NUM 50

typedef int Status;
typedef char VertexType;
typedef int EdgeType;

typedef struct MGraph {
    VertexType vexs[MAX_VERTEX_NUM];
    EdgeType arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int numNodes, numEdges;
} MGraph;

void CreateMGraph(MGraph *G) {
    printf("输入顶点数和边数:\n");
    scanf("%d,%d", &G->numNodes, &G->numEdges);
    printf("顶点数:%d,边数:%d\n", G->numNodes, G->numEdges);
    
    int i, j, w;
    for (i = 0; i < G->numNodes; i++) {
        scanf("%c", &G->vexs[i]);
        getchar();
    }
    
    for (i = 0; i < G->numNodes; i++) {
        for (j = 0; j < G->numNodes; i++) {
            G->arc[i][j] = INFINITYC;
        }
    }
    
    for (int k = 0; k < G->numEdges; k++) {
        printf("输入边(vi, vj)上的下标i, 下标j, 权w\n");
        scanf("%d,%d,%d", &i, &j, &w);
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j];
    }
    
    for (int i = 0; i < G->numNodes; i++) {
        printf("\n");
        for (int j = 0; j < G->numNodes; j++) {
            printf("%d ",G->arc[i][j]);
        }
    }
    printf("\n");
}

邻接表

邻接表（Adjacency List）是图的一种链式存储结构。在连接表中，对图中的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点v1的边。每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点v1邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点。数据域存储和边或弧相关的信息。每个链表附设一个表头结点。

#define MAX_VERTEX_NUM 50
#define true 1
#define false 0

typedef char Element;
typedef int BOOL;

typedef struct ArcNode {
    int adjvex;
    Element data;
    struct ArcNode *nextArc;
} ArcNode;

typedef struct VNode {
    Element data;
    ArcNode * firstedge;
} VertexNode, Adjlist[MAX_VERTEX_NUM];

typedef struct ALGraph {
    Adjlist adjlist;
    int arc_num;
    int node_num;
    BOOL is_directed;
} ALGraph, *GraphLink;

void CreateGraph(GraphLink *G) {
    printf("输入顶点数目, 边数和方向？：\n");
    scanf("%d %d %d", &(*G)->node_num, &(*G)->arc_num, &(*G)->is_directed);
    
    printf("输入顶点信息：\n");
    int i, j;
    for (i = 0; i < (*G)->node_num; i++) {
        getchar();
        scanf("%c", &(*G)->adjlist[i].data);
        (*G)->adjlist[i].firstedge = NULL;
    }
    
    ArcNode *p;
    printf("输入边信息：\n");
    for (int k = 0; k < (*G)->arc_num; k++) {
        getchar();
        scanf("%d %d", &i, &j);
        
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextArc = (*G)->adjlist[i].firstedge;
        (*G)->adjlist[i].firstedge = p;
        
        if (!(*G)->is_directed) {
            p = (ArcNode *)malloc(sizeof(ArcNode));
            p->adjvex = i;
            p->nextArc = (*G)->adjlist[j].firstedge;
            (*G)->adjlist[j].firstedge = p;
        }
    }
}

void putGraph(GraphLink G){
    printf("邻接表中存储信息:\n");
    for (int i = 0; i < G->node_num; i++) {
        ArcNode *p = G->adjlist[i].firstedge;
        while (p) {
            printf("%c->%c ", G->adjlist[i].data, G->adjlist[p->adjvex].data);
            p = p->nextArc;
        }
        printf("\n");
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    GraphLink g = (ALGraph *)malloc(sizeof(ALGraph));
    CreateGraph(&g);
    putGraph(g);
    return 0;
}

图的遍历

和树的遍历类似，从图中某一个顶点出发访遍图中其余顶点，且使每一个顶点紧被访问一次，这一过程叫图的遍历。

深度优先搜索

邻接矩阵深度优先搜索

/*
 邻接矩阵深度优先搜索
 */

Boolean visited[MAX_VERTEX_NUM];

void DFS(MGraph G, int v) {
    visited[v] = TRUE;
    
    printf("%c ", G.vexs[v]);
    for (int i = 0; i < G.numNodes; i++) {
        if (!visited[i] && G.arc[v][i] == 1) {
            DFS(G, i);
        }
    }
}

void DFSTraverse(MGraph G) {
    for (int i = 0; i < G.numNodes; i++) {
        visited[i] = FALSE;
    }
    
    for (int i = 0; i < G.numNodes; i++) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }
    printf("\n");
}

邻接表深度优先搜索

/*
 邻接表深度优先搜索
 */

BOOL visited[MAX_VERTEX_NUM];

void DFS(ALGraph G, int v) {
    visited[v] = true;
    printf("%c", G.adjlist[v].data);
    
    ArcNode *p;
    p = G.adjlist[v].firstedge;
    
    while (p) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex);
        }
        p = p->nextArc;
    }
}

void DFSTraverse(ALGraph G) {
    for (int i = 0; i < G.node_num; i++) {
        visited[i] = false;
    }
    
    for (int i = 0; i < G.node_num; i++) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }
    printf("\n");
}

分析上述算法，在遍历图时，对图中每个顶点至多调用一次DFS函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。

  • 当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需要的时间为O(n^2),其中n为图中顶点数。
  • 当用邻接表作图的存储结构时，找邻接点所需要的时间为O(e)，其中e为无向图中边的数或有向图中弧的数，因此，当以邻接表作为存储结构时，深度优化搜索遍历图的时间浮渣度为O(n + e)。

广度优先搜索

邻接矩阵的广度优先搜索

/*
邻接矩阵广度优先搜索
*/

void BFSTraverse(MGraph G) {
    for (int i = 0; i < G.numNodes; i++) {
        visited[i] = FALSE;
    }
    
    SqQueue Q;
    InitQueue(&Q);
    
    for (int i = 0; i < G.numNodes; i++) {
        if (!visited[i]) {
            visited[i] = TRUE;
            printf("%c ", G.vexs[i]);
            
            EnQueue(&Q, i);
            while (!QueueEmpty(Q)) {
                DeQueue(&Q, &i);
                for (int j = 0; j < G.numNodes; j++) {
                    if (G.arc[i][j] == 1 && !visited[j]) {
                        visited[j] = TRUE;
                        printf("%c ", G.vexs[j]);
                        EnQueue(&Q, j);
                    }
                }
            }
        }
    }
}

邻接表的广度优先搜索

/*
邻接表广度优先搜索
*/

void BFSTraverse(ALGraph G) {
    for (int i = 0; i < G.node_num; i++) {
        visited[i] = FALSE;
    }
    
    SqQueue Q;
    InitQueue(&Q);
    ArcNode *p;
    
    for (int i = 0; i < G.node_num; i++) {
        if (!visited[i]) {
            visited[i] = TRUE;
            printf("%c ", G.adjlist[i].data);
            
            EnQueue(&Q, i);
            while (!QueueEmpty(Q)) {
                DeQueue(&Q, &i);
                p = G.adjlist[i].firstedge;
                while (p) {
                    if (!visited[p->adjvex]) {
                        visited[p->adjvex] = TRUE;
                        printf("%c ", G.adjlist[p->adjvex].data);
                        EnQueue(&Q, p->adjvex);
                    }
                    p = p->nextArc;
                }
            }
        }
    }
}

分析上述算法，每个顶点至多进一次队列。遍历图的过程实质上是通过边和弧找邻接点的过程。因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。

Demo：https://github.com/ShoukaiWang/DataStructuresAndAlgorithms

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,772评论 6赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,458评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,610评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,640评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,657评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,590评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,962评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,631评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,870评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,611评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,704评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,386评论 4赞 319
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,969评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,944评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,179评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 44,742评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,440评论 2赞 342