Graph

Question 1

Graph : Types of edge

Answer 1

Question 2

Graph : Weight & Unweighted

Answer 2

Question 3

Graph : Simple Graph

Answer 3

Question 4

Graph : Multi Graph

Answer 4

Question 5

Graph : Complete Graph

Answer 5

Question 6

Graph : Pseudo Graph

Answer 6

Question 7

Graph : Acyclic Graph

Answer 7

Question 8

Graph : Basic Properties of Graph

Answer 8

Question 9

Graph : Walk & Path & Trail

Answer 9

Question 10

Graph : Connected & Strongly Connected

Answer 10

Question 11

Graph : Adjency Matrix & Adjency List

Answer 11

In summary, the choice between adjacency matrix and adjacency list depends on the characteristics of the graph and the operations to be performed on it.
If the graph is dense or operations like checking for the existence of edges between vertices are frequent, an adjacency matrix might be more suitable.
If the graph is sparse or memory efficiency is important, an adjacency list is usually preferred.

Question 12

Undirected Graph : Def Structure (AdjList)

Answer 12

Question 13

Undirected Graph : newListNode (AdjList)

Answer 13

Question 14

Undirected Graph : CreateGraph (AdjList)

Answer 14

Question 15

Undirected Graph : addEdge (AdjList)

1️⃣[src]head
2️⃣[dst]head

{
1.newnode
2.link :
From src to dst
From dst to src
}

Answer 15

Question 16

Undirected Graph : DeleteEdge (AdjList)

Hints:
1.prev
2.current
3.find dst in array[src]
4.link
5.delete
6. Delete (in array [ dst ]) :
redo 3-5 procedures

Answer 16

Question 17

Undirected Graph : addVertice (AdjList)

Hint :
1.newV
2.realloc
3.intialize array [newV -1]
4.for : link new vertices to each previous vertices
5. update V in Graph

Answer 17

In undirected graph, add a new vertice means it is connected to each previous vertices.

Question 18

Undirected Graph : deleteVertice (AdjList)

Hint :
1.current (in array [vertex])
2.next
3.while : delete every node in the array [vertext]
4.delete from dst to src :
for:
1️⃣current
2️⃣while: find related node
3️⃣link
4️⃣free

We can add the codes below to make it more precise.
5.move all the AdjNodes in each head forward
6.resize array

Answer 18

Question 19

Graph : PrintGraph (AdjList)

Answer 19

Question 20

Directed Graph : addEdge (AdjList)

Hints :
1.newnode
2.link

Answer 20

对比无向图，少了增加从dst到src的边的步骤

Question 21

Directed Graph : DeleteEdge (AdjList)

Hints:
1.prev
2.current (array [src].head )
3.while : find the node
4.link
5. free

Answer 21

对比无向图，少了删除从dst到src的边的步骤

Question 22

Directed Graph : addVetice (AdjList)

Hint :
1.newV
2.realloc
3.intialize array [newV -1]
4.for : link new vertices to vertices mentioned in the input value
5. update V in Graph

Answer 22

Question 23

Directed Graph : deleteVetice (AdjList)

Hint :
1.current (in array [vertex])
2.next
3.while : delete every node in the array [vertext]
4.delete from dst to src :
for:
{
if:
1️⃣current
2️⃣while: find related node
3️⃣link
4️⃣free
}
5.move all the AdjNodes in each head forward
6.resize array

Answer 23

Question 24

Graph : addition in deleteVetice （AdjList)

How to implement the following instructions?

1.move all the AdjNodes in each head forward
2.resize array

Answer 24

Question 25

Graph: Difference between Basic Operations ( AjdList)

Answer 25

**The code for adding or deleting edges may appear similar at first glance, but the final impact differs due to the fundamental differences between directed and undirected graphs.** In a directed graph, edges have a specific direction, meaning each edge goes from one vertex to another. Therefore, when adding or deleting an edge, you must consider this directionality, and operations such as deleting a vertex may involve searching for and removing both incoming and outgoing edges.In an undirected graph, edges do not have a direction, and each edge represents a bidirectional connection between two vertices. Thus, when adding or deleting an edge, you don't need to consider directionality, and operations such as deleting a vertex involve only removing edges directly connected to that vertex. So, even though the code may look similar, the final impact varies because of the underlying definitions and properties of directed and undirected graphs, which dictate how edges are added, deleted, and represented within the graph structure.

Question 26

Graph : def structure (Adj Matrix)

Answer 26

Question 27

Graph : iniEdge (Adj Matrix) Hint : 1.vertice 2.edge 3.initialise

Answer 27

Question 28

Graph : addEdge (Adj Matrix) Hints 1.if : 1️⃣from src to dst 2️⃣from dst to src (remove in directed graph) 3️⃣edge ++ else : invalid

Answer 28

Question 29

Graph : deleteEdge (Adj Matrix) Hints 1.if : 1️⃣from src to dst 2️⃣from dst to src (remove in directed graph) 3️⃣edge -- (4️⃣ Edge didn't exist) else : invalid

Answer 29

Question 30

Graph : addVertex (Adj Matrix) Hints 1.if : 1️⃣ Vertex ++ 2️⃣for : 1. ini last row 2.ini last column else : full

Answer 30

Question 31

Graph : deleteVertex (Adj Matrix) Hints : 1.if : 1️⃣for: delete edges from vertex 2️⃣for : delete edges to vertex 3️⃣for: cover deleted vertex 4️⃣ vertices -- else: Invalid

Answer 31

Question 32

Graph : PrintGraph (Adj Matrix)

Answer 32

Question 33

Directed graph & Undirected graph : BFS algorithm (AdjMatrix) Hints : 1.visited 2.queue & enqueue (s) (mark as visited before enqueue) 3.while : { 1️⃣ dequeue ------------- 2️⃣Enqueue : for () ( if :(s from dequeue 's neighbours unvisted) 1.mark as visited 2.enqueue ) 4.free (queue & visited)

Answer 33

Question 34

Disconnected graph: BFS algorithm (AdjMatrix) 1.visited 2.for : if : BFS

Answer 34

Question 35

Directed graph & Undirected graph : BFS algorithm (AdjList) Hints : 1.visited 2.queue & enqueue (s) (mark as visited after enqueue) 3.while : { 1️⃣ dequeue ------------- 2️⃣Enqueue : 1.temp 2.while : 1.adjvertex 2.if (unvisted ( visited enqueue ) } 4.free (queue & visited)

Answer 35

Question 36

Disconnect graph : BFS algorithm (AdjList) Hints: 1.visited [ ] 2.call BFS

Answer 36

Question 37

BFS :

Answer 37

Question 38

Graph ： an easy way to create graph (Adj Matrix)

Answer 38

Question 39

Graph : DFS (Adj Matrix) Hints : 1. mark as visited 2.printf 3.for : { if : } DFS every unvisted nodes of the chosen vertex

Answer 39

It also works in directed graph, undirected graph and disconnected graph.

Question 40

Graph : DFS Traversal (Adj Matrix) Hints : for : (view each vertex as independent graph)

Answer 40

It also works in directed graph, undirected graph and disconnected graph.

Question 41

Graph : DFS (Adj List) Hints : 1. mark 2.printf 3.while : { if: } DFS every unvisted nodes of the chosen vertex

Answer 41

It also works in directed graph, undirected graph and disconnected graph.

Question 42

Graph : DFS Traversal (Adj List) Hints : for : (view each vertex as independent graph)

Answer 42

It also works in directed graph, undirected graph and disconnected graph.

Question 43

Graph :Prim Algorithm Hints: 1.又叫加点法 2.一开始的集合 V只有一个点

Answer 43

Question 44

Graph :Kruskal Algorithm Hints: 1.又叫加边法 2.一开始的集合 V有所有的点

Answer 44

Question 45

Graph : Kruakal Algorithm 特殊情况

Answer 45

Question 46

例题 ：最小生成树

Answer 46

Question 47

例题 ：Prim & Kruakal Algorithm

Answer 47

Question 48

Grpah : def structure **concisely** (AdjList)

Answer 48

Question 49

Graph : See BFS explicitly

Answer 49

Question 50

Graph : detail in BFS Algorithm

Answer 50

因为要先展开 A的邻接点 （图中的b、c）

Question 51

Graph : See DFS explicitly

Answer 51

Hints :we can use a stack to simulate the process

Question 52

例题 ：已知 图 AdjList ，求BFS 、DFS结果

Answer 52

Question 53

Graph : Adj Matrix

Answer 53

In weighted graph :

Question 54

Graph : What's Spanning Tree?

Answer 54

Question 55

Graph : Dijkstra Algorithm - Priority Queue

Answer 55

Question 56

Dijkstra Algorithm : how the first vertice is added

Answer 56

Question 57

Dijkstra Algorithm : how the n th vertice is added (n >1)

Answer 57

Question 58

Dijkstra Algorithm : Print list

Answer 58

Question 59

Dijkstra Algorithm : minDistance Hint :(To find the vertex in list with min distance from source) 1.INT_MAX ,min_index 2.for { if ( unvisted &

Answer 59

Question 60

Dijkstra Algorithm : Dijkstra Hints : 1.dist,prev 2.visited 3.initialize 4.for : { 1.minDistance 2.update dist & prev 3.mark as visited } 5.printGraph

Answer 60

Question 61

Graph : Prim Algorithm Hints: 1.parent,key,mstSet 2.intialize 3.choose original node 4.for (all vertices) {1️⃣for : find smallest key isn't in mstSet 2️⃣insert u into mstSet 3️⃣check u 's neighbours : 1. if u -> v < key [v] 2.up date parent & key } 5.printf : the smallest distance between each pair of vertex.

Answer 61

Question 62

Graph : a simple way to def graph (AdjList) For the implementation of Kruskal Algorithm

Answer 62

Question 63

Graph : 最小生成树 （Minimum Cost Spanning Tree) & 最短路径（Shortest Path ）的不同

Answer 63

Question 64

Graph : difference of Prim Algorithm & Kruakal Algorithm

Answer 64

Both of them can find Minimum Cost Spanning Tree.But Kruskal's algorithm is often preferred when the graph is sparse (i.e., few edges), while Prim's algorithm tends to perform better on dense graphs.

Question 65

Graph : Floyd Algorithm Hints : 1.intialise 2.for ( k matrix) { for : find smallest distance from i to j } 3.print

Answer 65

Question 66

Graph : How to calculate the matrix in **Floyd Algorithm**

Answer 66

Question 67

Graph : 关键路径 - AOE网

Answer 67

Question 68

Graph : 关键路径例题 - 求分别求 事件 、活动 的最早、最迟时间 & 关键活动

Answer 68

Question 69

Graph : 关键路径例题 ：运用关键路径最本质的性质

Answer 69

Question 70

Graph : 什么是拓扑排序？

Answer 70

Question 71

Graph : 拓扑排序例题 Hint :看第二个图就可以了

Answer 71

Question 72

Disjoint Set : how Parents array works?

Answer 72

Question 73

Disjoint Set : Root Algorithm Impact : to check if it has circle

Answer 73

Question 74

Disjoint Set : unionSet (without considering rank)

Answer 74

Question 75

Disjoint Set : explanation for why we need to consider rank in unionSet function

Answer 75

Question 76

Disjoint Set : unionSet ( consider rank)

Answer 76

Question 77

Graph : SortEdge function for Kruskal Algorithm

Answer 77

Question 78

Graph : Kruskal Algorithm Hints : 1.parent 2.ini parent 3.sortEdge 4.result 5.while { if ( no circle ) : 1.enqueue result 2.union } 6.print

Answer 78

You have to know each edge contains weight,src and dst.

Question 79

Critical Path : ES EL LS LF

Answer 79

Question 80

Critical Path : What's Critical Activity?

Answer 80

Question 81

Critical Path : Details for determining EF & LS

Answer 81

Question 82

Critical Path : Def Hints : 1.task 2.dependency

Answer 82

Question 83

Critical Path : calculateEarliest Hints : 1.for : { 1️⃣ini 2️⃣for ( if () ( update i .ES ) 3️⃣update i.EF }

Answer 83

Question 84

Critical Path : calculateLatest Hints : for : { 1️⃣ini 2️⃣for ( if () ( update i .LF ) 3️⃣update i.LS }

Answer 84

Question 85

Critical Path : FindCriticalPath

Answer 85

Question 86

Critical Path : in main function

Answer 86