数据结构基础6.1：图的表示方法_数据结构图的表示方法

图的表示方法有多种：1. 邻接矩阵法 2. 邻接链表法 3. 十字链表法 4. 邻接多重表法

本文主要介绍邻接矩阵法和邻接链表法。

1.邻接矩阵法 ：

好处：直观简单；方便检查任一对顶点间是否存在边；方便找任一顶点的所有邻接点；方便计算任一顶点的度。

坏处：浪费空间，对于稀疏图会有大量无效元素。

2.邻接矩阵法：

好处：方便找任一顶点的所有邻接点；节约稀疏图的空间

坏处：对于检查任意一对顶点间是否存在边并不方便。

两种表示方法具体代码如下：

1.邻接矩阵法 ：

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <malloc.h>
 
using namespace std;
 
/* 图的邻接矩阵表示法 */
 
typedef int Vertex;
typedef int Status;
typedef int WeightType;
#define MaxVertexSize 10  
#define ERROR 1
#define OK 0
 
/* 图结点的定义 */
typedef struct GraphNode {
    int Nv;
    int Ne;
    WeightType matrix[MaxVertexSize][MaxVertexSize];
} *MGraph;
 
/* 边结点的定义 */
typedef struct EdgeNode {
    Vertex head, rear;
    WeightType weight;
} Edge;
 
/* 初始化有NumV个顶点, 但是没有边的图 */
MGraph CreateGraph(int NumV)
{
    Vertex i, j;
    MGraph graph;
    if(!(graph = (MGraph)malloc(sizeof(struct GraphNode))))
        exit(1);
    graph->Nv = NumV;
    graph->Ne = 0;
    for(i = 0; i < NumV; i++)
        for(j = 0; j < NumV; j++)
            graph->matrix[i][j] = 0;
            
    return graph;
}
 
/* 向图中插入边 */
Status InsertEdge(MGraph graph, Edge edge)
{
    if(!graph)
        return ERROR;
    
    graph->matrix[edge.head][edge.rear] = edge.weight;
	/* 无向图还需添加下面一行代码 */
    graph->matrix[edge.rear][edge.head] = edge.weight;
 
    return OK;
}
 
/* 建立有Nv个顶点Ne条边的图 */
MGraph BuildGraph()
{
    int Nv;
    Vertex i;
    MGraph graph;
    Edge edge;
    
    scanf("%d", &Nv);
    graph = CreateGraph(Nv);
    scanf("%d", &graph->Ne);
    
    for(i = 0; i < graph->Ne; i++) {
        scanf("%d %d %d", &edge.head, &edge.rear, &edge.weight);
        InsertEdge(graph, edge);
    }
    
    return graph;
}
 
int main()
{
    MGraph graph;
 
    graph = BuildGraph();
 
    system("pause");
    return 0;
}

2.邻接链表法：

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <malloc.h>
 
using namespace std;
 
/* 图的邻接链表表示法 */
 
typedef int Vertex;
typedef int Status;
typedef int WeightType;
#define MaxVertexSize 10  
#define ERROR 1
#define OK 0
 
/* 邻接点的定义 */
typedef struct LinkNode {
    Vertex index;
    WeightType weight;
    struct LinkNode *next;
} *pLink;
 
/* 顶点表头结点的定义 */
typedef struct LinkHead {
    pLink firstnode;
} *pHead;
 
/* 图结点的定义 */
typedef struct GraphNode {
    int Nv; /* 顶点数 */
    int Ne; /* 边数 */
    pHead list; /* 邻接链表 */
} *LGraph;
 
/* 边结点的定义 */
typedef struct EdgeNode {
    Vertex head, rear;
    WeightType weight;
} Edge;
 
/* 初始化有NumV个顶点, 但是没有边的图 */
LGraph CreateGraph(int NumV)
{
    Vertex i;
    LGraph graph;
    if(NumV < 0)
        return NULL;
    if(!(graph = (LGraph)malloc(sizeof(struct GraphNode))))
        exit(1);
    if(!(graph->list = (pHead)malloc(NumV * sizeof(struct LinkHead))))
        exit(1);
    graph->Nv = NumV;
    graph->Ne = 0;
    
    for(i = 0; i < NumV; i++) {
        graph->list[i].firstnode = NULL;
    }
    
    return graph;
}
 
/* 向图中插入边 */
Status InsertEdge(LGraph graph, Edge edge)
{
    pLink insert;
    if(!graph)
        return ERROR;
    
    if(!(insert = (pLink)malloc(sizeof(struct LinkNode))))
        exit(1);
    /* 插入边的初始化和 */
    insert->index = edge.rear;
    insert->weight = edge.weight;
    /* 将边插入到表头结点的下一个结点处 */
    insert->next = graph->list[edge.head].firstnode;
    graph->list[edge.head].firstnode = insert;
 
	/* 若是无向图还需添加以下代码 */
    if(!(insert = (pLink)malloc(sizeof(struct LinkNode))))
        exit(1);
    /* 插入边的初始化和 */
    insert->index = edge.head;
    insert->weight = edge.weight;
    /* 将边插入到表头结点的下一个结点处 */
    insert->next = graph->list[edge.rear].firstnode;
    graph->list[edge.rear].firstnode = insert;
	
    return OK;
}
 
/* 建立有Nv个顶点Ne条边的图 */
LGraph BuildGraph()
{
    int Nv;
    Vertex i;
    LGraph graph;
    Edge edge;
    
    scanf("%d", &Nv);
    graph = CreateGraph(Nv);
    scanf("%d", &graph->Ne);
    
    for(i = 0; i < graph->Ne; i++) {
        scanf("%d %d %d", &edge.head, &edge.rear, &edge.weight);
        InsertEdge(graph, edge);
    }
    
    return graph;
}
 
int main()
{
    LGraph graph;
 
    graph = BuildGraph();
 
    system("pause");
    return 0;
}