1.实现图的邻接矩阵和邻接表的存储

图.h的头文件

#ifndef Map
#define Map

#include
#include
#include
using namespace std;
#define MAXV 100         //定义最大顶点数
#define INF 65535   //用65535来表示无穷大
typedef char InfoTpye;
//以下定义邻接矩阵类型
typedef struct {
	int no;         //定点编号
	InfoTpye info;  //顶点其他信息
}VertexType;		//顶点类型
typedef struct {
	int edges[MAXV][MAXV];   //邻接矩阵数组
	int n, e;                //顶点数，边数
	VertexType vexs[MAXV];   //存放顶点信息
}MatGraph;					 //完整的图邻接矩阵类型
void CreatGraph(MatGraph& g, int A[MAXV][MAXV], int n, int e)
{//创建图的邻接矩阵
    g.n = n; g.e = e;
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < n; j++) 
        {
            g.edges[i][j] = A[i][j];
        }
    }
}
void DisGraph(MatGraph g)
{//输出邻接矩阵g
    for (int i = 0; i = g.n)
    {
        return -1; //顶点编号错误
    }
    for (int i = 0; i < g.n; i++) 
    {
        if (g.edges[v][i] > 0 && g.edges[v][i] < INF)
        {
            d++;
        }
    }
    return d;
}
int Degree2(MatGraph g, int v)
{
    int d1 = 0, d2 = 0, d;
    if (v < 0 || v > g.n)
    {
        return -1; //顶点编号错误
    }
    for (int i = 0; i < g.n; i++) 
    {  //计算出度
        if (g.edges[v][i] > 0 && g.edges[v][i] < INF)
        {
            d1++;
        }
    }
    for (int i = 0; i < g.n; i++) 
    {  //计算入度
        if (g.edges[i][v] > 0 && g.edges[i][v] < INF)
        {
            d2++;
        }
    }
    d = d1 + d2;
    return d;
}
//----------------------------------------------------------------------------
typedef char VertexType_1; 
typedef struct edgenode  //建立边节点
{
    int adjvex;             //该边的邻接点编号
    int weight;             //该边的相关信息，如权值等，用整形表示
    struct edgenode* nextarc;
} ArcNode;

typedef struct vexnode //建立头节点
{
    VertexType_1 data;
    ArcNode* firstarc; //头节点指向的第一条边
} VHeadNode;

typedef struct
{
    int n, e;                //图中的顶点数和边数
    VHeadNode adjlist[MAXV]; //建立头节点数组
} AdjGraph;
void CreatGraph_1(AdjGraph*& G, int A[MAXV][MAXV], int n, int e)
{//创建图的邻接表
    ArcNode* p;
    G = (AdjGraph*)malloc(sizeof(AdjGraph));
    G->n = n;
    G->e = e;
    for (int i = 0; i < n; i++)
    {//给邻接链表中所有头结点的指针域置初值
        G->adjlist[i].firstarc = NULL;
    }
    for (int i = 0; i < G->n; i++) 
    {//检查邻接矩阵中的每个元素
        for (int j = G->n - 1; j >= 0; j--) 
        {
            if (A[i][j] > 0 && A[i][j] < INF) //存一条边
            {
                p = (ArcNode*)malloc(sizeof(ArcNode));//创建一个节点p
                p->adjvex = j;
                p->weight = A[i][j];
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;//采用头插法插入结点p
            }
        }
    }
}
void DisplayGraph(AdjGraph* G)
{//输出邻接表G
    ArcNode* p;
    for (int i = 0; i < G->n; i++) 
    {
        p = G->adjlist[i].firstarc;
        printf(" % 3d", i);
        while (p != NULL) {
            printf(" % 3d[%d]→", p->adjvex, p->weight);
            p = p->nextarc;
        }
        printf("∧n");
    }
}
void DestoryGraph(AdjGraph*& G)
{//销毁图的邻接表
    ArcNode* pre, * p;
    for (int i = 0; i < G->n; i++) 
    {//扫描所有的单链表
        pre = G->adjlist[i].firstarc;//p指向第i个单链表的首结点
        if (pre != NULL) 
        {
            p = pre->nextarc;
            while (p != NULL) 
            {//释放第i个单链表的所有边结点
                free(pre);
                pre = p;
                p = p->nextarc;
            }
            free(pre);
        }
    }
    free(G);//释放头结点数组
}
int Degree_l(AdjGraph* G, int v)
{//无向图
    int d = 0;
    ArcNode* p;
    if (v < 0 || v >= G->n)
    {
        return -1; //顶点编号错误
    }
    for (int i = 0; i < G->n; i++)
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL) 
        {
            d++;
            p = p->nextarc;
        }
    }
    return d;
}
int Dgree_2(AdjGraph* G, int v)
{//有向图
    int d1 = 0, d2 = 0, d;
    ArcNode* p;
    if (v < 0 || v >= G->n)
    {
        return -1; //顶点编号错误
    }
    for (int i = 0; i < G->n; i++) 
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL)
        {
            d1++;
            p = p->nextarc;
        }
    }
    for (int i = 0; i < G->n; i++) 
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL)
        {
            if (p->adjvex == v)
            {
                d2++;
                p = p->nextarc;
            }
        }
    }
    d = d1 + d2;
    return d;
}

#endif

main函数测试：

#include"图.h"
int main()
{
	MatGraph g;
	AdjGraph* G;
	int A[MAXV][MAXV] = {
	{0, 5, INF, 7, INF, INF}, {INF, 0, 4, INF, INF, INF},
	{8, INF, 0, INF, INF, 9}, {INF, INF, 5, 0, INF, 6 },
	{INF, INF, INF, 5, 0, INF}, {3, INF, INF, INF, 1,0} };
	int n = 6, e = 10;           
	CreatGraph(g,A,n,e);
	printf("(1)图G的邻接矩阵：n"); DisGraph(g);
	CreatGraph_1(G, A, n, e);
	printf("(2)图G的邻接表：n"); DisplayGraph(G);
	printf("(3)销毁图G的邻接表n");
	DestoryGraph(G);
	system("pause");
	return 1;
}

运行结果截图：

2.实现图的遍历算法

map_travsal.h 头文件

#ifndef _map_travsal
#define _map_travsal
//实现图的两种遍历算法
#include
#include
#include
#include"图.h"
using namespace std;
int visited[MAXV];	//全局数组
void DFS(AdjGraph* G, int v) //递归深度优先遍历算法
{
	ArcNode* p;
	printf("%3d", v); visited[v] = 1;  //访问顶点v，并置已访问标记
	p = G->adjlist[v].firstarc; //p指向顶点v的第一条弧的弧头结点
	while (p != NULL)
	{
		if (visited[p->adjvex] == 0)  //若p->adjvex顶点未访问，递归访问它
		{
			DFS(G, p->adjvex);
		}	
		p = p->nextarc;   //p指向顶点v的下一条弧的弧头结点
	}	
}
//DFS1(G，v)算法的思路如下：
//栈St 初始化，visited数组所有元素初始化为0；访问顶点v，visited[v] = 1；顶点v进栈St；
//while (栈St非空)
//{
//    取St的栈顶顶点x(不退栈)；
//        找顶点x的第一个相邻点；
//        while (顶点x存在相邻点w)
//        {
//            if (顶点w没有访问过)
//            {
//                访问顶点w并置visited[w] = 1;
//                将顶点w进栈；
//                退出第2重循环；
//            }
//            继续找x的其他相邻点；
//        }
//    if (顶点x没有其他相邻点)将x退栈；
//}
void DFS1(AdjGraph* G, int v)  //非递归深度优先遍历算法
{
	ArcNode* p;
	int St[MAXV];
	int top = -1, w, x, i;
	for (i = 0; i < G->n; i++)
	{
		visited[i] = 0;  //顶点访问标志均置成 0
	}
	printf("%3d", v); //访问顶点v
	visited[v] = 1; //置顶点v已访问
	top++; St[top] = v;   //将顶点v进栈
	while (top > -1) //栈不空循环
	{
		x = St[top]; //取栈顶顶点x作为当前顶点
		p = G ->adjlist[x].firstarc; //找顶点x的第一个相邻点
		while (p != NULL)
		{
			w = p->adjvex; //x的相邻点为w
			if (visited[w] == 0) //若顶点w没有访问
			{
				printf("%3d", w); //访问顶点w
				visited[w] = 1; //置顶点w已访问
				top++; //将顶点w进栈
				St[top] = w;
				break; //退出循环，即再处理栈顶的顶点（体现后进先出）
			}
			p = p->nextarc; //找顶点x的下一个相邻点	
		}
		if (p == NULL)
		{
			top--; //若顶点x再没有相邻点，将其退栈	
		}
	}
	printf("n");
}
void BFS(AdjGraph* G, int v) //广度优先遍历算法
{
	ArcNode *p;
	int queue[MAXV], front = 0, rear = 0; //定义环形队列并初始化
	int visited[MAXV]; //定义存放顶点的访问标志的数组
	int w, i;
	for (i = 0; i < G->n; i++)
	{
		visited[i] = 0;//访问标志数组初始化
	}
	printf("%3d", v); //输出被访问顶点的编号
	visited [v] = 1; //置已访问标记
	rear = (rear + 1) % MAXV;
	queue[rear] = v; //v进队
	while (front != rear) //若队列不空时循环
	{
		front = (front + 1) % MAXV;
		w = queue[front]; //出队并赋给w
		p = G->adjlist[w].firstarc; //找顶点w的第一个相邻点
		while (p != NULL)
		{
			if (visited[p->adjvex] == 0) //若相邻点未被访问
			{
				printf("%3d", p->adjvex); //访问相邻点
				visited[p->adjvex] = 1; //置该顶点已被访问的标志
				rear = (rear + 1)%MAXV; //该顶点进队
				queue[rear] = p->adjvex;
			}
			p = p->nextarc; //找下一个相邻点
		}
	}
	printf("n");
}

#endif

main函数测试

#include"图.h"
#include"map_travsal.h"
int main()
{
	MatGraph g;
	AdjGraph* G;
	int A[MAXV][MAXV] = {
	{0, 5, INF, 7, INF, INF}, {INF, 0, 4, INF, INF, INF},
	{8, INF, 0, INF, INF, 9}, {INF, INF, 5, 0, INF, 6 },
	{INF, INF, INF, 5, 0, INF}, {3, INF, INF, INF, 1,0} };
	int n = 6, e = 10;           
	CreatGraph(g,A,n,e);
	printf("(1)图G的邻接矩阵：n"); DisGraph(g);
	CreatGraph_1(G, A, n, e);
	printf("(2)图G的邻接表：n"); DisplayGraph(G);
	printf("从顶点0开始的DFS(递归算法)：n"); 
	DFS(G, 0); printf("n");
	printf("从顶点0开始的DFS(非递归算法)：n");
	DFS1(G, 0);
	printf("从顶点0开始的BES:n");
	BFS(G, 0);
	DestoryGraph(G);
	system("pause");
	return 1;
}

数据结构-图

1.实现图的邻接矩阵和邻接表的存储

2.实现图的遍历算法

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