数据结构和算法之如何建立图

ゝ一世哀愁。 2024-03-31 14:59 47阅读 0赞

## **小白BG.1 邻接矩阵表示的图结点的结构** ##

>     typedef struct GNode *PtrToGNode;//PtrToGNode是指向GNode的一个指针
>     struct GNode{
>     int Nv;//顶点数
>     int Ne;//边数
>     WeightType G[MaxVertexNum][MaxVertexNum];
>     DataType Data[MaxVertexNum];//存顶点的数据
>     };
>     typedef PtrToGNode MGraph;//以邻接矩阵存储的图类型。定义为指向节点的指针。因为要用到的时候
>     一个指针远远比一整个图来的快捷

## **小白BG.2 邻接矩阵表示的图——初始化**  ##

初始化一个有VertexNum个顶点但没有边的图

>     typedef int Vertex;//用顶点下标表示顶点，为整型
>     MGraph CreateGraph(int VertexNum)//VertexNum这个顶点数真的是整数，
>     {
>     Vertex V , W;//我们在说V跟W的时候不是在说整数，而是顶点
>     MGraph Graph;
>     Graph = (MGraph)malloc(sizeof(struct GNode));
>     Graph->Nv = VertexNum;
>     Graph->Ne = 0;
>     //注意：这里默认顶点编号从0开始，到(Graph->Nv - 1)
>     for(V=0;V<Graph->Nv;V++)
>     for((W=0;W<Graph->Nv;W++))
>     Graph->G[V][M] = 0;//或者INFINITY，表示这两个顶点之间是没有边的
>     return Graph
>     }

## **小白BG.3 邻接矩阵表示的图——插入边** ##

>     typedef struct ENode *PtrToENode;
>     struct ENode{
>     Vertex V1,V2;//有向边<V1,V2>，V1V2两个顶点一个出发点一个终点
>     WeightType Weight;//权重，有权图才需要。权重的类型是WeightType
>     };
>     typedef PtrToENode Edge;
>     void InsertEdge(MGraph Graph,Edge E)
>     {
>     //插入边<V1,V2>，这是一条边
>     Graph->G[E->V1][E->V2] = E->Weight;
>     //无向图的话还需要一条边(一共两条)，<V2,V1>
>     Graph->G[E->V2][E->V1] = E->Weight;
>     }

## **小白BG.4 邻接矩阵表示的图——建立图**  ##

### **完整的建立一个MGraph**  ###

输入格式

1.  Nv Ne
2.  V1 V2 Weight
3.  ......

>     MGraph BuildGraph()
>     {
>     MGraph Graph;
>     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;
>     }

### 简易建法 ###

>     int G[MAXN][MAXN],Nv,Ne;//声明为全局变量
>     void BuildGraph()
>     {
>     int i,j,v1,v2,w;
>     scanf("%d",&Nv);
>     //CreateGraph
>     for(i=0;i<Nv;i++)
>     for(j=0;j<Nv;j++)
>     G[i][j] = 0;//或INFINITY，把矩阵所有元素先初始化为0或者无穷大
>     scanf("%d",&Ne);
>     for(i = 0;i < Ne; i++){
>     scanf("%d %d %d",&v1,&v2,&w);
>     //InsertEdge
>     G[v1][v2] = w;
>     G[v2][v1] = w;
>     }
>     }
> 
> ## **小白BG.5 邻接表表示的图结点的结构** ##

邻接表：G\[N\]为指针数组，对应矩阵每一行一个链表，只存非0元素

>     typedef struct GNode *PtrToGNode;
>     struct GNode {
>     int Nv;//顶点数
>     int Ne;//边数
>     AdjList G;//邻接表
>     };
>     typedef PtrToGNode LGraph;
>     //以邻接表方式存储的图类型
>     //AdjList是自己定义的
>     typedef struct Vnode{
>     PtrToAdjVNode FirstEdge;
>     DataType Data;//存顶点的数据
>     }AdjList[MaxVertexNum];//AdjList是邻接表类型
>     typedef struct AdjVNode *PtrToAdjVNode;
>     struct AdjVNode{
>     Vertex AdjV;//邻接点下标，定义为整型
>     WeightType Weight;//边权重
>     PtrToAdjVNode Next;
>     };

## **小白BG.6 邻接表表示的图——建立图** ##

**初始化一个有VertexNum个顶点但没有边的图**

>     typedef int Vertex;//用顶点下标表示顶点，为整型
>     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;
>     }

>     void InsertEdge(LGraph Graph,Edge E)
>     {
>     PtrToAdjVNode NewNode;
>     //-------------------插入边<V1,V2>------------------------------
>     //为V2建立新的邻接点
>     NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjNode));
>     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>------------------
>     //为V1建立新的邻接点
>     NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjNode));
>     NewNode->AdjV = E->V1;
>     NewNode->Weight = E->Weight
>     //将V2插入到V1的表头
>     NewNode->Next = Graph->G[E->V2].FirstEdge;
>     Graph->G[E->V2].FirstEdge = NewNode;
>     }