编程知识 cdmana.com

Data structure learning (4)

( One ) chart

linear relationship It's a one-to-one relationship , Trees It's a hierarchical one to many relationship , chart It's a many-to-many relationship .

In the linear table , Call the data element Elements , The tree structure refers to data elements as node , In the graph structure, data elements are called The vertices Vertex.

1.  Related definitions

(1)  chart
It consists of a finite nonempty set of fixed points and a set of edges between fixed points . Usually expressed as GV,E), among G Represents a graph .V The picture is G The set of fixed points in ,E The picture is G A collection in the middle .
(2)  No to the edge

The vertices Vi To Vj The edge between has no direction , I'm going to call this side theta No to the edge Edge), With unordered pairs (Vi,Vj) To express .

(3)  Undirected complete graph

There are edges between any two vertices , The graph is called Undirected complete graph .

(4)  There is a directional side

The vertices Vi To Vj The edge between has direction , I'm going to call this side theta There is a directional side Edge), Also known as arc , With an orderly couple <Vi,Vj> To express . among Vi yes Arctail ,Vj yes Arc head .

(5)  Simple picture

There is no vertex to its own edge , The same side doesn't repeat . Such a graph is called Simple picture .

(6)  A simple definition of a noun

Directed complete graph Sparse graph A dense picture power ( A number on an edge or an arc )、 Adjacency point , Attachment ( The edge is attached to two vertices ), The degree of the vertex ( The number of edges associated with the vertex )、 The degree of ( The number of arcs whose vertices are tails )、 The degree of ( The number of edges whose vertices are the heads of arcs )

(7)  network

A weighted graph is called a net Network.

(8)  route Path

( Need to verify ) From the top of the graph A To the top D The path of , It's a sequence of vertices (), In fact, it is a set of paths of interrelated edges . It's a collection of sides . Path length is the number of edges or arcs .

(9)  Ring

The same path from the first vertex to the last vertex is called loop perhaps Ring . In sequence , A path whose vertices do not recur is called Simple path . Except for the first and last , The loop where the rest of the vertices do not recur is called Simple circuit .

(10)  Subgraphs

Suppose two graphs G=V,E) and G’=V’,E’, If V yes V Subset ,E yes E Subset . said G’ yes G The subtree of .

(11)  Connected graph

There is a path between two nodes , We call them two nodes connected . If any two nodes in the graph are connected , The graph is called Connected graph . In the undirected graph , It is called the polar graph Connected component .

(12)  Connected graph spanning tree

Is a minimal connected subgraph , Contains all of the graphs N vertices , But only enough to make a tree N-1 side .

2.  Storage structure

(1)  Adjacency matrix

The adjacency matrix of a graph is stored in two arrays , A one-dimensional array stores vertex information in the way . A two-dimensional array ( It's called adjacency matrix ) Store arc or edge information in a graph .

Adjacency matrix of undirected graph is symmetric matrix . Adjacency matrix is convenient to calculate the degree of vertex .

(2)  Adjacency list

Use an array to store vertex information , Use a linked list to store information about the edges of vertices . This combination of array and linked list is called adjacency linked list .

The data structure of the vertex is Data fields data And pointer fields first_edge.

Adjacency table is suitable for storing undirected graphs . Because there is no problem of getting in and out of the way . If you store a digraph , Can only store out of the arc ( Adjacency list ) Or choose the arc to store in degrees ( Inverse adjacency list ). Choose one . For example, choose out the degree , Then, the calculation of the node penetration needs to traverse the whole graph . Calculation is troublesome .

(3)  Cross linked list

Combine adjacency list and inverse adjacency list .

The data structure of vertex element is data domain data And two pointer fields first_in and first_out.

The vertices are stored in the array Vertex table in .

Edge table node structure tail_vex yes The starting point of the arc is Vertex table The subscript ,head_vex It's the end of the arc at Vertex table The subscript ,head_link Is the pointer field of the input side table , Point to the next side with the same end point .tail_link It's the out side pointer field , Point to the next side with the same starting point .

(4)  Adjacency multiple tables
(5)  Edge set array

There are two one-dimensional arrays . One stores vertex information , Another store side information . Edge information data element is the starting point subscript of edge begin, End subscript end And weights weight.

3.  Graph traversal

Starting from a vertex of a graph , Traverse the rest of the vertices in the graph . And each vertex is accessed only once and only once . This process is called Graph traversal .

(1)  Graph depth first traversal

Depth-first traversal (Depth_First_Search), Also known as depth first search . abbreviation DFS.

From a vertex of a graph V set out , Access this vertex . And then from V Of the adjacent points that are not accessed , Depth first traversal graph , Until all and V All vertices with the same path are visited . If there are no vertices in the graph that have not been accessed , Select another vertex that is not visited as the starting point , Repeat the process , Until all vertices in the graph are accessed .

Adjacency matrix Depth-first algorithm

There are two layers of operation .

first floor : Traversing the vertex table , Each vertex is set to be untouched . Next, traverse each node , If the node is not accessed , Call Depth first recursive algorithm of adjacency matrix .

The second floor : The depth priority recursive algorithm of adjacency matrix is implemented . First visit the node , Set the node has been accessed . Then traverse the one-dimensional array of data corresponding to the node in the adjacency matrix . The essence is to traverse the node adjacent to the current vertex . Recursively call its own method .

 

  1. bool visited[MaxVnum];  
  2. void DFS(Graph G,int v)  
  3. {  
  4. visited[v]= true; // from V Start visiting ,flag it   
  5. printf("%d",v);    // Print out V  
  6. for(int j=0;j<G.vexnum;j++)   
  7. if(G.arcs[v][j]==1&&visited[j]== false) // Here you can get V Never visited adjacency points   
  8. DFS(G,j); // Recursively call , If all nodes have been accessed , Just go back , Instead of calling here DFS  
  9. }  
  10. void DFSTraverse(Graph G) {  
  11. for (int v = 0; v < G.vexnum; v++)  
  12. visited[v] = false; // I haven't been interviewed at first   
  13. for (int v = 0; v < G.vexnum; ++v)  
  14. if (visited[v] == false) // Never traverse the graph from the first element that has not been accessed   
  15. DFS(G, v);  
  16. }

 

l  Adjacency table depth first algorithm

There are two layers of operation .

first floor : Traversing the vertex table , Each vertex is set to be untouched . Next, traverse each node , If the node is not accessed , Call Adjacency list depth first recursive algorithm .

The second floor : Adjacency list depth first recursive algorithm implementation . First visit the node , Set the node has been accessed . Then traverse the linked list of adjacency lists . The essence is to traverse the node adjacent to the current vertex . Recursively call its own method .

The code is as follows :

  1. typedef int Boolean;//Boolean It's the boolean type , Its value is TRUE or FALSE  
  2. Boolean visited[100];  
  3. // Depth first recursive algorithm of adjacency table   
  4. void DFS(GraphAdjList GL, int i) {  
  5. EdgeNode *p;  
  6. visited[i] = 1;  
  7. cout << GL.adjList[i].data << " ";// Print vertex , You can do something else   
  8. p = GL.adjList[i].firstedge;  
  9. while (p) {  
  10. if (!visited[p->adjvex])  
  11. DFS(GL, p->adjvex);// Call recursively on the adjacent vertices that are not accessed   
  12. p = p->next;  
  13. }  
  14. }  
  15. // Depth traversal operation of adjacency table   
  16. void DFSTraverse(GraphAdjList GL) {  
  17. int i;  
  18. for (i = 0; i < GL.numVertexes; i++) {  
  19. visited[i] = 0;// All initial vertex states are not accessed   
  20. }  
  21. for (i = 0; i < GL.numVertexes; i++) {  
  22. if (!visited[i])// Call... On a vertex that has not been visited DFS, If it's a connected graph , It's only going to be executed once   
  23. DFS(GL, i);  
  24. }  
(2)  Graph breadth first traversal

Breadth first traversal (Breadth_First_Search), Also known as breadth first search . abbreviation BFS

l  Graph breadth first traversal of adjacency matrix

Divided into three layers ; first floor , Set all vertices in all vertex table as not accessed . And then traverse all the vertices , Access vertex data , And set the current vertex has been accessed . Visited the vertex and joined the queue .

The second floor : Pop up the vertex elements of the first layer , Traverse the adjacent nodes that access the visited vertices 【 A row of data corresponding to the adjacency matrix 】. It's equivalent to accessing layer 2 data . After the visit , Join the queue in the order of access .

The third level : There's data in the queue , Will continue to pop up data , Process layer 3 data one by one . Go down in turn . Until all nodes have been processed .

l  Graph breadth first traversal of adjacency list

The breadth first processing of adjacency list is consistent with that of adjacency matrix . It's just that the way to remove the next layer of data is inconsistent . Adjacency matrix is to take a row of data , Adjacency list is just a linked list .

4.  Minimum spanning tree

The minimum spanning tree is called the minimum spanning tree . Personal understanding : It can connect all nodes , And the connection cost is the least . It has great practical significance . There's a network of places , And it costs the least .

(1)  Prim algorithm

hypothesis N=V,{E}} It's a connected network ,TE yes N The set of edges in the minimal spanning tree on . Algorithm from U=U0}(U0 yes V The elements of ),TE={} Start . Repeat the following : Satisfy a vertex on all edges U in , The other vertex is at V-U In the middle , Select an edge with the smallest weight . As TE The elements of . meanwhile ,TE Put all the vertices in U in . Then continue with the above operation , until U=V. be T Namely N The minimum spanning tree of .

(2)  Kruskal algorithm

5.  Shortest path

The shortest path is the path between two vertices with the smallest sum of weights on the edge . And we call the first node the source point , The last vertex is the end .

6.  A topological sort

l  Definition

In a directed graph that represents a project , use The vertex represents activity , use The arc represents the priority relationship between activities , This digraph is Vertices represent active nets , We become AOV network .AOV The arc of the network represents a certain restriction between activities .

The topological sequence : set up G=V,E} Is a n Digraphs with vertices ,V The sequence of vertices in V1V2 ... Vn, Satisfaction from the top i To the top j There is a path . Then in the vertex sequence, the vertex Vi It must be at the top Vj Before . We call such a sequence of vertices The topological sequence .

So-called A topological sort , In fact, it is the process of constructing topological sequence for a directed graph .

l  Algorithm

from AOV In the network, choose a degree of entry 0 The vertex output of , Then delete this vertex , And delete the arc whose tail is the vertex ( The penetration of the vertex corresponding to the end of the arc needs -1), Continue to repeat this step . Until all the vertices or AOV There is no vertex in the net. The degree of penetration is 0 To the top of .

Code ideas

1 Define a stack (stack) Store vertex numbers without degrees , Definition top Point to the top of the stack , Definition count Record the number of output vertices , In order to determine whether there is a ring .

2 initialization stack, Put all the entries into 0 The top of the stack .

3 Loop with stack not empty : Out of the stack , And print this vertex information ,count++. And then through the loop The adjacency list of the vertex , And the penetration of the arc head in Minus one , If in be equal to 0, The vertex needs to be put on the stack .

4 Finally, judge count Is it equal to the number of vertices

The code is as follows

  1. int TopologicalSort(GraphVerter G)  
  2. {  
  3. EdgeNode *e;  
  4. int i;  
  5. int top = 0;  
  6. int gettop;  
  7. int count = 0;  
  8. int *stack;  
  9. stack = (int *)malloc(G.numvertexes * sizeof(int));   // Create a stack
  10. for(i = 0; i < G.numvertexes; i++)  
  11. {  
  12. if(G.verter[i]->in == 0)  
  13. stack[++top] = i;  //  The degree of 0 The top of the stack
  14. }  
  15. while(top != 0)   //  When the stack is not empty, the stack is looped out 、 Handle
  16. {  
  17. gettop = stack[top--];  
  18. printf("%d",G.verter[gettop]->data);  
  19. count++;  
  20. for(e = G.verter[gettop]->firstedge; e ; e = e->next)  
  21. {  
  22. G.verter[e->adjvex]->in--;  // The penetration of the vertex of the arc head -1
  23. if(G.verter[e->adjvex]->in == 0)  // -1 If it is 0, The stack
  24. stack[++top] = e->adjvex;  
  25. }  
  26. }  
  27. if(count < G.numvertexes)   // count == G.numvertexes  Represents that all vertices are in a topological sequence
  28. return 0;  
  29. else  
  30. return 1;  

7.  critical path

Topological sorting mainly solves the problem whether a project can be carried out in sequence . The critical path is to solve the problem of the shortest time needed to complete the project .

(1)  Definition

l AOE network

In a weighted directed graph that represents a project , use A vertex represents an event , Using digraphs Side means activity , Use the edge of The weight is the duration of the activity . This kind of directed graph edge represents the active net , be called AOE network .

AOV Net and AOE The difference between the web :

AOV A net uses vertices to represent events , It only describes the constraints between activities .

AOE Network is based on the restriction between activities without contradiction . And then analyze how much time it takes for the whole project . Or in order to shorten the time required for the project , Problems that need to be accelerated .

l  Key activities

Every activity on the path ( arc ) The sum of the duration is called The length of the path . From the source point to the sink point there is The maximum length of the path be called critical path . Activities on the critical path are called Key activities . Only by shortening the time of critical activities on the critical path , In order to reduce the length of the construction period .

(2)  Algorithmic thought

 

 

 

Four necessary parameters , The first two are for vertices , The last two are for the side

The earliest time of the event etvearliest time of vertex The vertices Vi The earliest occurrence time of .

Latest incident time ltvlastest time of vertex

The vertices Vi The latest time it happened , If it is exceeded, the whole construction period will be delayed .

The earliest start time of the activity eteearliest time of edge

edge Eg The earliest time of occurrence .

The latest start time of the activity ltelastest time if edge

edge Eg At the latest . The latest starting time of the project shall not be delayed .

 

 

 

 

The earliest time of occurrence : Suppose the starting point is vo, We call it from v0 To vi The length of the longest path of is vi Of The earliest time of occurrence understand :Vi For an event , It happens, which means that everything it depends on happens . From Vo All the routes from the departure arrive Vi It's about . Since it all happened , So the longest path has happened . therefore , This is a Vi The earliest occurrence time of

meanwhile ,vi The earliest occurrence time of is also all with vi Represented by the arc of the tail The earliest start time of the activity , The earliest start time of each event is the starting time of the arc of the event, and the time of drunkenness ). Use e(i) It means activity ai The earliest time of occurrence , besides , We also defined a The latest time of the event , Use l(i) Express , The latest starting time of the project shall not be delayed . We put e(i)=l(i) The activities of ai be called Key activities , therefore , This condition is that we ask for a AOE- The key to the critical path of the network is .

What we are asking for now is that each arc corresponds to e(i) and l(i), The formula for these two variables is

e(i)=ve(j) ; 

l(i)=vl(k)-dut(<j,k>) ;

 

A variable is introduced

First, let's assume that the activity ai) It's an arc <j,k> Activities on ,j Is the end of the arc ,k For the arc head ( The side with the arrow ), vej) It's the tail of the arc j The earliest occurrence time of , vlk) It represents the arc head k The latest time of occurrence of dut<j,k>) Represents the duration of the event , Is the weight of the arc

 

Algorithmic thought

To prepare two arrays ,a: Earliest start time array etv,b: Latest start time array .( For a vertex is an event

1. From the source V0 set out , Make etv[0]( Source point )=0, Find the earliest occurrence time of other vertices according to topological order etv[i]1 i n-1). At the same time, according to the previous chapter

The method of topological sorting detects whether there is a ring .

2. From the meeting point Vn set out , Make ltv[n-1] = etv[n-1], The latest occurrence time of each other vertex is calculated according to topological order ltv[i]n-2 i 2;

3. According to the vertex of etv and ltv The value of the array , Find the arc ( Activities ) The earliest and the latest start time of , Find whether the earliest start time and the latest start time of each arc are equal , If equal , It's the key activity .

Be careful :1,2 Finish it ( event ) The earliest and the latest .3 Calculate the earliest and the latest activities based on events , So we can find the arc ( Activities ) Is it a key activity .

 

 

(3)  Critical path algorithm

①  Improved topology algorithm , Calculate each of the The vertices The earliest occurrence time of .

  1. int TopplogicalSort(GraphAdjList *g)  
  2. {  
  3. int count=0;  
  4. eNode *e=NULL;    
  5. StackType *stack=NULL;  
  6. StackType top=0;  
  7. stack = (StackType *)malloc((*g).numVextexs*sizeof(StackType));    
  8. int i;  
  9. // Initializing the topological sequence stack   
  10. g_topOfStk = 0;  
  11. // Open the earliest start time array corresponding to the topological sequence stack   
  12. g_etv = (int *)malloc((*g).numVextexs*sizeof(int));  
  13. // Initialize array   
  14. for (i=0;i<(*g).numVextexs;i++)  
  15. g_etv[i]=0;        
  16. // Open up the stack of vertex array of topological sequence   
  17. g_StkAfterTop = (int *)malloc(sizeof(int)*(*g).numVextexs);  
  18. // The degree of 0 The top of the stack   
  19. for (i=0;i<(*g).numVextexs;i++)  
  20. if (!(*g).adjList[i].numIn)  
  21. stack[++top] = i;      
  22. while(top)  
  23. {  
  24. int geter = stack[top];  
  25. top--;    
  26. // Save the topological sequence to the topological sequence stack , Prepare for the back  ,stack in The first to go out of the stack g_StkAfterTop At the bottom of the stack .stack in The last element that comes out of the stack is placed in  g_StkAfterTop Top of stack
  27. g_StkAfterTop[g_topOfStk++] = geter;    
  28. count++;    
  29. // Get the current point out of degree , Subtract one from the degree of entry to the out of degree point ( The current point should be plotted ).  
  30. // Get the current vertex out of degree point table   
  31. e = (*g).adjList[geter].fitstedge;  
  32. while(e)          {  
  33. int eIdx = e->idx;  
  34. // Subtract one from the entry of the selected exit point   
  35. int crntIN = --(*g).adjList[eIdx].numIn;  
  36. if (crntIN == 0)  
  37. // If 0, It means that the vertex is not in degree , It's the next round of output .  
  38. stack[++top] = eIdx;        
  39. // Find the critical path    The earliest occurrence time of the vertex
  40. if ((g_etv[geter] + e->weigh) > g_etv[eIdx])  
  41. {                  g_etv[eIdx] = g_etv[geter] + e->weigh;              }  
  42. e = e->next;  
  43. }  
  44. }  
  45. if (count < (*g).numVextexs)  {// If the graph itself is a large ring , Or the graph contains rings , So the vertices with rings don't go into the stack and print out .  
  46. return false;    }  
  47. else{  
  48. printf("finish\n");  
  49. return true;    }  
  50. }  

②  Critical path code

  1. void CriticalPath(GraphAdjList g)  
  2. {  
  3. int i;  
  4. int geter;  
  5. eNode *e = NULL;  
  6. g_topOfStk--;  
  7. //1. The latest start time of initialization array ( The earliest start time of meeting point ( initial value ))  
  8. g_ltv = (int *)malloc(sizeof(int)*g.numVextexs);  
  9. for (i=0;i<g.numVextexs;i++)  
  10. {  
  11. g_ltv[i] = g_etv[g.numVextexs-1];  
  12. }  
  13. //2. Find the latest start time of each point , From the sink point .  
  14. while (g_topOfStk)  
  15. {  
  16. // Get the current stack ( trans ) The serial number of   
  17. geter = g_StkAfterTop[g_topOfStk--];  
  18. // For each exit point   
  19. if (g.adjList[geter].fitstedge != NULL)  
  20. {  
  21. e = g.adjList[geter].fitstedge;  
  22. while(e != NULL)  
  23. {  
  24. int eIdx = e->idx;  
  25. if (g_ltv[eIdx] - e->weigh < g_ltv[geter])  
  26. {  
  27. g_ltv[geter] = g_ltv[eIdx] - e->weigh;  
  28. }  
  29. e = e->next;  
  30. }  
  31. }  
  32. }  
  33. int ete,lte;// The earliest and latest start time of the activity   
  34. printf("start:->");  
  35. //3. Ask for key activities , namely ltv and etv equal   
  36. for (i=0;i<g.numVextexs;i++)  
  37. {  
  38. if (g.adjList[i].fitstedge)  
  39. {  
  40. e = g.adjList[i].fitstedge;  
  41. while(e)  
  42. {  
  43. int eIdx = e->idx;  
  44. // Activities (i->eIdx) Earliest start time : event ( The vertices ) i Earliest start time   
  45. ete = g_etv[i];  
  46. // Activities (i->eIdx) The latest start time : event ( The vertices ) eIdx  The latest start time   subtract   Duration of the event   
  47. lte = g_ltv[eIdx] - e->weigh;  
  48. if (ete == lte)  
  49. {  
  50. printf("(%c - %c)->",g_init_vexs[i],g_init_vexs[eIdx]);  
  51. }  
  52. e= e->next;  
  53. }  
  54. }  
  55. }  
  56. printf(" end\n");  
  57. }  

版权声明
本文为[It lost schoolboy]所创,转载请带上原文链接,感谢

Scroll to Top