Graph Flashcards
Graph : Types of edge
Graph : Weight & Unweighted
Graph : Simple Graph
Graph : Multi Graph
Graph : Complete Graph
Graph : Pseudo Graph
Graph : Acyclic Graph
Graph : Basic Properties of Graph
Graph : Walk & Path & Trail
Graph : Connected & Strongly Connected
Graph : Adjency Matrix & Adjency List
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.
Undirected Graph : Def Structure (AdjList)
Undirected Graph : newListNode (AdjList)
Undirected Graph : CreateGraph (AdjList)
Undirected Graph : addEdge (AdjList)
1️⃣[src]head
2️⃣[dst]head
{
1.newnode
2.link :
From src to dst
From dst to src
}
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
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
In undirected graph, add a new vertice means it is connected to each previous vertices.
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
Graph : PrintGraph (AdjList)
Directed Graph : addEdge (AdjList)
Hints :
1.newnode
2.link
对比无向图，少了增加从dst到src的边的步骤
Directed Graph : DeleteEdge (AdjList)
Hints:
1.prev
2.current (array [src].head )
3.while : find the node
4.link
5. free
对比无向图，少了删除从dst到src的边的步骤
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
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
Graph : addition in deleteVetice （AdjList)
How to implement the following instructions?
1.move all the AdjNodes in each head forward
2.resize array
Graph: Difference between Basic Operations ( AjdList)
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.
Graph : def structure (Adj Matrix)
Graph : iniEdge (Adj Matrix)
Hint :
1.vertice
2.edge
3.initialise
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
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
Graph : addVertex (Adj Matrix)
Hints
1.if :
1️⃣ Vertex ++
2️⃣for :
1. ini last row
2.ini last column
else : full
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
Graph : PrintGraph (Adj Matrix)
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)
Disconnected graph: BFS algorithm (AdjMatrix)
1.visited
2.for :
if :
BFS
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)
Disconnect graph : BFS algorithm (AdjList)
Hints:
1.visited [ ]
2.call BFS
BFS :
Graph ： an easy way to create graph (Adj Matrix)
Graph : DFS (Adj Matrix)
Hints :
1. mark as visited
2.printf
3.for :
{
if :
}
DFS every unvisted nodes of the chosen vertex
It also works in directed graph, undirected graph and disconnected graph.
Graph : DFS Traversal (Adj Matrix)
Hints :
for : (view each vertex as independent graph)
It also works in directed graph, undirected graph and disconnected graph.
Graph : DFS (Adj List)
Hints :
1. mark
2.printf
3.while :
{
if:
}
DFS every unvisted nodes of the chosen vertex
It also works in directed graph, undirected graph and disconnected graph.
Graph : DFS Traversal (Adj List)
Hints :
for : (view each vertex as independent graph)
It also works in directed graph, undirected graph and disconnected graph.
Graph :Prim Algorithm
Hints:
1.又叫加点法
2.一开始的集合 V只有一个点
Graph :Kruskal Algorithm
Hints:
1.又叫加边法
2.一开始的集合 V有所有的点
Graph : Kruakal Algorithm 特殊情况
例题 ：最小生成树
例题 ：Prim & Kruakal Algorithm
Grpah : def structure concisely (AdjList)
Graph : See BFS explicitly
Graph : detail in BFS Algorithm
因为要先展开 A的邻接点 （图中的b、c）
Graph : See DFS explicitly
Hints :we can use a stack to simulate the process
例题 ：已知 图 AdjList ，求BFS 、DFS结果
Graph : Adj Matrix
In weighted graph :
Graph : What’s Spanning Tree?
Graph : Dijkstra Algorithm - Priority Queue
Dijkstra Algorithm : how the first vertice is added
Dijkstra Algorithm : how the n th vertice is added (n >1)
Dijkstra Algorithm : Print list
Dijkstra Algorithm : minDistance
Hint :(To find the vertex in list with min distance from source)
1.INT_MAX ,min_index
2.for
{
if ( unvisted & <min)
{
}
}
3.return
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
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.
Graph : a simple way to def graph (AdjList)
For the implementation of Kruskal Algorithm
Graph : 最小生成树 （Minimum Cost Spanning Tree) & 最短路径（Shortest Path ）的不同
Graph : difference of Prim Algorithm & Kruakal Algorithm
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.
Graph : Floyd Algorithm
Hints :
1.intialise
2.for ( k matrix)
{
for :
find smallest distance from i to j
}
3.print
Graph : How to calculate the matrix in Floyd Algorithm
Graph : 关键路径 - AOE网
Graph : 关键路径例题 - 求分别求 事件 、活动 的最早、最迟时间 & 关键活动
Graph : 关键路径例题 ：运用关键路径最本质的性质
Graph : 什么是拓扑排序？
Graph : 拓扑排序例题
Hint :看第二个图就可以了
Disjoint Set : how Parents array works?
Disjoint Set : Root Algorithm
Impact : to check if it has circle
Disjoint Set : unionSet (without considering rank)
Disjoint Set : explanation for why we need to consider rank in unionSet function
Disjoint Set : unionSet ( consider rank)
Graph : SortEdge function for Kruskal Algorithm
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
You have to know each edge contains weight,src and dst.
Critical Path : ES EL LS LF
Critical Path : What’s Critical Activity?
Critical Path : Details for determining EF & LS
Critical Path : Def
Hints :
1.task
2.dependency
Critical Path : calculateEarliest
Hints :
1.for :
{
1️⃣ini
2️⃣for
(
if ()
(
update i .ES
)
3️⃣update i.EF
}
Critical Path : calculateLatest
Hints :
for :
{
1️⃣ini
2️⃣for
(
if ()
(
update i .LF
)
3️⃣update i.LS
}
Critical Path : FindCriticalPath
Critical Path : in main function
