图的邻接链表的建立以及简单操作（一）

图的邻接链表的建立以及简单操作（一）

图一般有两种，有向图和无向图，对于它的编码方式也各有两种，邻接矩阵和邻接链表，顾名思义，邻接矩阵是顺序结构，而邻接链表就是链式结构了。

简单说一下邻接矩阵，如果一个图有N个节点，那么就建立一个N*N的数组并初始化为0（有些书籍是初始化为无穷大∞），如果两个节点之间有联系，就赋值为1，（如果有权值的话，就直接赋值为权值）

那么链接链表图是怎样的呢？定义一个图的数组，其每一个元素（图的顶点）都是一个链表的头结点，链表里的元素是其顶点的弧。

那么，下面贴上我的代码：

/*
TIME：2019/10/27
    图的创建及遍历
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int MAX_NUM = 20;
const int Y = 1;        //有向图
const int N = 0;        //无向图
/************定义图(定义结构体)*******************/ 
/*
就是感觉变量有点多，起名字有点烦。
所以尽量象征意义的背下来 
*/
typedef struct arcNode{
    int vertexIndex;            //弧指向的顶点信息 
    struct arcNode *nextarc;    //定义下一条弧 
    double price;                //权重(可以是距离，价格等) 
}arcNode;
typedef struct Vertex{
    int data;
    arcNode *firstarc;
}Vertex;
typedef struct Graph{
    Vertex *vertex[MAX_NUM];    //每个元素都为指向邻接表的指针，可以不定义成指针类型
    int verNum;
    int arcNum;
    int kind;
}Graph;
/***********建立图（初始化图）并且指定图的类型（有向还是无向）************/
void createGraph(Graph *&G,int kind){    //Graph* createGraph(Graph *G,int kind){...return Graph;}
    G = (Graph*)malloc(sizeof(Graph));
    if(G==NULL){
        return;
    }
    for(int i = 0;i<MAX_NUM;i++){    //邻接表数组每一个元素相当于是一个链表的头结点，所以要初始化为NULL 
        G->vertex[i] = NULL;
    }
    G->arcNum = 0;
    G->verNum = 0;
    G->kind = kind;        //这里是图的类型，可以是有向图，可以是无向图 
}
/*********释放图结构(删除图)*************/
void destory(Graph *&G){
    arcNode *cur,*next;
    if(G==NULL){
        return;
    }
    for(int i = 0;i<G->verNum;i++){
        if(G->vertex[i]==NULL) continue;
        cur = next = G->vertex[i]->firstarc;
        while(cur!=NULL){
            cur = next;
            next = next->nextarc;
            free(cur);
            cur = next;
        }
        G->vertex[i]->firstarc = NULL;
    }
    free(G);
    G = NULL;
} 
/**************增加顶点***********/
void addvertex(Graph *&G,int data){
    if(G->verNum == MAX_NUM){
        cout<<"不能再添加新的顶点了！"<<endl;
        return;
    }
    for(int i =0;i<G->verNum;i++){
        if(G->vertex[i] == NULL)
            continue;
        if(G->vertex[i]->data == data){
            cout<<"已经存在相同的顶点，不允许再添加"<<endl;
            return;
        }
    }
    Vertex *p = (Vertex*)malloc(sizeof(Vertex));
    p->data = data;
    p->firstarc = NULL;
    G->vertex[G->verNum] = p;
    G->verNum++;
}
/******删除指定节点**********/ 
void delVertexFromGraph(Graph *&G,int data){
    arcNode *cur,*next;
    arcNode *pre,temp;
    Vertex *othervertex;
    bool haveThisVertex = false;
    if(G==NULL || G->vexNum<=0){
        return;
    }
    for(int i = 0;i<G->verNum;i++){
        if(G->vertex[i] == NULL){
            continue;
        }
        if(G->vertex[i]->data == data){
            haveThisVertex = true;
            cur = next = G->vertex[i]->firstarc;
            if(G->kind == Y){    //如果是有向图，，稍微简单些 
                while(cur){
                    next = next->nextarc;
                    free(cur);
                    cur = next;
                }
                G->vertex[i]->firstarc = NULL;
            }
            else if(G->kind ==N ){        //如果是无向图，那么稍微麻烦些 
                while(cur!=NULL){
                    othervertex = G->vertex[cur->vertexIndex];    //这里就是找到另一个顶点，因为是无向图，两个地方都应该断掉关系
                    pre = NULL;
                    while(temp){
                        if(temp->vertexIndex == i){
                            if(pre == NULL){
                                othervertex->firstarc = temp->nextarc;
                                free(temp);
                            }
                            else{
                                pre->nextarc = temp->nextarc;
                                free(temp);
                            }
                            break;
                        }
                        pre = temp;
                        temp = temp->nextarc;
                    }
                    next = cur->nextarc;
                    free(cur);
                    G->arcNum--;
                    cur = next;
                }
                G->vertex[i] = NULL;
            }
            for(int j = i;j<G->verNum-1;++j){
                G->vertex[j] = G->vertex[j+1]； 
            }
            G->vertex[j] = NULL;
            G->vexNum--;
            break;
        }
    }
    if(haveThisVertex == false){
        cout<<"It doesn't have this vertex"<<endl;
    }
}