首页 > 代码库 > 图的存储形式——邻接矩阵(数组)

图的存储形式——邻接矩阵(数组)

2024-07-09 08:50:23   224人阅读

邻接矩阵：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。
比如考虑下面这个有向图：

如果用邻接矩阵存储可以表示为：
1.顶点数组：

2.邻接矩阵：

图的遍历：
深度优先（DFS）：
深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有顶点未曾访问过，则深度优先搜索可从图中的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中还有顶点未访问，则另选图中未访问的顶点作为起始点，重复上述过程，直至所有顶点被访问。
上图深度优先遍历结果：abcdfeghi
广度优先（BFS）：
广度优先搜索类似于树的层次遍历。假设从图中某顶点v出发，在访问了v之后，依次访问v的各个未曾访问的邻接点，然后分别从这些邻接点触发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时仍有顶点没访问，另选图中未访问的顶点作为起始点，重复上述过程，直至所有顶点被访问。
上图广度优先遍历结果：abgcehidf

具体实现:
/************************************
图的邻接矩阵(数组)表示
by Rowandjj
2014/6/22
************************************/

#include<iostream>
using namespace std;

#define INFINTY_INT_MAX  0x7fffffff    //代表正无穷
#define MAX_VERTIEX_NUM 20    //最大顶点个数
#define MAX_INFO 20

typedef enum{DG,DN,AG,AN}GraphKind;//有向图、有向网、无向图、无向网

typedef struct
{
    int adj;//顶点关系类型
    char *info;//该弧的相关信息
}ArcCell,AdjMatrix[MAX_VERTIEX_NUM][MAX_VERTIEX_NUM];


typedef struct 
{
    char vexs[MAX_VERTIEX_NUM];//顶点向量
    AdjMatrix arcs;//邻接矩阵
    int vexnum,arcnum;//顶点数、弧数
    GraphKind kind;//种类
}MGraph,*pMGraph;


bool visited[MAX_VERTIEX_NUM];//访问标志数组(全局)
bool (*VisitFunc)(char);

bool Visit(char v)
{
    cout<<v;    
    return true;
}
//----------------操作-------------------------------
int LocateVex(MGraph G,char u);//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1
bool CreateDG(pMGraph G);//创建有向图
bool CreateDN(pMGraph G);//创建有向网
bool CreateAG(pMGraph G);//创建无向图
bool CreateAN(pMGraph G);//创建无向网

bool CreateGraph(pMGraph G);//构造图
void DestroyGraph(pMGraph G);//销毁图G
char GetVex(MGraph G,int v);//初始条件: 图G存在，v是G中某个顶点的序号。操作结果: 返回v的值
bool PutVex(pMGraph G,char v,char iValue);//初始条件: 图G存在，v是G中某个顶点。操作结果: 对v赋新值value
int FirstAdjVex(MGraph G,char v);//返回v的第一个邻接顶点的序号
int NextAdjVex(MGraph G,char v,char w);//返回v的(相对于w的)下一个邻接顶点的序号,否则返回-1
void InsertVex(pMGraph G,char v);//在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做)
bool DeleteVex(pMGraph G,char v);//删除G中顶点v及其相关的弧
bool InsertArc(pMGraph G,char v,char w);//在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>
bool DeleteArc(pMGraph G,char v,char w);//在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>

void DFSTravel(MGraph G,bool (*Visit)(char));//深度优先
void DFS(MGraph G,int v);
void BFSTravel(MGraph G,bool (*Visit)(char));//广度优先
void Display(MGraph G);

//----------------辅助队列--------------------------

typedef struct _QUEUENODE_
{
    int data;
    struct _QUEUENODE_ *next;
}QueueNode,*pQueueNode;

typedef struct _QUEUE_
{
    int size;
    pQueueNode pHead;
    pQueueNode pTail;
}Queue,*pQueue;

bool InitQueue(pQueue Q);
bool DestroyQueue(pQueue Q);
bool DeQueue(pQueue Q,int* e);
bool EnQueue(pQueue Q, int e);
bool QueueEmpty(Queue Q);
//------------------------------------------
bool InitQueue(pQueue Q)
{
    Q->pHead = Q->pTail = (pQueueNode)malloc(sizeof(QueueNode));
    if(!Q->pHead)
    {
        return false;
    }
    Q->pHead->next = NULL;
    Q->size = 0;
    return true;
}

bool DestroyQueue(pQueue Q)
{
    pQueueNode pTemp = Q->pHead->next;
    while(pTemp != NULL)
    {
        Q->pHead->next = pTemp->next;
        free(pTemp);
        pTemp = Q->pHead->next;
    }
    free(Q->pHead);
    Q->size = 0;
    return true;
}
bool QueueEmpty(Queue Q)
{
    return Q.size == 0;
}

bool DeQueue(pQueue Q,int* e)
{
    pQueueNode pDel = Q->pHead->next;
    if(pDel != NULL)
    {
        *e = pDel->data;
        Q->pHead->next = pDel->next;
        if(Q->pTail == pDel)
        {
            Q->pTail = Q->pHead;
        }
        free(pDel);
        Q->size--;
    }
    return true;
}
bool EnQueue(pQueue Q, int e)
{
    pQueueNode pNew = (pQueueNode)malloc(sizeof(QueueNode));
    if(!pNew)
    {
        return false;
    }
    pNew->next = NULL;
    pNew->data = http://www.mamicode.com/e;>
测试：


联系
我们