图的引子和数据结构以及相关的操作

本博客的代码的思想和图片参考：好大学慕课浙江大学陈越老师、何钦铭老师的《数据结构》

Graph

1 What is the graph

1.1 Graph Definition

a) show the relationship of many to many

b) contain:

1.a group of terminal points: use the V(Vertex)stand for the collection of vertex

2.a group of edges: using the E(Edge) to stand for the collection of terminal edges

 

edge:edge is the two vertex connection. For example:

No direction edge is use(v,w) to stand for a path v and w can reach each other. Direction edge is use<v,w> to stand for a path from v to w. We don’t think repeat edge and self path.

 

 

 

 

 

 

The number in the edge is the weight of the edge. For example,we can use those number stand for the distance between the two vertexes.

We call the graph with weight as the network.

 

 

 

 

 

2 Define Abstract Data Type and Operate

2.1 Date Type Name

图：Graph

 

2.2 The Collection of the Data Type

G(V,E) is not null,contains limited points’ collection and limited edges’ collection.

2.3 The Collection of Operate

Operation Collections：

a):

   /*build a empty graph then return*/

q Graph Create();

 

b):

   /*insert a new vertex into the graph

*/

q Graph InsertVertex(Graph G, Vertex v);

 

c):

/*

insert a new edge into the graph

*/

q Graph InsertEdge(Graph G, Edge e);

 

d):

/* from the vertex v start, depth first search graph*/

q void DFS(Graph G, Vertex v);

 

e)

   /*from the vertex start,breadth first search graph*/

q void BFS(Graph G, Vertex v);

/*get min path from vertex v to other vertex*/

q void ShortestPath(Graph G, Vertex v, int Dist[]);

   

  /*calculate the min created tree*/

q void MST(Graph G);

......

 

3 How to show a graph using program

3.1 Adjacent Matrix

G[n][n]:There are N vertex from 0 to N-1 stored in the matrix

 

1 if<vi,vj> is the edge in the graph

G[i][i]=

0 if <vi,vj> is not edge in the graph

 

 

For example:

 

 

 

We find the matrix is symmetrical,So we only store halt of those data.

So we can use a one-dimensional array to stand for the above two-dimensional.

 

 

The one-dimensional length is n*(n+1)/2,The G(i,j) in the one-dimensional index is (i*(i+1)/2+ j ). If the graph is network,we just modify the 1 to the weight value.

 

 

3.1.1 The Advantages of Adjacent Matrix

 

 

3.1.2 The Disadvantages of Adjacent Matrix

 

 

 

3.1.3 Sparse Matrix

In sparse matrix,the 0  element is too many.

3.2 Adjacent Table

We set a point to every vertex and let them to point the vertexes that they are adjacent. From following picture,we find we need N head point and 2*E(edge) node

For example:

 

 

 

 

Think this method is really reduce space?

From above picture,in no direction graph ,we store the node twice.4-->9 and 9-->4.It waste the space.But if the graph is very spare,we use the adjacent table is very reduce the space.But is the graph is not spare graph,the adjacent will waste many space.

 

3.2.1 The Advantage and the Disadvantage of Adjacent Table

 

 

 

 

 

3.2.2 Orthogonal List

We know we only get indegree(入度) from the adjacent table.If will want get outdegree(出度), we need construct reverse adjacent table. Is a link list can provide the tow advantage. We can try orthogonal list. Let’s see following picture.

 

3.3 What method we will chose?

From the above two ways,we can know: adjacent matrix store N vertex need N*(N+1)/2 space The adjacent table store N vertex need N + 2*E(edge)space.

If N*(N+1)/2 >= N+2*E

 

 

4 Data Structure Code and Insert Code of Graph

 

adjacent matrix:

#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTEX_NUM 100 /*define the max number of the vertex*/
#define INFINITY 65535     /*define double byte no negitive integer max number is 65535*/

typedef int vertex;        /*define the data type of the vertex*/
typedef int weightType;    /*define the data type of the weight*/
typedef char dataType; /*define the data type of the vertex value*/

/*define the data structure of the Edge*/
typedef struct eNode *ptrToENode;
typedef struct eNode{
    vertex v1,v2;           /*two vertex between the edge <v1,v2>*/
    weightType weight;      /*the value of the edge's weigth */
};
typedef ptrToENode edge;

/*define the data structure of the graph*/
typedef struct gNode *ptrToGNode;
typedef struct gNode{
    int vertex_number;  /*the number of the vertex*/
    int edge_nunber;    /*the number of the edge*/
    weightType g[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   /*define the adjacent matrix of graph*/
    dataType data[MAX_VERTEX_NUM];                  /*define the dataType array to store the value of vertex*/
};
typedef ptrToGNode adjacentMatrixGraph;             /*a graph show by adjacent matrix*/

/*
create a graph given the vertex number.
@param vertexNum The verter number of the graph
@return a graph with vertex but no any egdgs
*/
adjacentMatrixGraph createGraph(int vertexNum){
    vertex v,w;
    adjacentMatrixGraph graph;
    graph =(adjacentMatrixGraph)malloc(sizeof(struct gNode));
    graph->vertex_number=vertexNum;
    graph->edge_nunber=0;
    /*initialize the adjacent matrix*/
    for(v=0;v<graph->vertex_number;v++){
        for(w=0;w<graph->vertex_number;w++){
            graph->g[v][w]= INFINITY;
        }
    }

    return graph;
}

/*
insert a edge to graph.We will distinct oriented graph and undirected graph
@param graph The graph you want to insert edge
@param e The edge you want to insert the graph
@param isOriented Whether the graph is oriented graph.If the graph is oriented
        we will set adjacent matrix [n][m]=[m][n]=edge's weight,else we only set
        the adjacent matrix [n][m]=edge's weight
*/
void inserEdge(adjacentMatrixGraph graph,edge e,int isOriented){
    graph->g[e->v1][e->v2]=e->weight;
    if(!isOriented){
        graph->g[e->v2][e->v1]=e->weight;
    }
}

/*
construct a graph according user's input

@return a graph has been filled good
*/
adjacentMatrixGraph buildGraph(){
    adjacentMatrixGraph graph;
    edge e;
    vertex v;
    int vertex_num,i;
    scanf("%d",&vertex_num);
    graph = createGraph(vertex_num);
    scanf("%d",&(graph->edge_nunber));
    if(!graph->edge_nunber){
        e = (edge)malloc(sizeof(struct eNode));
        for(i=0;i<graph->edge_nunber;i++){
            scanf("%d %d %d",&e->v1,&e->v2,&e->weight);
            inserEdge(graph,e,1);
        }
    }

    for(i=0;i<graph->vertex_number;i++){
        scanf("%c",&(graph->data[i]));
    }

    return graph;


}


int main(){
    printf("just test");
    return 0;
}

 

adjacent table

#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTEX_NUM 100 /*define the max number of the vertex*/
#define INFINITY 65535     /*define double byte no negitive integer max number is 65535*/

typedef int vertex;        /*define the data type of the vertex*/
typedef int weightType;    /*define the data type of the weight*/
typedef char dataType; /*define the data type of the vertex value*/

/*define the data structure of the Edge*/
typedef struct eNode *ptrToENode;
typedef struct eNode{
    vertex v1,v2;           /*two vertex between the edge <v1,v2>*/
    weightType weight;      /*the value of the edge's weigth */
};
typedef ptrToENode edge;

/*define the data structure adjacent table node*/
typedef struct adjNode *ptrToAdjNode;
typedef struct adjNode{
    vertex adjVerx;         /*the index of the vertex*/
    weightType weight;      /*the value of the weight*/
    ptrToENode next;        /*the point to point the next node*/
};

/*define the data structure of the adjacent head*/
typedef struct vNode{
    ptrToAdjNode head;      /*the point to point the adjacent table node*/
    dataType data;          /*the space to store the name of the vertex,but some time the vertex has no names*/
}adjList[MAX_VERTEX_NUM];

/*define the data structure of graph*/
typedef struct gNode *ptrToGNode;
typedef struct gNode{
    int vertex_number;  /*the number of the vertex*/
    int edge_nunber;    /*the number of the edge*/
    adjList g;          /*adjacent table*/
};
typedef ptrToGNode adjacentTableGraph;             /*a graph show by adjacent table*/


/*
create a graph given the vertex number.
@param vertexNum The verter number of the graph
@return a graph with vertex but no any egdgs
*/
adjacentTableGraph createGraph(int vertexNum){
    adjacentTableGraph graph;

    vertex v;
    graph =(adjacentTableGraph)malloc(sizeof(struct gNode));
    graph->vertex_number=vertexNum;
    graph->vertex_number=0;
    /*initialize the adjacent table*/
    for(v=0;v<graph->vertex_number;v++){
        graph->g[v].head=NULL;
    }
    return graph;
}

/*
insert a edge to graph.We will distinct oriented graph and undirected graph
The e->v1 and e->v2 are the vertexs' indexs in the adjacent table
@param graph The graph you want to insert edge
@param e The edge you want to insert the graph
@param isOriented Whether the graph is oriented graph.If the graph is oriented
        we will set adjacent table graph[v1]->head=v2 and set graph[v1].head=v2
        otherwise we only set graph[v1].head=v2
*/
void insertEdge(adjacentTableGraph graph,edge e,int isOriented){
    /*build node<v1,v2>*/
    ptrToAdjNode newNode;
    newNode =(ptrToAdjNode)malloc(sizeof(struct adjNode));
    newNode->adjVerx=e->v1;
    newNode->weight=e->weight;
    newNode->next = graph->g[e->v1].head;
    graph->g[e->v1].head=newNode;
    /*if the graph is directed graph*/
    if(!isOriented){
        newNode =(ptrToAdjNode)malloc(sizeof(struct adjNode));
        newNode->adjVerx=e->v1;
        newNode->weight = e->weight;
        newNode->next = graph->g[e->v2].head;
        graph->g[e->v1].head=newNode;
    }
}

/*
build a graph stored by adjacent table
*/
adjacentTableGraph buildGraph(){
    adjacentTableGraph graph;
    edge e;
    vertex v;
    int vertex_num,i;

    scanf("%d",&vertex_num);
    graph  = createGraph(vertex_num);
    scanf("%d",(graph->edge_nunber));
    if(!graph->edge_nunber){
        e = (edge)malloc(sizeof(struct eNode));
        for(i=0;i<graph->edge_nunber;i++){
            scanf("%d %d %d",&e->v1,&e->v2,&e->weight);
            insertEdge(graph,e,1);
        }
    }

    /*if the vertex has name*/
    for(i=0;i<graph->vertex_number;i++){
        scanf("%c",&(graph->g[i].data));
    }
    return graph;
}


int main(){
    printf("just test");
}

 

 

 orthogonal list

#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTEX_NUM 100 /*define the max number of the vertex*/
#define INFINITY 65535     /*define double byte no negitive integer max number is 65535*/

typedef int vertex;        /*define the data type of the vertex*/
typedef int weightType;    /*define the data type of the weight*/
typedef char dataType; /*define the data type of the vertex value*/

/*define the data structure of the Edge*/
typedef struct eNode *ptrToENode;
typedef struct eNode{
    vertex v1,v2;           /*two vertex between the edge <v1,v2>*/
    weightType weight;      /*the value of the edge's weigth */
};
typedef ptrToENode edge;

/*define the data structure of the orthogonal list table node*/
typedef struct adjNode *ptrToAdjNode;
typedef struct adjNode{
    vertex tailVertex;      /*the inde of tail vertex*/
    vertex headVertex;      /*the index of the head vertex*/
    weightType weight;      /*the valie of the weight*/
    ptrToAdjNode hLink;     /*the point to point next node who point the head vertex*/
    ptrToAdjNode tLink;     /*the point to point next node who point the tail vertex*/
};
/*define the data structure of orthogonal list of head node*/
typedef struct headNode{
    dataType data;          /*the space to store the name of the vertex,but some time the vertex has no names*/
    ptrToAdjNode firstin;   /*the point to point the in-degree node*/
    ptrToAdjNode firstout;   /*the point to poit the out-degree node*/
}headList[MAX_VERTEX_NUM];

typedef struct gNode *ptrToGNode;
typedef struct gNode{
    int vertex_number;  /*the number of the vertex*/
    int edge_nunber;    /*the number of the edge*/
    headList head;
};
typedef ptrToGNode orthogonalList;

/*
create a graph given the vertex number.
@param vertexNum The verter number of the graph
@return a graph with vertex but no any egdgs
*/
orthogonalList createGraph(int vertexNum){
    orthogonalList graph;
    vertex v;
    graph =(orthogonalList)malloc(sizeof(struct gNode));
    graph->vertex_number;
    graph->edge_nunber=0;
    for(v=0;v<graph->vertex_number;v++){
        graph->head[v].firstin=NULL;
        graph->head[v].firstout=NULL;
    }
    return graph;
}

/*
insert a edge to graph.We will distinct oriented graph and undirected graph
The e->v1 and e->v2 are the vertexs' indexs in the orthogoanlList
@param graph The graph you want to insert edge
@param e The edge you want to insert the graph
*/
void insertEdge(orthogonalList graph,edge e){
    ptrToAdjNode newNode;
    newNode =(ptrToAdjNode)malloc(sizeof(struct adjNode));
    newNode->tailVertex=e->v1;
    newNode->headVertex=e->v2;
    newNode->weight = e->weight;
    /*let v1 head's firstout point to the new node */
    newNode->tLink=graph->head[e->v1].firstout;
    graph->head[e->v1].firstout=newNode;

    /*let v2 head's firstin point to new node*/
    newNode->hLink=graph->head[e->v2].firstin;
    graph->head[e->v2].firstin=newNode;
}

/*
build a graph stored by orthogonal list
*/
orthogonalList buildGraph(){
    orthogonalList graph;
    edge e;
    vertex v;
    int vertex_num,i;

    scanf("%d",&vertex_num);
    graph = createGraph(vertex_num);
    scanf("%d",&(graph->edge_nunber));
    if(!graph->vertex_number){
        e = (edge)malloc(sizeof(struct eNode));
        for(i=0;i<graph->edge_nunber;i++){
            scanf("%d %d %d",&e->v1,&e->v2,&e->weight);
            insertEdge(graph,e);
        }
    }

    /*if the vertex has name,we will set it following*/
    for(i=0;i<graph->vertex_number;i++){
        scanf("%c",&(graph->head[i].data));
    }
    return graph;
}
int main(){
    printf("just test");
    return 0;
}

 

 The Search of Graph

5.1 Depth First Search(DFS)

we will introduce it by following picture:

 

5.2 Breadth First Search(BFS)

 

BFS is similar with the tree level search.We using follow picture to display it’s principle.

 

 

 

 

6 Special Graph

6.1

we maybe meet some graphs, that are don’t connect to all nodes.

If we use BFS or DFS to search,we we find some node will be be searched. How to solve this problem.

The following we will use Chinese to describe.

 

首先我们要引入一些概念：

连通：如果从V到W存在一条(无向)路径，则V和W是连通的。

路径：V到W的路径是一系列的顶点{V,v1,v2,v3....W},其中任意相邻的顶点都有图的边。路径的长度是路径中边数之和(如果有权重则是所有的权重之和)，如果V到W之间所有的顶点都不同，则称为简单路径。  

回路：起点等于终点的路径

连通图：图中任意两点均连通。

 

6.2 图不连通怎么办

连通分量:无向图的极大连通子图

极大顶点数：再加一个顶点图就不连通了。

极大边数：包含子图中所有顶点相连的所有边

下面使用一个图片来说明

 

 

 

 

 

n 强连通：有向图中顶点V和W之间存在双向路径，则称V和W是强连通的

n 强连通图：有向图中任意两顶点均强连通

n 强连通分量：有向图的极大强连通子图

 

 

6.3 不连通的图如何进行BFS和DFS

对于不连通的图，对BFS来说，之前我们需要遍历每个节点的邻接点，但是如果出现不连通的图，我们需要把遍历每个节点的邻接点改为遍历每个节点的极大连通子图。对于DFS，我们需要在遍历每个节点的邻接点时改为遍历每个节点的极大连通子图即可。

BFS和DFS的遍历算法，使用的邻接表作为存储图的数据结构

 

#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTEX_NUM 100 /*define the max number of the vertex*/
#define INFINITY 65535     /*define double byte no negitive integer max number is 65535*/



typedef int vertex;        /*define the data type of the vertex*/
typedef int weightType;    /*define the data type of the weight*/
typedef char dataType; /*define the data type of the vertex value*/

//int visited[MAX_VERTEX_NUM];

/*define the data structure of the Edge*/
typedef struct eNode *ptrToENode;
typedef struct eNode{
    vertex v1,v2;           /*two vertex between the edge <v1,v2>*/
    weightType weight;      /*the value of the edge's weigth */
};
typedef ptrToENode edge;

/*define the data structure adjacent table node*/
typedef struct adjNode *ptrToAdjNode;
typedef struct adjNode{
    vertex adjVerx;         /*the index of the vertex*/
    weightType weight;      /*the value of the weight*/
    ptrToENode next;        /*the point to point the next node*/
};

/*define the data structure of the adjacent head*/
typedef struct vNode *ptrToVNode;
typedef struct vNode{
    ptrToAdjNode head;      /*the point to point the adjacent table node*/
    dataType data;          /*the space to store the name of the vertex,but some time the vertex has no names*/
}adjList[MAX_VERTEX_NUM];

/*define the data structure of graph*/
typedef struct gNode *ptrToGNode;
typedef struct gNode{
    int vertex_number;  /*the number of the vertex*/
    int edge_nunber;    /*the number of the edge*/
    adjList g;          /*adjacent table*/
};
typedef ptrToGNode adjacentTableGraph;             /*a graph show by adjacent table*/


/*
create a graph given the vertex number.
@param vertexNum The verter number of the graph
@return a graph with vertex but no any egdgs
*/
adjacentTableGraph createGraph(int vertexNum){
    adjacentTableGraph graph;

    vertex v;
    graph =(adjacentTableGraph)malloc(sizeof(struct gNode));
    graph->vertex_number=vertexNum;
    graph->edge_nunber=0;
    /*initialize the adjacent table*/
    for(v=0;v<graph->vertex_number;v++){
        graph->g[v].head=NULL;
    }
    return graph;
}

/*
insert a edge to graph.We will distinct oriented graph and undirected graph
The e->v1 and e->v2 are the vertexs' indexs in the adjacent table
@param graph The graph you want to insert edge
@param e The edge you want to insert the graph
@param isOriented Whether the graph is oriented graph.If the graph is oriented
        we will set adjacent table graph[v1]->head=v2 and set graph[v1].head=v2
        otherwise we only set graph[v1].head=v2
*/
void insertEdge(adjacentTableGraph graph,edge e,int isOriented){
    /*build node<v1,v2>*/
    ptrToAdjNode newNode;
    newNode =(ptrToAdjNode)malloc(sizeof(struct adjNode));
    newNode->adjVerx=e->v2;
    newNode->weight=e->weight;
    newNode->next = graph->g[e->v1].head;
    graph->g[e->v1].head=newNode;
    /*if the graph is directed graph*/
    if(!isOriented){
        newNode =(ptrToAdjNode)malloc(sizeof(struct adjNode));
        newNode->adjVerx=e->v1;
        newNode->weight = e->weight;
        newNode->next = graph->g[e->v2].head;
        graph->g[e->v1].head=newNode;
    }
}

/*
build a graph stored by adjacent table
*/
adjacentTableGraph buildGraph(){
    adjacentTableGraph graph;
    edge e;
    vertex v;
    int vertex_num,i;

    //printf("please input the quantity of the vertex:");
    scanf("%d",&vertex_num);
    graph  = createGraph(vertex_num);
    //printf("please input the quantity of the edges:");
    scanf("%d",&(graph->edge_nunber));
    if(graph->edge_nunber){
        e = (edge)malloc(sizeof(struct eNode));
        for(i=0;i<graph->edge_nunber;i++){
            scanf("%d %d %d",&e->v1,&e->v2,&e->weight);
            insertEdge(graph,e,1);
        }
    }

    /*if the vertex has name*/
    for(i=0;i<graph->vertex_number;i++){
        scanf(" %c",&(graph->g[i].data));
    }
    //printf("lala:%c,%c\n",graph->g[0].data,graph->g[1].data);
    //printf("lala:%d\n",graph->vertex_number);
    //printf("%c",graph->g[1].data);
    return graph;
}



/*==============================define a queue=====================================================*/
/*define a list to store the element in the queue*/
typedef ptrToVNode elementType;
typedef struct node *pList;
typedef struct node{
    elementType element;
    struct node *next;
};

/*define a queue to point the list*/
typedef struct node2 *pQueue;
typedef struct node2{
    pList front;    /*the front point to point the head of the list*/
    pList rear;     /*the rear point to point the rear of of the list*/
};

/*create a empty list to store the queue element*/
pList createEmptyList(){
    pList list;
    list = (pList)malloc(sizeof(struct node));
    list->next=NULL;
    return list;
}
/*create a empty queye*/
pQueue createEmptyQueue(){
    pQueue queue = (pQueue)malloc(sizeof(struct node2));
    queue->front=NULL;
    queue->rear=NULL;
    return queue;
}

/*
Wether the queue is empty
@param queue The queue need to adjust
@return If the queue is null,return 1 otherwise return 0
*/
int isQueueEmpty(pQueue queue){
    return(queue->front==NULL);
}

/*
Add a element to a queue,If the queue is null,we will create a new queue
@parama queue The queue we will add elememt to
@prama element The element we will add to queue
*/
void addQueue(pQueue queue,elementType element){
    if(isQueueEmpty(queue)){
        pList list = createEmptyList();
        list->element=element;
        queue->front=queue->rear=list;
    }else{
        pList newNode = (pList)malloc(sizeof(struct node));
        newNode->element = element;
        newNode->next = queue->rear->next;
        queue->rear->next=newNode;
        queue->rear=newNode;
    }
}

/*
delete a element from a queue
@param queue The queue will be deleted a element
@return The element has been deleted
*/
elementType deleteEleFromQueue(pQueue queue){
    if(isQueueEmpty(queue)){
        printf("the queue is empty,don't allow to delete elemet from it!");
    }else{
        pList oldNode = queue->front;
        elementType element = oldNode->element;
        if(queue->front==queue->rear){
            queue->rear=queue->front=NULL;
        }else{
            queue->front=queue->front->next;
        }
        free(oldNode);
        return element;
    }
}

/*
visite a graph's node
@param graph The graph to store the elements
@param v The index of vertex in the adjacent table
*/
void visit(adjacentTableGraph graph,vertex v){
    printf("%c ",graph->g[v].data);
}

/*
Breadth first search
@param graph The graph stored by the adjacent table
@param startPoint The point we start search 
@param visited A array to tag the elemeent whether has been visited
*/
void BFS(adjacentTableGraph graph,vertex startPoint,int *visited){
    ptrToAdjNode p;
    //printf("lala:%d",graph->g[3].head->adjVerx);
    visited[startPoint]=1;
    visit(graph,startPoint);
    pQueue queue = createEmptyQueue();
    addQueue(queue,&(graph->g[startPoint]));
    while(!isQueueEmpty(queue)){
        elementType element = deleteEleFromQueue(queue);
        //printf("lala:%d\n",element->head->adjVerx);
        for(p=element->head;p;p=p->next){
            if(visited[p->adjVerx]==0){
                visited[p->adjVerx]=1;
                visit(graph,p->adjVerx);
                addQueue(queue,&(graph->g[p->adjVerx]));
            }
        }
    }
}

/*
Depth first search a graph
@param graph The graph need to search
@param startPoint The fisrt point we start search the graph
@paran int *visited The array we use to tag the vertex we has accessed.
*/
void DFS(adjacentTableGraph graph,vertex startPoint,int *visited){
    ptrToAdjNode p;
    visit(graph,startPoint);
    p=graph->g[3].head;
    //printf("lala%d",p->adjVerx);
    visited[startPoint]=1;
    for(p=graph->g[startPoint].head;p;p=p->next){
        if(visited[p->adjVerx]==0){
        //printf("lala:%d",p->adjVerx);
            DFS(graph,p->adjVerx,visited);
        }
    }
}



int main(){
    int i;
    adjacentTableGraph graph=buildGraph();
    int visited[graph->vertex_number];
    for(i=0;i<graph->vertex_number;i++){
        visited[i]=0;
    }
    DFS(graph,0,visited);
    printf("\n");
    for(i=0;i<graph->vertex_number;i++){
        visited[i]=0;
    }
    BFS(graph,0,visited);
    printf("just test\n");
    return 0;
}

 

测试数据：

 

 

测试结果：