# The seventh job: graph representation and traversal

Which course does this assignment belong to data structure
What are the requirements for this assignment https://edu.cnblogs.com/campus/qdu/DS2020/homework/11430
The goal of this assignment Master the representation of adjacency matrix and adjacency table of graph, the depth first and breadth first search methods of graph, and understand the application methods of graph
Student number 2018204150

### Graph representation and traversal of Experiment 4

#### 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 widely used in the early stage of crawler development. Its purpose is to achieve the leaf nodes of the searched structure. 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: 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. Topological 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.
5. Shortest path: 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.

#### 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;
{
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())!='#')
{
i++;
}
g->vexnum=i;             /*Number of vertices*/
for(j=0;j<g->vexnum;j++)
g->arcs[i][j]=0;
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);
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);
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);
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 figure below 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;
{
struct edgenode *next; /*Pointer to the next node*/
} edgenode;

{
char data;    /*Vertex information*/
int ind;      /*Vertex penetration*/
} vnode;

void topSort(vnode g[],int n); /*Topological sorting*/

{
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())!='#')
{
i++;
}
n=i;
*p=n;
scanf("%d,%d",&i,&j);
while(i!=-1)
{
s=(struct edgenode*)malloc(sizeof(edgenode));
adjlist[j].ind++;  /*The penetration of vertex j plus 1*/
e++;
scanf("%d,%d",&i,&j);
}
for(i=0; i<n; i++) /*Output adjacency table*/
{
while(s!=NULL)
{
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++;
while (p)       //Delete all edges of the node
{
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()
{
int n,*p;
int m;
p=&n;
printf("\n");
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.

```#define N 20
#define TRUE 1
#define INF 32766 / * infinite elements in adjacency matrix*/
#define INFIN 32767 / * number greater than infinity element*/

typedef struct
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())!='#')
{
i++;
}
g->vexnum=i;
for(j=0;j<6;j++)
g->arcs[i][j]=INF;
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;
{
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]);
/*The output of path k to vertex j*/
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:
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
Shortest path:
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

Through this experiment, I have mastered the graph depth first and breadth first search algorithms, and understood the structural characteristics of the graph and its related applications. I have gained a lot. Keep going!

Posted by Toby on Sat, 07 May 2022 14:58:23 +0300