【algo&ds】6.图及其存储结构、遍历

时间：2024-11-08 15:37:08

1.什么是图

图表示”多对多”的关系

包含

一组顶点：通常用 V（Vertex）表示顶点集合

一组边：通常用 E（Edge）表示边的集合

边是顶点对：（v,w）∈ E，其中 v,w ∈ V ，v—w

有向边 <v,w> 表示从 v 指向 w 的边（单行线） v→w

不考虑重边和自回路

常见术语

无向图：图中所有的边无所谓方向

有向图：图中的边可能是双向，也可能是单向的，方向是很重要的

权值：给图中每条边赋予的值，可能有各种各样的现实意义

网络：带权值的图

邻接点：有边直接相连的顶点

出度：从某顶点发出的边数

入度：指向某顶点的边数

稀疏图：顶点很多而边很少的图

稠密图：顶点多边也多的图

完全图：对于给定的一组顶点，顶点间都存在边

抽象数据类型定义

类型名称：图（Graph）

数据对象集：G（V，E）由一个非空的有限顶点集合 V 和一个有限边集合 E 组成

操作集：对于任意图 G ∈ Graph，以及 v ∈ V，e ∈ E

主要操作有：

Graph Crate()：建立并返回空图

Graph InsertVertex(Graph G,Vertex v)：将 v 插入 G

Graph InsertEdge(Graph G,Edge e)：将 e 插入 G

void DFS(Graph G,Vertex v)：从顶点 v 出发深度优先遍历图 G

void BFS(Graph G,Vertex v)：从顶点 v 出发宽度优先遍历图 G

2.图的存储结构表示

2.1邻接矩阵表示

【algo&ds】6.图及其存储结构、遍历

邻接矩阵 G[N][N]——N 个顶点从 0 到 N-1 编号

存在边<vi,vj>，则G[i][j]=1，否则为0

特征：

对角线元素全 0

关于对角线对称

优点：

直观、简单、好理解

方便检查任意一对顶点间是否存在边

方便找任一顶点的所有邻接点

方便计算任一顶点的度

无向图：对应行（或列）非 0 元素的个数

有向图：对应行非 0 元素的个数是出度；对应列非 0 元素的个数是入度

缺点：

浪费空间——存稀疏图

浪费时间——统计稀疏图的边

代码实现

#include<stdio.h>

#include<stdlib.h>

#define MaxVertexNum 100

typedef int weightType;

typedef int Vertex;

typedef int DataType;

typedef struct GNode *ptrToGNode;

struct GNode{   // 图

	int Nv;   // 顶点数

	int Ne;   // 边数

	weightType G[MaxVertexNum][MaxVertexNum];

	DataType Data[MaxVertexNum]; // 存顶点的数据

};

typedef ptrToGNode MGraph;

typedef struct ENode *ptrToENode;

struct ENode{  // 边

	Vertex V1,V2;    // 有向边<V1,V2>

	weightType Weight;  // 权重

};

typedef ptrToENode Edge;

// 初始化图

MGraph Create(int VertexNum){

	Vertex v,w;

	MGraph Graph;

	Graph = (MGraph)malloc(sizeof(struct GNode));

	Graph->Nv = VertexNum;

	Graph->Ne = 0;

	for(v=0;v<VertexNum;v++)

		for(w=0;w<VertexNum;w++)

			Graph->G[v][w] = 0;

	return Graph;

}

// 插入边

MGraph Insert(MGraph Graph,Edge E){

	// 插入边 <V1,V2>

	Graph->G[E->V1][E->V2] = E->Weight;

	// 如果是无向图，还需要插入边 <V2,V1>

	Graph->G[E->V2][E->V1] = E->Weight;

} 

// 建图

MGraph BuildGraph(){

	MGraph Graph;

	Edge E;

	Vertex V;

	int Nv,i;

	scanf("%d",&Nv);   // 读入顶点数

	Graph = Create(Nv);

	scanf("%d",&(Graph->Ne));  // 读入边数

	if(Graph->Ne != 0){

		E = (Edge)malloc(sizeof(struct ENode));

		for(i=0;i<Graph->Ne;i++){

			scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);  // 读入每个边的数据

			Insert(Graph,E);

		}

	}

	return Graph;

}

// 遍历图

void print(MGraph Graph){

	Vertex v,w;

	for(v=0;v<Graph->Nv;v++){

		for(w=0;w<Graph->Nv;w++)

			printf("%d ",Graph->G[v][w]);

		printf("\n");

	}

} 

int main(){

	MGraph Graph;

	Graph = BuildGraph();

	print(Graph);

	return 0;

}

2.2邻接表实现

【algo&ds】6.图及其存储结构、遍历

特点：

  • 方便找任一顶点的所有邻接顶点
  • 节省稀疏图的空间
    • 需要 N 个头指针 + 2E 个结点（每个结点至少 2 个域）
  • 对于是否方便计算任一顶点的度
    • 无向图：方便
    • 有向图：只能计算出度
  • 不方便检查任意一对顶点间是否存在边

代码实现

#include<stdio.h>

#include<stdlib.h>

#define MaxVertexNum 100

typedef int Vertex;

typedef int DataType;

typedef int weightType;  

typedef struct ENode *ptrToENode;

struct ENode{  // 边

	Vertex V1,V2;    // 有向边<V1,V2>

	weightType Weight;  // 权重

};

typedef ptrToENode Edge;

typedef struct AdjVNode *ptrToAdjVNode;

struct AdjVNode{  // 邻接表内元素

	Vertex AdjV;  // 邻接点下标

	weightType Weight;  // 权值

	ptrToAdjVNode Next;  // 下一个

};

typedef struct VNode{  // 邻接表头

	ptrToAdjVNode FirstEdge;  // 存每个顶点指针

	DataType Data;  // 顶点数据

}AdjList[MaxVertexNum];

typedef struct GNode *ptrToGNode;

struct GNode{  // 图

	int Nv;  // 顶点

	int Ne;  // 边数

	AdjList G; // 邻接表

};

typedef ptrToGNode LGraph;

// 初始化

LGraph create(int VertexNum){

	Vertex v,w;

	LGraph Graph;

	Graph = (LGraph)malloc(sizeof(struct GNode));

	Graph->Nv = VertexNum;  // 初始化边

	Graph->Ne = 0;   // 初始化点

	// 每条边的 FirstEdge 指向 NULL

	for(v=0;v<Graph->Nv;v++)

		Graph->G[v].FirstEdge = NULL;

	return Graph;

}

// 插入一条边到邻接表的顶点指针之后

void InsertEdge(LGraph Graph,Edge E){

	ptrToAdjVNode newNode; 

	/**************** 插入边<V1,V2> ******************/

	// 为 V2 建立新的结点

	newNode = (ptrToAdjVNode)malloc(sizeof(struct AdjVNode));

	newNode->AdjV = E->V2;

	newNode->Weight = E->Weight;

	// 将 V2 插入到邻接表头

	newNode->Next = Graph->G[E->V1].FirstEdge;

	Graph->G[E->V1].FirstEdge = newNode;

	/*************** 若为无向图，插入边<V2,V1> *************/

	newNode = (ptrToAdjVNode)malloc(sizeof(struct AdjVNode));

	newNode->AdjV = E->V1;

	newNode->Weight = E->Weight;

	newNode->Next = Graph->G[E->V2].FirstEdge;

	Graph->G[E->V2].FirstEdge = newNode;

} 

// 建图

LGraph BuildGraph(){

	LGraph Graph;

	Edge E;

	Vertex V;

	int Nv,i;

	scanf("%d",&Nv);

	Graph = create(Nv);

	scanf("%d",&(Graph->Ne));

	if(Graph->Ne != 0){

		for(i=0;i<Graph->Ne;i++){

			E = (Edge)malloc(sizeof(struct ENode));

			scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);

			InsertEdge(Graph,E);

		}

	}

	return Graph;

} 

// 打印

void print(LGraph Graph){

	Vertex v;

	ptrToAdjVNode tmp;

	for(v=0;v<Graph->Nv;v++){

		tmp = Graph->G[v].FirstEdge;

		printf("%d ",v);

		while(tmp){

			printf("%d ",tmp->AdjV);

			tmp = tmp->Next;

		}

		printf("\n");

	}

}

int main(){

	LGraph Graph;

	Graph = BuildGraph();

	print(Graph);

	return 0;

}

3.图的遍历

3.1深度优先搜索DFS

void DFS ( Vertex V ){

    visited[ V ] = true;

    for ( V 的每个邻接点 W )

        if( !visited[ W ])

            DFS( W );

}

3.2广度优先搜索BFS

void BFS( Vertex V ){

    queue<Vertex> q;

    visited[V] = true;

    q.push(V);

    while(!q.empty()){

        V = q.front(); q.pop();

        for( V 的每个邻接点 W ){

        	if( !visited[ W ]){

            	visited[W] = true;

            	q.push(W);

            }

        }

    }

}

相关文章