程序员经验分享-hwhale

数据结构图的建立和遍历（邻接表、邻接矩阵）

2023-05-16

以本代码为基础增加了对图的最短路径计算,路径记录,交互界面等功能,增加代码请看
数据结构课程设计——图的建立和遍历(邻接矩阵+邻接表)和最短路径dijkstra路径记录

首先是图的存储结构：

一、邻接矩阵存储方式实现

邻接矩阵存储的结构体中，包括一个存储边的结构体，存储每条边的信息(权值)
将这个边的结构体的二维数组作为图的基本存储结构，放到单个图的结构体中
每个图又包含总节点数、总边数、图的类型等信息
最下方定义一个遍历操作图的函数

#include<iostream>
#include<stdio.h>
#include<string>
#include<queue>
#include<string.h>
#define INFINITY 0X7fffffff
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
using namespace std;
#define MAX_VERTEX_NUM 30
typedef char InfoType;
typedef int Status;
typedef int Boolean;
typedef string VertexType;
typedef enum {DG,DN,UDG,UDN} GraphKind;
Boolean visited[MAX_VERTEX_NUM];
typedef struct ArcCell///弧(邻接矩阵)
{
    int adj;
    InfoType *info;
} ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct///图(邻接矩阵)
{
    string vexs[MAX_VERTEX_NUM];///结点名
    AdjMatrix arcs;             ///邻接矩阵
    int vexnum,arcnum;          ///结点数，弧数
    GraphKind kind;
} MGraph;
Status (*VisitFunc)(MGraph G,int v);

建图，以建立无向无权图为例：
首先输入该图的总结点数、总边数、是否包含信息
然后对于每个标号输入该标号(结点)的命名

Status CreateUDG(MGraph &G)///邻接矩阵(建立无权无向图)
{
    int IncInfo;
    printf("建立无权无向图，请依次输入总结点数、总边数、是否包含信息:\n");
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);
    printf("请为从1至n个结点命名:\n");
    for(int i=0; i<G.vexnum; i++)cin>>G.vexs[i];
    for(int i=0; i<G.vexnum; i++)
        for(int j=0; j<G.vexnum; j++)G.arcs[i][j].adj=INFINITY,G.arcs[i][j].info=NULL;
    string v1,v2;
    printf("请输入%d组相互依附的两结点:\n",G.arcnum);
    for(int k=0; k<G.arcnum; k++)
    {
        cin>>v1>>v2;
        int i=LocateVex(G,v1);
        int j=LocateVex(G,v2);
        G.arcs[i][j].adj=TRUE;///无权
        if(IncInfo)scanf("%s",G.arcs[i][j].info);
        G.arcs[j][i]=G.arcs[i][j];///无向图,结构体赋值
    }
    return OK;
}

对图的基本操作：根据结点名获取结点的存储位置(邻接矩阵中的标号)

Status LocateVex(MGraph G,string name)///获取结点标号
{
    for(int i=0; i<G.vexnum; i++)
        if(name==G.vexs[i])return i;
    return -1;
}

利用DFS(深度优先搜索)遍历顺序遍历图
输入一个起始搜索点作为遍历的起点，若是一个连通图，一遍搜索即可
否则对于剩下未被标记的结点，作为一个新的连通图进行搜索

void DFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v))
{
    VisitFunc=Visit;
    printf("请输入深度优先搜索起始结点:\n");
    for(int v=0; v<G.vexnum; v++)visited[v]=FALSE;
    string st;
    cin>>st;
    int tmp=LocateVex(G,st);
    printf("深度优先搜索遍历序列:\n");
    DFS(G,tmp);
    for(int v=0; v<G.vexnum; v++)if(!visited[v])DFS(G,v);
    printf("\n");
}

void DFS(MGraph G,int v)///邻接矩阵DFS
{
    visited[v]=TRUE;
    VisitFunc(G,v);
    for(int w=0; w<G.vexnum; w++)
        if(G.arcs[v][w].adj!=INFINITY&&!visited[w])DFS(G,w);
}

利用BFS(广度优先搜索)顺序遍历图
利用队列，遍历每个当前结点可以到达的结点，将下一个可以到达的结点放入队列中作为搜索的候选项，这样不断放入可以达到的结点，不短弹出队首结点以连接投入新的可到达节点放入队列中

void BFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v))///邻接矩阵BFS
{
    for(int v=0; v<G.vexnum; v++)visited[v]=FALSE;
    queue<int>Q;
    printf("请输入广度优先搜索起始结点:\n");
    string st;
    cin>>st;
    printf("广度优先搜索遍历序列:\n");
    int temp=LocateVex(G,st);
    Visit(G,temp);
    Q.push(temp);
    visited[temp]=TRUE;
    while(!Q.empty())
    {
        int tmp=Q.front();
        Q.pop();
        for(int w=0; w<G.vexnum; w++)
        {
            if(!visited[w]&&G.arcs[tmp][w].adj!=INFINITY)
            {
                visited[w]=TRUE;
                Visit(G,w);
                Q.push(w);
            }
        }
    }
    for(int v=0; v<G.vexnum; v++)///剩余连通分量
    {
        if(!visited[v])
        {
            visited[v]=TRUE;
            Visit(G,v);
            Q.push(v);
            while(!Q.empty())
            {
                int tmp=Q.front();
                Q.pop();
                for(int w=0; w<G.vexnum; w++)
                {
                    if(!visited[w]&&G.arcs[tmp][w].adj!=INFINITY)
                    {
                        visited[w]=TRUE;
                        Visit(G,w);
                        Q.push(w);
                    }
                }
            }
        }
    }
    printf("\n");
}

遍历(以输出结点名为例)图

Status visit(MGraph G,int v)///邻接矩阵遍历
{
    cout<<G.vexs[v]<<' ';
}

完整代码，数据结构作业模板，存档用

#include<iostream>
#include<stdio.h>
#include<string>
#include<queue>
#include<string.h>
#define INFINITY 0X7fffffff
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
using namespace std;
#define MAX_VERTEX_NUM 30
typedef char InfoType;
typedef int Status;
typedef int Boolean;
typedef string VertexType;
typedef enum {DG,DN,UDG,UDN} GraphKind;
Boolean visited[MAX_VERTEX_NUM];
typedef struct ArcCell///弧(邻接矩阵)
{
    int adj;
    InfoType *info;
} ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct///图(邻接矩阵)
{
    string vexs[MAX_VERTEX_NUM];///结点名
    AdjMatrix arcs;             ///邻接矩阵
    int vexnum,arcnum;          ///结点数，弧数
    GraphKind kind;
} MGraph;
Status (*VisitFunc)(MGraph G,int v);

Status LocateVex(MGraph G,string name)///获取结点标号
{
    for(int i=0; i<G.vexnum; i++)
        if(name==G.vexs[i])return i;
    return -1;
}

Status CreateDG(MGraph &G)///邻接矩阵(建立无权有向图)
{
    int IncInfo;
    printf("建立无权有向图，请依次输入总结点数、总边数、是否包含信息:\n");
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);
    printf("请为从1至n个结点命名:\n");
    for(int i=0; i<G.vexnum; i++)cin>>G.vexs[i];
    for(int i=0; i<G.vexnum; i++)
        for(int j=0; j<G.vexnum; j++)G.arcs[i][j].adj=INFINITY,G.arcs[i][j].info=NULL;
    string v1,v2;
    printf("请输入%d组由左指向右的有向边:\n",G.arcnum);
    for(int k=0; k<G.arcnum; k++)
    {
        cin>>v1>>v2;
        int i=LocateVex(G,v1);
        int j=LocateVex(G,v2);
        G.arcs[i][j].adj=TRUE;///无权
        if(IncInfo)scanf("%s",G.arcs[i][j].info);
    }
    return OK;
}

Status CreateDN(MGraph &G)///邻接矩阵(建立带权有向网)
{
    int IncInfo;
    printf("建立带权有向网，请依次输入总结点数、总边数、是否包含信息:\n");
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);
    printf("请为从1至n个结点命名:\n");
    for(int i=0; i<G.vexnum; i++)cin>>G.vexs[i];
    for(int i=0; i<G.vexnum; i++)
        for(int j=0; j<G.vexnum; j++)G.arcs[i][j].adj=INFINITY,G.arcs[i][j].info=NULL;
    string v1,v2;
    int w;
    printf("请输入%d组由左指向右的有向边与边权:\n",G.arcnum);
    for(int k=0; k<G.arcnum; k++)
    {
        cin>>v1>>v2>>w;
        int i=LocateVex(G,v1);
        int j=LocateVex(G,v2);
        G.arcs[i][j].adj=w;///带权
        if(IncInfo)scanf("%s",G.arcs[i][j].info);
    }
    return OK;
}

Status CreateUDG(MGraph &G)///邻接矩阵(建立无权无向图)
{
    int IncInfo;
    printf("建立无权无向图，请依次输入总结点数、总边数、是否包含信息:\n");
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);
    printf("请为从1至n个结点命名:\n");
    for(int i=0; i<G.vexnum; i++)cin>>G.vexs[i];
    for(int i=0; i<G.vexnum; i++)
        for(int j=0; j<G.vexnum; j++)G.arcs[i][j].adj=INFINITY,G.arcs[i][j].info=NULL;
    string v1,v2;
    printf("请输入%d组相互依附的两结点:\n",G.arcnum);
    for(int k=0; k<G.arcnum; k++)
    {
        cin>>v1>>v2;
        int i=LocateVex(G,v1);
        int j=LocateVex(G,v2);
        G.arcs[i][j].adj=TRUE;///无权
        if(IncInfo)scanf("%s",G.arcs[i][j].info);
        G.arcs[j][i]=G.arcs[i][j];///无向图,结构体赋值
    }
    return OK;
}

Status CreateUDN(MGraph &G)///邻接矩阵(建立带权无向网)
{
    int IncInfo;
    printf("建立带权无向网，请依次输入总结点数、总边数、是否包含信息:\n");
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);
    printf("请为从1至n个结点命名:\n");
    for(int i=0; i<G.vexnum; i++)cin>>G.vexs[i];
    for(int i=0; i<G.vexnum; i++)
        for(int j=0; j<G.vexnum; j++)G.arcs[i][j].adj=INFINITY,G.arcs[i][j].info=NULL;
    string v1,v2;
    printf("请输入%d组相互依附的两结点与边权:\n",G.arcnum);
    int w;///边权
    for(int k=0; k<G.arcnum; k++)
    {
        cin>>v1>>v2>>w;
        int i=LocateVex(G,v1);
        int j=LocateVex(G,v2);
        G.arcs[i][j].adj=w;///带权
        if(IncInfo)scanf("%s",G.arcs[i][j].info);
        G.arcs[j][i]=G.arcs[i][j];///无向图,结构体赋值
    }
    return OK;
}

void DFS(MGraph G,int v)///邻接矩阵DFS
{
    visited[v]=TRUE;
    VisitFunc(G,v);
    for(int w=0; w<G.vexnum; w++)
        if(G.arcs[v][w].adj!=INFINITY&&!visited[w])DFS(G,w);
}

void DFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v))
{
    VisitFunc=Visit;
    printf("请输入深度优先搜索起始结点:\n");
    for(int v=0; v<G.vexnum; v++)visited[v]=FALSE;
    string st;
    cin>>st;
    int tmp=LocateVex(G,st);
    printf("深度优先搜索遍历序列:\n");
    DFS(G,tmp);
    for(int v=0; v<G.vexnum; v++)if(!visited[v])DFS(G,v);
    printf("\n");
}

void BFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v))///邻接矩阵BFS
{
    for(int v=0; v<G.vexnum; v++)visited[v]=FALSE;
    queue<int>Q;
    printf("请输入广度优先搜索起始结点:\n");
    string st;
    cin>>st;
    printf("广度优先搜索遍历序列:\n");
    int temp=LocateVex(G,st);
    Visit(G,temp);
    Q.push(temp);
    visited[temp]=TRUE;
    while(!Q.empty())
    {
        int tmp=Q.front();
        Q.pop();
        for(int w=0; w<G.vexnum; w++)
        {
            if(!visited[w]&&G.arcs[tmp][w].adj!=INFINITY)
            {
                visited[w]=TRUE;
                Visit(G,w);
                Q.push(w);
            }
        }
    }
    for(int v=0; v<G.vexnum; v++)///剩余连通分量
    {
        if(!visited[v])
        {
            visited[v]=TRUE;
            Visit(G,v);
            Q.push(v);
            while(!Q.empty())
            {
                int tmp=Q.front();
                Q.pop();
                for(int w=0; w<G.vexnum; w++)
                {
                    if(!visited[w]&&G.arcs[tmp][w].adj!=INFINITY)
                    {
                        visited[w]=TRUE;
                        Visit(G,w);
                        Q.push(w);
                    }
                }
            }
        }
    }
    printf("\n");
}

Status CreateGraph(MGraph &G)///邻接矩阵
{
    printf("请输入建图类型(1:无权有向图、2:带权有向网、3:无权无向图、4:带权无向网):\n");
    scanf("%d",&G.kind);///输入图的种类
    switch(G.kind-1)
    {
    case DG:
        return CreateDG(G);
    case DN:
        return CreateDN(G);
    case UDG:
        return CreateUDG(G);
    case UDN:
        return CreateUDN(G);
    default:
        return ERROR;
    }
}

Status visit(MGraph G,int v)///邻接矩阵遍历
{
    cout<<G.vexs[v]<<' ';
}

int main()
{
    while(true)
    {
        MGraph G1;
        CreateGraph(G1);///邻接矩阵
        DFSTraverse(G1,visit);///深搜邻接矩阵
        BFSTraverse(G1,visit);///广搜邻接矩阵
    }
}
/*
3

8 9

V1 V2 V3 V4 V5 V6 V7 V8

V1 V2
V2 V4
V4 V8
V8 V5
V2 V5
V1 V3
V3 V6
V3 V7
V6 V7
*/

二、邻接表存储方式实现

邻接表存储方式相比邻接矩阵的方式节省了很多存储空间，有多少条边就用到了多少空间，不会像邻接矩阵一样浪费很多权值为无限或零(两结点不相通)的情况
邻接矩阵的基本原理是构造n个链表，n指结点数量，每个结点形成的链表表示该结点可以到达的所有结点，每个链表中的结点数目表示从该链表头结点出发，到达其他结点的边的条数。
在DFS和BFS过程中，每次从一个结点出发，判断有哪些可以到达的结点时，不在遍历所有结点以判断两结点之间的关系，而是直接取出该结点可以到达的几个结点进行深搜或放入队列，时间复杂度也降降低。

首先是建图：
包括每个弧的结构体，将存储从头结点指向的某个可达到结点的位置。以及一个指针指向下一个头结点可以到达的结点所形成的弧

第二个结构体表示每个结点(链表的头结点)
存储了该结点的命名以及第一个该点连接的边

第三个结构体表示一个图，该结构体存储了图中所有链表的头结点(数组)，以及图的基本信息：结点数量，边的数量

#include<iostream>
#include<stdio.h>
#include<string>
#include<queue>
#include<string.h>
#define INFINITY 0X7fffffff
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
using namespace std;
#define MAX_VERTEX_NUM 30
typedef char InfoType;
typedef int Status;
typedef int Boolean;
typedef string VertexType;
typedef enum {DG,DN,UDG,UDN} GraphKind;
Boolean visited[MAX_VERTEX_NUM];
typedef struct ArcNode///弧(邻接表)
{
    int adjvex;             ///当前弧指向的顶点
    int info;               ///权值
    struct ArcNode *nextarc;///下一条当前顶点为出度的弧
} ArcNode;

typedef struct VNode///点(邻接表)
{
    VertexType data;///结点名
    ArcNode *firstarc;///该点的第一条出边
} VNode,AdjList[MAX_VERTEX_NUM];

typedef struct///图(邻接表)
{
    AdjList vertices;///点的邻接表(数组)
    int vexnum,arcnum;
    int kind;
} ALGraph;
Status (*VisitFunc_2)(ALGraph G,int v);

建立邻接表：

方式①：按结点存储标号从大到小的顺序建立邻接表
因为邻接表存储的是该结点依附的所有边，这些边都是同等优先级的，先遍历谁并没有什么不同，那么就有按输入顺序建图和按一定规律标准建图两种方式，这段代码表示的是，无论输入顺序如何，邻接表的存储形式都是按一定规定顺序的，同一张图按不同的边关系输入顺序，遍历和存储的序列都将固定

void ArcAdd_sort(ALGraph &G,int v1,int v2,int w)///从大到小顺序建立邻接表
{
    ArcNode *p,*h,*q;
    p=new ArcNode;
    p->adjvex=v2;
    p->info=w;
    p->nextarc=NULL;
    h=q=G.vertices[v1].firstarc;
    if(q==NULL)G.vertices[v2].firstarc=p;
    else
    {
        if(p->adjvex > q->adjvex)///邻接表按结点序号从大到小排列
        {
            p->nextarc=q;
            G.vertices[v2].firstarc=p;
        }
        else
        {
            while(G.vertices[v2].firstarc!=NULL&&q->nextarc!=NULL&&p->adjvex < q->adjvex)
            {
                h=q;
                q=q->nextarc;
            }
            if(q->nextarc==NULL&&p->adjvex < q->adjvex) q->nextarc=p;
            else
            {
                p->nextarc=q;
                h->nextarc=p;
            }
        }
    }
}

方式②：按一般随机输入方式建图，不存在规律，根据输入顺序的不同，存储的顺序也不同，遍历的顺序也随之改变，但都一定正确，只是多种遍历顺序中的其中一种序列。无优先级。

void ArcAdd(ALGraph &G,int v1,int v2,int w)///加边
{
    ArcNode *p,*q;
    p=new ArcNode;
    p->adjvex=v2;
    p->info=w;
    p->nextarc=NULL;
    q=G.vertices[v1].firstarc;
    if(q==NULL) G.vertices[v1].firstarc=p;///若第一条依附v2顶点的弧还未存在，新加入的边作为第一条依附弧
    else///否则顺着链表向后查找
    {
        while(q->nextarc!=NULL) q=q->nextarc;
        q->nextarc=p;
    }
}

对图的基本操作，获取每个结点对应的存储位置标号

int LocateVex_2(ALGraph G,string name)///获取结点标号
{
    for(int i=0; i<G.vexnum; i++)
        if(name==G.vertices[i].data)return i;
    return -1;
}
```c

## 建图(以建立无权无向图为例)

```c
Status CreateUDG_2(ALGraph &G)///邻接表(建立无权无向图)
{
    printf("建立无权无向图，请依次输入总结点数、总边数:\n");
    scanf("%d%d",&G.vexnum,&G.arcnum);
    printf("请为从1至n个结点命名:\n");
    for(int i=0; i<G.vexnum; i++)cin>>G.vertices[i].data,G.vertices[i].firstarc=NULL;
    string v1,v2;
    printf("请输入%d组相互依附的两结点:\n",G.arcnum);
    for(int k=0; k<G.arcnum; k++)
    {
        cin>>v1>>v2;
        int i=LocateVex_2(G,v1);///获取标号
        int j=LocateVex_2(G,v2);
        ArcAdd(G,i,j,1);///无向边
        ArcAdd(G,j,i,1);
    }
    return OK;
}

遍历每个节点的邻接表的基础操作：
因为利用邻接表存储结点间的关系，那么就不能像邻接矩阵一样用for循环遍历二维数组
而是用指针传递的方式遍历每一条边和结点，这里有两个函数，一个是获取某结点的头指针。
一个是获取某结点的下一条(next)边信息

int FirstAdjVex(ALGraph G,int v)
{
    if(G.vertices[v].firstarc) return G.vertices[v].firstarc->adjvex;
    return -1;
}
int NextAdjVex(ALGraph G,int v,int w)
{
    ArcNode *p=G.vertices[v].firstarc;
    while(p->adjvex!=w&&p->nextarc!=NULL)p=p->nextarc;
    if(p->nextarc==NULL)return -1;
    return p->nextarc->adjvex;
}

有了以上基础操作，可以利用这些操作实现DFS(深度优先搜索)遍历和BFS(广度优先搜索)遍历的操作

深度优先遍历(DFS)：

void DFSTraverse_2(ALGraph G,Status (*Visit)(ALGraph G,int v))
{
    VisitFunc_2=Visit;
    printf("请输入深度优先搜索起始结点:\n");
    for(int v=0; v<G.vexnum; v++)visited[v]=FALSE;
    string st;
    cin>>st;
    int tmp=LocateVex_2(G,st);
    printf("深度优先搜索遍历序列:\n");
    DFS_2(G,tmp);
    for(int v=0; v<G.vexnum; v++)if(!visited[v])DFS_2(G,v);
    printf("\n");
}

void DFS_2(ALGraph G,int v)///邻接表DFS
{
    visited[v]=TRUE;
    VisitFunc_2(G,v);
    for(int w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
        if(!visited[w])DFS_2(G,w);
}

广度优先遍历(BFS)：

void BFSTraverse_2(ALGraph G,Status (*Visit)(ALGraph G,int v))///邻接表BFS
{
    for(int v=0; v<G.vexnum; v++)visited[v]=FALSE;
    queue<int>Q;
    printf("请输入广度优先搜索起始结点:\n");
    string st;
    cin>>st;
    printf("广度优先搜索遍历序列:\n");
    int temp=LocateVex_2(G,st);
    Visit(G,temp);
    Q.push(temp);
    visited[temp]=TRUE;
    while(!Q.empty())
    {
        int tmp=Q.front();
        Q.pop();
        for(int w=FirstAdjVex(G,tmp); w>=0; w=NextAdjVex(G,tmp,w))
        {
            if(!visited[w])
            {
                visited[w]=TRUE;
                Visit(G,w);
                Q.push(w);
            }
        }
    }
    for(int v=0; v<G.vexnum; v++)///剩余连通分量
    {
        if(!visited[v])
        {
            visited[v]=TRUE;
            Visit(G,v);
            Q.push(v);
            while(!Q.empty())
            {
                int tmp=Q.front();
                Q.pop();
                for(int w=FirstAdjVex(G,tmp); w>=0; w=NextAdjVex(G,tmp,w))
                {
                    if(!visited[w])
                    {
                        visited[w]=TRUE;
                        Visit(G,w);
                        Q.push(w);
                    }
                }
            }
        }
    }
    printf("\n");
}

邻接表的结构输出

为了更清楚的看到邻接表的存储结构，可以输出邻接表以理解该表的存储方式

void PrintGraph(ALGraph G)///输出邻接表
{
    cout<<"图的创建完成,该图的邻接表表示为:"<<endl;
    ArcNode *p;
    for(int i=0; i<G.vexnum; i++)
    {
        if(G.vertices[i].firstarc == NULL)
            cout<<i<<":"<<G.vertices[i].data<<"-->NULL"<<endl;
        else
        {
            p = G.vertices[i].firstarc;
            cout<<i<<":"<<G.vertices[i].data<<"-->";
            while(p->nextarc!=NULL)
            {
                cout<<p->adjvex<<"-->";
                p = p->nextarc;
            }
            cout<<p->adjvex<<"-->NULL"<<endl;
        }
    }
}

遍历(以输出操作为例)图

Status visit_2(ALGraph G,int v)///邻接表遍历
{
    cout<<G.vertices[v].data<<' ';
}

完整邻接表方式建图遍历图代码

#include<iostream>
#include<stdio.h>
#include<string>
#include<queue>
#include<string.h>
#define INFINITY 0X7fffffff
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
using namespace std;
#define MAX_VERTEX_NUM 30
typedef char InfoType;
typedef int Status;
typedef int Boolean;
typedef string VertexType;
typedef enum {DG,DN,UDG,UDN} GraphKind;
typedef struct ArcNode///弧(邻接表)
{
    int adjvex;             ///当前弧指向的顶点
    int info;               ///权值
    struct ArcNode *nextarc;///下一条当前顶点为出度的弧
} ArcNode;

typedef struct VNode///点(邻接表)
{
    VertexType data;///结点名
    ArcNode *firstarc;///该点的第一条出边
} VNode,AdjList[MAX_VERTEX_NUM];

typedef struct///图(邻接表)
{
    AdjList vertices;///点的邻接表(数组)
    int vexnum,arcnum;
    int kind;
} ALGraph;
Status (*VisitFunc_2)(ALGraph G,int v);

void ArcAdd_sort(ALGraph &G,int v1,int v2,int w)///从大到小顺序建立邻接表
{
    ArcNode *p,*h,*q;
    p=new ArcNode;
    p->adjvex=v2;
    p->info=w;
    p->nextarc=NULL;
    h=q=G.vertices[v1].firstarc;
    if(q==NULL)G.vertices[v2].firstarc=p;
    else
    {
        if(p->adjvex > q->adjvex)///邻接表按结点序号从大到小排列
        {
            p->nextarc=q;
            G.vertices[v2].firstarc=p;
        }
        else
        {
            while(G.vertices[v2].firstarc!=NULL&&q->nextarc!=NULL&&p->adjvex < q->adjvex)
            {
                h=q;
                q=q->nextarc;
            }
            if(q->nextarc==NULL&&p->adjvex < q->adjvex) q->nextarc=p;
            else
            {
                p->nextarc=q;
                h->nextarc=p;
            }
        }
    }
}

void ArcAdd(ALGraph &G,int v1,int v2,int w)///加边
{
    ArcNode *p,*q;
    p=new ArcNode;
    p->adjvex=v2;
    p->info=w;
    p->nextarc=NULL;
    q=G.vertices[v1].firstarc;
    if(q==NULL) G.vertices[v1].firstarc=p;///若第一条依附v2顶点的弧还未存在，新加入的边作为第一条依附弧
    else///否则顺着链表向后查找
    {
        while(q->nextarc!=NULL) q=q->nextarc;
        q->nextarc=p;
    }
}

int LocateVex_2(ALGraph G,string name)///获取结点标号
{
    for(int i=0; i<G.vexnum; i++)
        if(name==G.vertices[i].data)return i;
    return -1;
}

Status CreateDG_2(ALGraph &G)///邻接表(建立无权有向图)
{
    printf("建立无权有向图，请依次输入总结点数、总边数:\n");
    scanf("%d%d",&G.vexnum,&G.arcnum);
    printf("请为从1至n个结点命名:\n");
    for(int i=0; i<G.vexnum; i++)cin>>G.vertices[i].data,G.vertices[i].firstarc=NULL;
    string v1,v2;
    printf("请输入%d组由左指向右的有向边:\n",G.arcnum);
    for(int k=0; k<G.arcnum; k++)
    {
        cin>>v1>>v2;
        int i=LocateVex_2(G,v1);///获取标号
        int j=LocateVex_2(G,v2);
        ArcAdd(G,i,j,1);
    }
    return OK;
}

Status CreateDN_2(ALGraph &G)///邻接表(建立带权有向网)
{
    printf("建立带权有向网，请依次输入总结点数、总边数:\n");
    scanf("%d%d",&G.vexnum,&G.arcnum);
    printf("请为从1至n个结点命名:\n");
    for(int i=0; i<G.vexnum; i++)cin>>G.vertices[i].data,G.vertices[i].firstarc=NULL;
    string v1,v2;
    int w;
    printf("请输入%d组由左指向右的有向边与边权:\n",G.arcnum);
    for(int k=0; k<G.arcnum; k++)
    {
        cin>>v1>>v2>>w;
        int i=LocateVex_2(G,v1);///获取标号
        int j=LocateVex_2(G,v2);
        ArcAdd(G,i,j,w);
    }
    return OK;
}

Status CreateUDG_2(ALGraph &G)///邻接表(建立无权无向图)
{
    printf("建立无权无向图，请依次输入总结点数、总边数:\n");
    scanf("%d%d",&G.vexnum,&G.arcnum);
    printf("请为从1至n个结点命名:\n");
    for(int i=0; i<G.vexnum; i++)cin>>G.vertices[i].data,G.vertices[i].firstarc=NULL;
    string v1,v2;
    printf("请输入%d组相互依附的两结点:\n",G.arcnum);
    for(int k=0; k<G.arcnum; k++)
    {
        cin>>v1>>v2;
        int i=LocateVex_2(G,v1);///获取标号
        int j=LocateVex_2(G,v2);
        ArcAdd(G,i,j,1);///无向边
        ArcAdd(G,j,i,1);
    }
    return OK;
}

Status CreateUDN_2(ALGraph &G)///邻接表(建立带权无向网)
{
    printf("建立带权无向网，请依次输入总结点数、总边数:\n");
    scanf("%d%d",&G.vexnum,&G.arcnum);
    printf("请为从1至n个结点命名:\n");
    for(int i=0; i<G.vexnum; i++)cin>>G.vertices[i].data,G.vertices[i].firstarc=NULL;
    string v1,v2;
    int w;
    printf("请输入%d组相互依附的两结点与边权:\n",G.arcnum);
    for(int k=0; k<G.arcnum; k++)
    {
        cin>>v1>>v2>>w;
        int i=LocateVex_2(G,v1);///获取标号
        int j=LocateVex_2(G,v2);
        ArcAdd(G,i,j,w);///无向边
        ArcAdd(G,j,i,w);
    }
    return OK;
}

int FirstAdjVex(ALGraph G,int v)
{
    if(G.vertices[v].firstarc) return G.vertices[v].firstarc->adjvex;
    return -1;
}
int NextAdjVex(ALGraph G,int v,int w)
{
    ArcNode *p=G.vertices[v].firstarc;
    while(p->adjvex!=w&&p->nextarc!=NULL)p=p->nextarc;
    if(p->nextarc==NULL)return -1;
    return p->nextarc->adjvex;
}

void DFS_2(ALGraph G,int v)///邻接表DFS
{
    visited[v]=TRUE;
    VisitFunc_2(G,v);
    for(int w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
        if(!visited[w])DFS_2(G,w);
}

void DFSTraverse_2(ALGraph G,Status (*Visit)(ALGraph G,int v))
{
    VisitFunc_2=Visit;
    printf("请输入深度优先搜索起始结点:\n");
    for(int v=0; v<G.vexnum; v++)visited[v]=FALSE;
    string st;
    cin>>st;
    int tmp=LocateVex_2(G,st);
    printf("深度优先搜索遍历序列:\n");
    DFS_2(G,tmp);
    for(int v=0; v<G.vexnum; v++)if(!visited[v])DFS_2(G,v);
    printf("\n");
}

void BFSTraverse_2(ALGraph G,Status (*Visit)(ALGraph G,int v))///邻接表BFS
{
    for(int v=0; v<G.vexnum; v++)visited[v]=FALSE;
    queue<int>Q;
    printf("请输入广度优先搜索起始结点:\n");
    string st;
    cin>>st;
    printf("广度优先搜索遍历序列:\n");
    int temp=LocateVex_2(G,st);
    Visit(G,temp);
    Q.push(temp);
    visited[temp]=TRUE;
    while(!Q.empty())
    {
        int tmp=Q.front();
        Q.pop();
        for(int w=FirstAdjVex(G,tmp); w>=0; w=NextAdjVex(G,tmp,w))
        {
            if(!visited[w])
            {
                visited[w]=TRUE;
                Visit(G,w);
                Q.push(w);
            }
        }
    }
    for(int v=0; v<G.vexnum; v++)///剩余连通分量
    {
        if(!visited[v])
        {
            visited[v]=TRUE;
            Visit(G,v);
            Q.push(v);
            while(!Q.empty())
            {
                int tmp=Q.front();
                Q.pop();
                for(int w=FirstAdjVex(G,tmp); w>=0; w=NextAdjVex(G,tmp,w))
                {
                    if(!visited[w])
                    {
                        visited[w]=TRUE;
                        Visit(G,w);
                        Q.push(w);
                    }
                }
            }
        }
    }
    printf("\n");
}

void PrintGraph(ALGraph G)///输出邻接表
{
    cout<<"图的创建完成,该图的邻接表表示为:"<<endl;
    ArcNode *p;
    for(int i=0; i<G.vexnum; i++)
    {
        if(G.vertices[i].firstarc == NULL)
            cout<<i<<":"<<G.vertices[i].data<<"-->NULL"<<endl;
        else
        {
            p = G.vertices[i].firstarc;
            cout<<i<<":"<<G.vertices[i].data<<"-->";
            while(p->nextarc!=NULL)
            {
                cout<<p->adjvex<<"-->";
                p = p->nextarc;
            }
            cout<<p->adjvex<<"-->NULL"<<endl;
        }
    }
}

Status CreateGraph_2(ALGraph &G)///邻接表
{
    printf("请输入建图类型(1:无权有向图、2:带权有向网、3:无权无向图、4:带权无向网):\n");
    scanf("%d",&G.kind);///输入图的种类
    switch(G.kind-1)
    {
    case DG:
        return CreateDG_2(G);
    case DN:
        return CreateDN_2(G);
    case UDG:
        return CreateUDG_2(G);
    case UDN:
        return CreateUDN_2(G);
    default:
        return ERROR;
    }
}


Status visit_2(ALGraph G,int v)///邻接表遍历
{
    cout<<G.vertices[v].data<<' ';
}

int main()
{
    while(true)
    {
        MGraph G1;
        CreateGraph(G1);///邻接矩阵
        DFSTraverse(G1,visit);///深搜邻接矩阵
        BFSTraverse(G1,visit);///广搜邻接矩阵
        ALGraph G2;///邻接表
        CreateGraph_2(G2);
        PrintGraph(G2);///输出邻接表
        DFSTraverse_2(G2,visit_2);///邻接表深搜
        BFSTraverse_2(G2,visit_2);///邻接表广搜
    }
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构图的建立和遍历

邻接矩阵

数据结构图的建立和遍历（邻接表、邻接矩阵） 的相关文章

随机推荐

热门标签