图的遍历，邻接矩阵与邻接表的实现

图没有顺序结构

邻接矩阵

-用于边集合较密集的情况

图结点的定义

#include 
#include 
#include 
#include 
#define ERROR -1
#define MaxVertexNum 100 //最大顶点数设为100
#define INFINITY 65535

typedef int Vertex; //用顶点下标表示顶点
typedef int WeightType;//边的权值设为整型
typedef char DataType;//顶点存储的数据类型设为字符型
typedef int ElementType;
typedef int Position;

typedef struct GNode *PtrToGNode;
struct GNode {
    int Nv; //顶点数
    int Ne; //边数
    WeightType G[MaxVertexNum][MaxVertexNum]; //邻接矩阵
    DataType Data[MaxVertexNum]; //存顶点的数据
    int Visited[MaxVertexNum];
};
typedef PtrToGNode MGraph;

边的定义

typedef struct ENode *PtrToENode;
struct ENode {
    Vertex V1,V2; //有向边
    WeightType Weight; //权重
};
typedef PtrToENode Edge;

邻接矩阵的创建

//初始化一个有VertexNum个顶点但没有边的图
MGraph CreateGraph(int VertexNum)
{
    Vertex V,W;
    MGraph Graph;
    
    Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    
    for(V=0; VNv; V++)
        for(W=0; WNv; W++)
            Graph->G[V][W] = INFINITY;
    
    return Graph;
}

//边的插入
void InsertEdge(MGraph Graph, Edge E)
{
    Graph->G[E->V2][E->V1] = E->Weight;
    Graph->G[E->V1][E->V2] = E->Weight; //无向图
}

//读入图的信息存入邻接矩阵
MGraph BuildGraph()
{
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv,i;
    
    printf("请输入顶点个数：");
    scanf("%d",&Nv); //读入顶点个数
    Graph = CreateGraph(Nv); //初始化图的Ne=0
    
    printf("请输入边数：");
    scanf("%d",&(Graph->Ne)); //读入边数
    if(Graph->Ne!=0) {
        E = (Edge)malloc(sizeof(struct ENode)); //建立边结点
        for(i = 0; iNe; i++) {
            printf("初始化边，请输入：“边的起点，终点和权重(有向图)”");
            scanf("%d %d %d",&E->V1,&E->V2,&E->Weight); //读入边，格式为起点 终点 权重
            InsertEdge(Graph, E); ///插入邻接矩阵
        }
    }
    //如果顶点有数据的话读入数据
    for(V = 0; VNv; V++)
        scanf("%c",&(Graph->Data[V]));
    
    return Graph;
}

深度优先遍历O()

- 树的先序遍历的推广

void Visit(Vertex V)
{
    printf("正在访问顶点%dn",V);
}

void DFS(MGraph Graph, Vertex V)
{
    Vertex W;
    
    Visit(V); //首先访问当前结点
    Graph->Visited[V] = 1;
    
    for (W = 0; W < Graph->Nv; W++) //W的每个邻接点
        if(!Graph->Visited[W] && Graph->G[V][W] 
广度优先遍历——队列实现（队列操作见前） 
- 树的层序遍历的推广 
- O() 
//队列的定义
struct QNode {
    ElementType *Data;  
    Position Front, Rear;   
    int MaxSize;  
};
typedef struct QNode *Queue;

bool IsEdge(MGraph Graph, Vertex V, Vertex W)
{
    return Graph->G[V][W]Visited[S] = 1; //标记S已访问
    AddQ(Q,S); //S入队列
    
    while(!IsEmpty(Q)) {
        V = DeleteQ(Q); //弹出V
        for(W = 0; W < Graph->Nv; W++) //对图中的每个顶点
            if(IsEdge(Graph,V,W) && !Graph->Visited[W]) { //若W是V的邻接点且未访问过
                Visit(W); //访问顶点W
                Graph->Visited[W] = 1; //标记顶点W已访问
                AddQ(Q,W); //W入队列
            }
    }
} 

邻接表 
数据结构定义 
//邻接点结点的定义
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode {
    Vertex AdjV; //邻接点下标
    WeightType Weight; //边权重
    PtrToAdjVNode Next; //不要忘记Next域
};

//顶点表头结点的定义（一维数组）
typedef struct VNode {
    PtrToAdjVNode FirstEdge; //边表头指针，指向第一个邻接点
    DataType Data; //存顶点的数据
}AdjList[MaxVertexNum];

//图的定义
typedef struct GNode *PtrToGNode;
struct GNode {
    int Nv; //顶点数
    int Ne; //边数
    AdjList G; //邻接表表头
    int Visited[MaxVertexNum];
};
typedef PtrToGNode LGraph;

//边的定义
typedef struct ENode *PtrToENode;
struct ENode {
    Vertex V1,V2; //有向边
    WeightType Weight; //权重
};
typedef PtrToENode Edge;
 
邻接表的创建 
//初始化一个有VertexNum个顶点但没有边的图
LGraph CreateGraph(int VertexNum)
{
    Vertex V;
    LGraph Graph;
    
    Graph = (LGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    
    for(V=0; VNv; V++)
        Graph->G[V].FirstEdge = NULL;
    
    return Graph;
}

//插入边
void InsertEdge(LGraph Graph, Edge E)
{
    PtrToAdjVNode NewNode1,NewNode2;
    
    NewNode1 = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode1->AdjV = E->V2;
    NewNode1->Weight = E->Weight;
    NewNode1->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode1;

    //无向图
    NewNode2 = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode2->AdjV = E->V1;
    NewNode2->Weight = E->Weight;
    NewNode2->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode2;
}

//图的建立
LGraph BuildGraph()
{
    LGraph Graph;
    Edge E;
    Vertex V;
    int Nv,i;
    
    printf("请输入顶点个数：");
    scanf("%d",&Nv); //读入顶点个数
    Graph = CreateGraph(Nv); //初始化图的Ne=0
    
    printf("请输入边数：");
    scanf("%d",&(Graph->Ne)); //读入边数
    if(Graph->Ne!=0) {
        E = (Edge)malloc(sizeof(struct ENode)); //建立边结点
        for(i = 0; iNe; i++) {
            printf("初始化边，请输入：“边的起点，终点和权重(有向图)”");
            scanf("%d %d %d",&E->V1,&E->V2,&E->Weight); //读入边，格式为起点 终点 权重
            InsertEdge(Graph, E); ///插入邻接矩阵
        }
    }
    //如果顶点有数据的话读入数据
    for(V = 0; VNv; V++)
        scanf("%c",&(Graph->G[V].Data));
    
    return Graph;
}
 
深度优先遍历O(N+E) 
void Visit(Vertex V)
{
    printf("正在访问顶点%dn",V);
}

void DFS(LGraph Graph, Vertex V)
{
    PtrToAdjVNode W;
    
    Visit(V); //首先访问当前结点
    Graph->Visited[V] = 1;
    
    for (W = Graph->G[V].FirstEdge; W; W = W->Next) //递归访问W每个邻接点
        if(!Graph->Visited[W->AdjV])
            DFS(Graph, W->AdjV);
}
 
广度优先遍历——队列实现 
- O(N+E) 
//队列中结点的定义
struct Node{
    ElementType Data;
    PtrTonode Next;
};
typedef PtrTonode Position;

void BFS(LGraph Graph, Vertex S)
{
    Queue Q;
    Vertex V;
    PtrToAdjVNode W;
    Q = CreateQueue(100);
    Visit(S); //访问顶点S
    Graph->Visited[S] = 1; //标记S已访问
    AddQ(Q,S); //S入队列
    
    while(!IsEmpty(Q)) {
        V = DeleteQ(Q); //弹出V
        for(W = Graph->G[V].FirstEdge; W; W = W->Next) //对图中的每个顶点W
            if(!Graph->Visited[W->AdjV]) { //若W未访问过
                Visit(W->AdjV); //访问顶点W
                Graph->Visited[W->AdjV] = 1; //标记顶点W已访问
                AddQ(Q,W->AdjV); //W入队列
            }
    }
} 
对以上操作的测试 
int main(void)
{
    MGraph Graph;
    Graph = BuildGraph();
    Vertex V = 0;
    
    for(V = 0; VNv; V++)
        Graph->Visited[V] = 0;
    
    DFS(Graph, V);
    BFS(Graph, V);
    
    return 0;
}

图的遍历，邻接矩阵与邻接表的实现

C/C++/C#相关栏目本月热门文章