The seventh operation

Which course does this assignment belong to https://edu.cnblogs.com/campus/qdu/DS2020
What are the requirements for this assignment https://edu.cnblogs.com/campus/qdu/DS2020/homework/11472
The goal of this assignment Master the representation of adjacency matrix and adjacency table of graph; Master the depth first and breadth first search methods of map; Understand the application of graph
Student number 2018204231

1, Experimental purpose

1. Master the representation of adjacency matrix and adjacency table of graph
2. Master the depth first and breadth first search methods of map
3. Understand the application of graph

2, Experimental Preview

Explain the following concepts
1. Depth first search traversal:
Depth first search is a method that is widely used in the early stage of crawler development. Its purpose is to reach the leaf nodes of the searched structure (that is, those HTML files that do not contain any hyperlinks). In an HTML file, when a hyperlink is selected, the linked HTML file will perform a depth first search, that is, a single chain must be completely searched before searching the rest of the hyperlink results. Depth first search follows the hyperlink on the HTML file until it can't go further, then returns to an HTML file, and then continues to select other hyperlinks in the HTML file. When there are no other hyperlinks to choose from, the search has ended.
2. Breadth first search traversal:
Width first search algorithm (also known as breadth first search) is one of the simplest graph search algorithms. This algorithm is also the prototype of many important graph algorithms. Dijkstra single source shortest path algorithm and Prim minimum spanning tree algorithm adopt the idea similar to width first search. Its alias is BFS, which belongs to a blind search method. Its purpose is to systematically expand and check all nodes in the graph to find the results. In other words, it does not consider the possible location of the result and searches the whole graph thoroughly until it finds the result.
3. Topology sorting:
Topological sorting of a directed acyclic graph G is to arrange all vertices in G into a linear sequence, so that any pair of vertices u and v in the graph, if the edge < u, v > ∈ E(G), u appears before v in the linear sequence. Generally, such a linear sequence is called a sequence satisfying topological order, which is called topological sequence for short. In short, a partial order on a set is used to obtain a total order on the set. This operation is called topological sorting.
4. Minimum spanning tree:
The spanning tree of a connected graph with n nodes is the minimal connected subgraph of the original graph, contains all N nodes in the original graph, and has the least edges to keep the graph connected. In a given undirected graph G = (V, E), (u, v) represents the edge connecting vertex u and vertex v, and w(u, v) represents the weight of this edge. If there is a subset of T and an acyclic graph such that w(T) is the smallest, then t is the minimum spanning tree of G.
5. Shortest path:
It is used to calculate the shortest path from one node to all other nodes. The main feature is to take the starting point as the center and expand outward layer by layer until it reaches the end point. Dijkstra algorithm can get the optimal solution of the shortest path, but it is inefficient because it traverses many nodes.

3, Experiment contents and requirements

  • 1. Read and run the following program, and write the running results according to the input.
#include<stdio.h>
#define N 20
#define TRUE 1
#define FALSE 0
int visited[N];    
typedef struct    /*Definition of queue*/
{
    int data[N];
    int front,rear;
}queue;
typedef struct    /*adjacency matrix */
{
    int vexnum,arcnum;
    char vexs[N];
    int arcs[N][N];
}
graph;

void createGraph(graph *g);  /*An adjacency matrix of undirected graph is established*/
void dfs(int i,graph *g);    /*Depth first search from the ith vertex*/
void tdfs(graph *g);          /*Depth first search entire graph*/
void bfs(int k,graph *g);    /*Breadth first search from the k th vertex*/
void tbfs(graph *g);          /*Breadth first search entire graph*/
void init_visit();            /*Initialize access identity array*/

void createGraph(graph *g)   /*An adjacency matrix of undirected graph is established*/
{   int i,j;
    char v;
    g->vexnum=0;
    g->arcnum=0;
    i=0;
    printf("Input vertex sequence(with#End): (n ");
    while((v=getchar())!='#')
    {
        g->vexs[i]=v;        /*Read in vertex information*/
        i++;
    }
    g->vexnum=i;             /*Number of vertices*/
    for(i=0;i<g->vexnum;i++) /*Adjacency matrix initialization*/
        for(j=0;j<g->vexnum;j++)
            g->arcs[i][j]=0;
    printf("Enter information about the edge:\n");
    scanf("%d,%d",&i,&j);  /*Read in edge i,j*/
    while(i!=-1)              /*It ends when I is read in and j is - 1*/
    {
        g->arcs[i][j]=1;
        g->arcs[j][i]=1;
        scanf("%d,%d",&i,&j);
    }
}

void dfs(int i,graph *g) /*Depth first search from the ith vertex*/
{
    int j;
    printf("%c",g->vexs[i]);
    visited[i]=TRUE;
    for(j=0;j<g->vexnum;j++)
        if((g->arcs[i][j]==1)&&(!visited[j]))
            dfs(j,g);
}

void tdfs(graph *g)      /*Depth first search entire graph*/
{
    int i;
    printf("\n From vertex%C Start depth first search sequence:",g->vexs[0]);
    for(i=0;i<g->vexnum;i++)
        if(visited[i]!=TRUE)
            dfs(i,g);
}

void bfs(int k,graph *g)  /*Breadth first search from the k th vertex*/
{
    int i,j;
    queue qlist,*q;
    q=&qlist;
    q->rear=0;
    q->front=0;
    printf("%c",g->vexs[k]);
    visited[k]=TRUE;
    q->data[q->rear]=k;
    q->rear=(q->rear+1)%N;
    while(q->rear!=q->front)
    {
        i=q->data[q->front];
        q->front=(q->front+1)%N;
        for(j=0;j<g->vexnum;j++)
            if((g->arcs[i][j]==1)&&(!visited[j]))
            {
                printf("%c",g->vexs[j]);
                visited[j]=TRUE;
                q->data[q->rear]=j;
                q->rear=(q->rear+1)%N;
            }
    }
}

void tbfs(graph *g) /*Breadth first search entire graph*/
{
    int i;
    printf("\n From vertex%C Start breadth first search sequence:",g->vexs[0]);
    for(i=0;i<g->vexnum;i++)
        if(visited[i]!=TRUE)
            bfs(i,g);
}

void init_visit()   /*Initialize access identity array*/
{
    int i;
    for(i=0;i<N;i++)
        visited[i]=FALSE;
}

int main()
{
    graph ga;
    int i,j;
    createGraph(&ga);
    printf("Adjacency matrix of undirected graph:\n");
for(i=0;i<ga.vexnum;i++)
{
        for(j=0;j<ga.vexnum;j++)
            printf("%3d",ga.arcs[i][j]);
        printf("\n");
    }
    init_visit();
    tdfs(&ga);
    init_visit();
    tbfs(&ga);
    return 0;
}
  • According to the structure verification experiment in the right figure

  • Input:
    ABCDEFGH#
    0,1
    0,2
    0,5
    1,3
    1,4
    2,5
    2,6
    3,7
    4,7
    -1,-1

  • Operation results:

  • 2. Read and run the following program to supplement the topology sorting algorithm.

#include<stdio.h>
#include<malloc.h>
const int N=20;
typedef struct edgenode   /*Adjacency list of graph: adjacency linked list node*/
{
    int adjvex;  /*Vertex sequence number*/
    struct edgenode *next; /*Pointer to the next node*/
} edgenode;

typedef struct vnode  /*Adjacency table of graph: adjacency table*/
{
    char data;    /*Vertex information*/
    int ind;      /*Vertex penetration*/
    struct edgenode *link;  /*Pointer to adjacent linked list*/
} vnode;

int createGraph_list(vnode adjlist[],int *p); /*Establish adjacency table of directed graph*/
void topSort(vnode g[],int n); /*Topological sorting*/

int createGraph_list(vnode adjlist[],int *p)  /*Establish adjacency table of directed graph*/
{
    int i,j,n,e;
    char v;
    edgenode *s;
    i=0;
    n=0;
    e=0;
    printf("Input vertex sequence(with#End): (n ");
    while((v=getchar())!='#')
    {
        adjlist[i].data=v;        /*Read in vertex information*/
        adjlist[i].link=NULL;
        adjlist[i].ind=0;
        i++;
    }
    n=i;
    *p=n;
    /*Establish adjacency linked list*/
    printf("\n Please enter information about the arc(i=-1 end): i,j:\n");
    scanf("%d,%d",&i,&j);
    while(i!=-1)
    {
        s=(struct edgenode*)malloc(sizeof(edgenode));
        s->adjvex=j;
        s->next=adjlist[i].link;
        adjlist[i].link=s;
        adjlist[j].ind++;  /*The penetration of vertex j plus 1*/
        e++;
        scanf("%d,%d",&i,&j);
    }
    printf("Adjacency table:");
    for(i=0; i<n; i++) /*Output adjacency table*/
    {
        printf("\n%c,%d:",adjlist[i].data,adjlist[i].ind);
        s=adjlist[i].link;
        while(s!=NULL)
        {
            printf("->%d",s->adjvex);
            s=s->next;
        }
    }
    return n;
}

void topSort(vnode g[],int n)  /*Topological sorting*/
{
    printf("Enter a topological sort vertex sequence:\n");
    int i,j,k,m=0,top=-1;
    struct  edgenode *p;
    for (i=0; i<=n; i++)    //Stack vertices with zero degrees
        if (g[i].ind==0)
        {
            g[i].ind=top;
            top=i;
        }
    while (top!=-1)     //Stack is not empty
    {
        j=top;
        top=g[top].ind;     //Out of stack
        printf("%c",g[j].data);
        m++;
        p=g[j].link;
        while (p)       //Delete all edges of the node
        {
            k=p->adjvex;
            g[k].ind--;
            if (g[k].ind==0)        //Stack points with zero degree
            {
                g[k].ind=top;
                top=k;
            }
            p=p->next;
        }
    }
// if (m<n)
// printf("the graph has rings \ n");
}

int main()
{
    vnode adjlist[N];
    int n,*p;
    int m;
    p=&n;
    m=createGraph_list(adjlist,p);
    printf("\n");
    topSort(adjlist,m-1);
    return 0;
}
  • According to the input, the topological sorting sequence of the directed graph is output. And draw a directed graph.

  • Input:
    ABCDEF#
    0,1
    1,2
    2,3
    4,1
    4,5
    -1,-1

  • Operation results:

  • 3. Read and run the following program.

#include<stdio.h>
#define N 20
#define TRUE 1
#define INF 32766 / * infinite elements in adjacency matrix*/
#define INFIN 32767 / * number greater than infinity element*/

typedef struct
{ /*adjacency matrix */
    int vexnum,arcnum;
    char vexs[N];
    int arcs[N][N];
}
graph;

void createGraph_w(graph *g,int flag);
void prim(graph *g,int u);
void dijkstra(graph g,int v);
void showprim();
void showdij();

/*Establish the adjacency matrix of weighted graph. If flag is 1, it is undirected graph, and flag is 0, it is directed graph*/
void createGraph_w(graph *g,int flag)
{
    int i,j,w;
    char v;
    g->vexnum=0;
    g->arcnum=0;
    i=0;
    printf("Input vertex sequence(with#End): (n ");
    while((v=getchar())!='#')
    {
        g->vexs[i]=v;        /*Read in vertex information*/
        i++;
    }
    g->vexnum=i;
    for(i=0;i<6;i++)        /*Adjacency matrix initialization*/
        for(j=0;j<6;j++)
            g->arcs[i][j]=INF;
    printf("Enter information about the edge:\n");
    scanf("%d,%d,%d",&i,&j,&w);  /*Read in edge (i,j,w)*/
    while(i!=-1)              /*End when read in i is - 1*/
    {
        g->arcs[i][j]=w;
        if(flag==1)
            g->arcs[j][i]=w;
        scanf("%d,%d,%d",&i,&j,&w);
    }
}

void prim(graph *g,int u)/*Starting vertex u*/
{
    int lowcost[N],closest[N],i,j,k,min;
    for(i=0;i<g->vexnum;i++)  /*Find the weight of other vertices to the starting vertex u*/
    {
        lowcost[i]=g->arcs[u][i];
        closest[i]=u;
    }
    lowcost[u]=0;
    for(i=1;i<g->vexnum;i++)    /*Loop to find the edges in the minimum spanning tree*/
    {   min=INFIN;
        for(j=0;j<g->vexnum;j++)   /*Select to get an edge with the least cost*/
            if(lowcost[j]!=0&&lowcost[j]<min)
            {
                min=lowcost[j];
                k=j;
            }
        printf("(%c,%c)--%d\n",g->vexs[closest[k]],g->vexs[k],lowcost[k]);      /*Output this edge*/
        lowcost[k]=0;       /*Vertex k into the minimum spanning tree */
        for(j=0;j<g->vexnum;j++)  /*Find the weight from other vertices to vertex k*/
            if(g->arcs[k][j]!=0&&g->arcs[k][j]<lowcost[j])
            {
                lowcost[j]=g->arcs[k][j];
                closest[j]=k;
            }
    }
}

void printPath(graph g,int startVex,int EndVex)
{
    int stack[N],top=0;   /*stack*/
    int i,k,j;
    int flag[N];  /*Output path vertex flag*/
    k=EndVex;
    for (i=0;i<g.vexnum;i++) flag[i]=0;
    j=startVex;
    printf("%c",g.vexs[j]);
    flag[j]=1;
    stack[top++]=k;
    while (top>0) /*Path to k not found j*/
    {
        for (i=0;i<g.vexnum;i++)
        {
            if (path[k][i]==1 && flag[i]==0) /*j The path to k contains i vertices*/
            {
                if (g.arcs[j][i]!=INF )   /*j The path to i contains intermediate vertices*/
                {
                    printf("-> %c(%d) ",g.vexs[i],g.arcs[j][i]); 
                            /*Output the vertex i of the path from j to k*/
                    flag[i]=1;
                    j=i;
                    k=stack[--top];
                    break;
                }
                else
                {
                    if (i!=k) stack[top++]=i;  /*break;*/
                }
            }
        }
    }

void dijkstra(graph g,int v){  /*dijkstra Algorithm for single source shortest path*/
    int path[N][N],dist[N],s[N];
    int mindis,i,j,u,k;
    for(i=0;i<g.vexnum;i++){
        dist[i]=g.arcs[v][i];
        s[i]=0;
        for(j=0;j<g.vexnum;j++)
            path[i][j]=0;
        if(dist[i]<INF){
            path[i][v]=1;
            path[i][i]=1;
        }
    }
    dist[v]=0;
    s[v]=1;
    for(i=0,u=1;i<g.vexnum;i++){
        mindis=INFIN;
        for(j=0;j<g.vexnum;j++)
            if(s[j]==0)
                if(dist[j]<mindis){
                    u=j;
                    mindis=dist[j];
                }
        s[u]=1;
        for(j=0;j<g.vexnum;j++)
            if((s[j]==0)&&dist[u]+g.arcs[u][j]<dist[j]){
                dist[j]=dist[u]+g.arcs[u][j];
                for(k=0;k<g.vexnum;k++)
                    path[j][k]=path[u][k];
                path[j][j]=1;
            }
    }
    printf("\n vertex%c->Shortest path to each vertex\n",g.vexs[v]);
    for(i=0;i<g.vexnum;i++){
        printf("\n vertex%c->vertex%c: ",g.vexs[v],g.vexs[i]);
        if(dist[i]==INF||dist[i]==0)
            printf("no path");
        else{
            printf("%d  ",dist[i]);
            printf("Pass through vertex:");
            printPath(g,v,i);  /*Output v to i path*/
        }
    }
}

void showprim()/*Demonstration of minimum spanning tree prim algorithm*/
{
    graph ga;
    createGraph_w(&ga,1);
    prim(&ga,0);
}

void showdij(){   /*dijstra Algorithm demonstration*/
    graph ga;
    createGraph_w(&ga,0);
    dijkstra(ga,0);
}

int main(){
showprim(); /*prim Algorithm demonstration*/
getchar();
    showdij();  /*dijstra Algorithm demonstration*/
    return 0;
}
  • The following inputs verify the prim algorithm and dijstra algorithm respectively. The first part of the input instance is an undirected graph, and its minimum spanning tree is obtained; The second part of the input is a directed graph to find its shortest path.
    Minimum spanning tree shortest path
    ABCDEF#
    0,1,6
    0,2,1
    0,3,5
    1,2,5
    1,4,3
    2,3,5
    2,4,6
    2,5,4
    3,5,2
    4,5,6
    -1,-1,-1
    ABCDEF#
    0,2,10
    0,5,100
    0,4,30
    1,2,5
    2,3,50
    3,4,20
    3,5,10
    4,3,20
    4,5,60
    -1,-1,-1

  • Operation results:

4, Experimental summary
Master the representation of adjacency matrix and adjacency table of graph, grasp the depth first and breadth first search methods of graph, and understand the application methods of graph

Posted by denoteone on Sun, 08 May 2022 04:11:54 +0300