建立一个图，并且遍历---MOOC浙大数据结构建图向LGraph中插入边考试写法：矩阵方式：考试写法：上述两种标准写法，封装好了底层的接口，让调用者无须关注底层的实现，到底是用矩阵？还是用链表？遍历六度空间--MOOC浙大数据结构PTA - 拯救007 ( BFS )

113 阅读 0 评论 75 点赞

我是靠谱客的博主腼腆小笼包，最近开发中收集的这篇文章主要介绍建立一个图，并且遍历---MOOC浙大数据结构建图向LGraph中插入边考试写法：矩阵方式：考试写法：上述两种标准写法，封装好了底层的接口，让调用者无须关注底层的实现，到底是用矩阵？还是用链表？遍历六度空间--MOOC浙大数据结构PTA - 拯救007 ( BFS )，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

建图

以邻接表方式存储的图类型

typedef struct GNode *PtrToGNode;
struct GNode{//整个图
	int Nv;//顶点数
	int Ne;//边数、
	AdjList G;//邻接表
};
typedef PtrToGNode LGraph;

typedef struct AdjVNode *PtrToAdjVNode;
typedef struct Vnode{//顶点
	PtrToAdjuVNode FirstEdge;
	DataType Data;/*存顶点的数据*/
}AdjList[MaxVertexNum];//邻接表类型

typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{//邻接点
	Vertex AdjV;//邻接点下标
	WeightType Weight;//边权重
	PtrToAdjVNode Next;
};
typedef struct ENode *PtrToENode;
struct ENode{
	Vertex V1, V2;		//有向边《V1，V2》
	WeightType Weight;	//权重（如果需要）
};
typedef PtrToENode Edge;
	Vertex V1, V2;		//有向边《V1，V2》
	WeightType Weight;	//权重（如果需要）
};
typedef PtrToENode Edge;

LGraph初始化

typedef int Vertex;//用顶点下标表示顶点，为整型int
LGraph CreateGraph(int VertexNum)
{
	Vertex V, W;
	LGraph Graph;

	Graph = (LGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	/*默认顶点编号从0开始，到Graph->Nv-1 */
	for (V = 0; V < Graph->Nv; V++)
		Graph->G[V].FirstEdge = NULL;
	return Graph;
}

向LGraph中插入边

void InsertEdge(LGraph Graph, Edge E)
{
	PtrToAdjVNode NewNode;
	/*插入边《V1，V2》*/
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));//V2建立邻接点
	NewNode->AdjV = E->V2;
	NewNode->Weight = E->Weight;
	/*将V2插入V1的表头*/
	NewNode->Next = Graph->G[E->V1].FirstEdge;
	Graph->G[E->V1].FirstEdge = NewNode;

	/*如果是无向图，还要插入边《V2，V1》*/
	/*插入边《V2，V1》*/
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));//V1建立邻接点
	NewNode->AdjV = E->V1;
	NewNode->Weight = E->Weight;
	/*将V1插入V2的表头*/
	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 = CreateGraph(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);
			InsertEdge(Graph, E);
		}
	}
	/*如果顶点有数据，甚至是结构体，那么还要读入数据*/
	for (V = 0; V < Graph->Nv; V++)
		scanf("%c", &(Graph->Data[V]));
	return Graph;
}

考试写法：

struct graph{
  int     node;
  graph*  p_next;
  graph(int x):node(x),p_next(NULL){}
};
  graph* p=new graph(0);//图的头，链表头
  graph* tmp=p;
While()//循环条件
{
     tmp->node=a;//节点的值
     tmp->p_next=new graph(b);//边的值
     tmp=tmp->p_next;
}

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
struct graph{
	int     node;
	graph*  p_next;
	graph(int x) :node(x), p_next(NULL){}
};
int N;

void DFS(int vertex,vector<int>& vec,int value,graph** head,int * visit)
{
	value++;
	visit[vertex] = 1;
	int flag = false;
	graph* tmp = head[vertex];
	while (tmp->p_next != NULL)
	{
		tmp = tmp->p_next;
		if (!visit[tmp->node])
		{
			flag = true;
			DFS(tmp->node,vec,value,head,visit);
		}
	}
	if (!flag)
	{
		vec.push_back(value-1);
	}
}

int main()
{
	cin >> N;
	int *visit = new int[N + 1];
	for (int i = 0; i < N + 1; i++)
	{
		visit[i] = 0;
	}

	graph** head = new graph*[N];
	for (int i = 1; i <= N;i++)
	{
		head[i] = new graph(i);
	}
	int saveN = N - 1;
	while (saveN--)
	{
		int tmp1, tmp2;
		cin >> tmp1>>tmp2;
		graph* tmp = head[tmp1];
		while (tmp->p_next != NULL)
		{
			tmp = tmp->p_next;
		}
		tmp->p_next = new graph(tmp2);
	}
	vector<int> vec;
	DFS(1, vec, 0, head, visit);
	sort(vec.begin(),vec.end());
	int res = 0;
	for (int i = 0; i < vec.size()-1;i++)
	{
		res += 2 * vec[i];
	}
	res += vec[vec.size() - 1];
	cout << res<<endl;

	return 0;
}

矩阵方式：

定义图：

typedef struct GNode *PtrToGNode;

struct GNode{
	int Nv;//顶点数
	int Ne;//边数、
        /*有可能有权值int value*/
	WeightType G[MaxVertexNum][MaxVertexNum];
        DataType   Data[MaxVertexNum];//存顶点的数据类型
};
typedef PtrToGNode MGraph;//以邻接矩阵存储的图类型

建立图：

typedef int Vertex;//用顶点下标表示顶点，为整型int
MGraph CreateGraph(int VertexNum)
{
	Vertex V, W;
	MGraph Graph;

	Graph = (MGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;

	for (V = 0; V < Graph->Nv; V++)
		for (W = 0; W < Graph->NV; W++)
			Graph->G[V][W] = 0;//有权图用INFINITY无穷大表示没有边
	return Graph;
}

插入边：

typedef struct ENode *PtrToENode;
struct ENode{
	Vertex V1, V2;		//有向边《V1，V2》
	WeightType Weight;	//权重（如果需要）
};
typedef PtrToENode Edge;

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

完整建立一个MGraph

MGraph BuildGraph()
{
	MGraph Graph;
	Edge E;
	Vertex V;
	int Nv, i;

	scanf("%d",&Nv);
	Graph = CreateGraph(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);
			InsertEdge(Graph, E);
		}
	}
	/*如果顶点有数据，甚至是结构体，那么还要读入数据*/
	for (V = 0; V < Graph->Nv; V++)
		scanf("%c", % (Graph->Data[V]));
	return Graph;
}

考试写法：

上述两种标准写法，封装好了底层的接口，让调用者无须关注底层的实现，到底是用矩阵？还是用链表？

遍历

深度优先

void DFS ( Vertex V )
{ visited[ V ] = true;
	for ( V 的每个邻接点W )
		if ( !visited[ W ] )
			DFS( W );
}

广度优先

void BFS ( Vertex V )
{ 
	visited[V] = true;
	Enqueue(V, Q);
	while(!IsEmpty(Q)){
		V = Dequeue(Q);
		for ( V 的每个邻接点W )
		if ( !visited[W] ) {
			visited[W] = true;
			Enqueue(W, Q);
			}
	}
}