Đồ án, luận văn, do an, luan van

Weighted Graph
We can add attributes to edges. We call the attributes weights.
For example if we are using the graph as a map where the vertices are the cites and the edges are highways between the cities.
Then if we want the shortest travel distance between cities an appropriate weight would be the road mileage.
If we are concerne...

7 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 940 | Lượt tải: 0

Connected graph
A graph is connected if and only if there exists a path between every pair of distinct vertices
Sub-graph
A graph with the vertex and edge set being subsets of the original graph
Connected Components
A connected component of a graph is a maximally connected subgraph of a graph
Cycle
A path in a graph that s...

12 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 1005 | Lượt tải: 0

Depth-First Search 1. From the given vertex, visit one of its adjacent vertices and leave others; 2. Then visit one of the adjacent vertices of the previous vertex; 3. Continue the process, visit the graph as deep as possible until:
A visited vertex is reached;
An end vertex is reached Depth-First Traversal 1. Depth-first traversal of...

8 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 912 | Lượt tải: 0

We need also algorithm to traverse a graph like for a tree
Graph traversal may start at an arbitrary vertex. (Tree traversal generally starts at root vertex)
Two difficulties in graph traversal, but not in tree traversal: - The graph may contain cycles; - The graph may not be connected.
There are two important traversal methods: - Br...

6 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 855 | Lượt tải: 0

Undirected graphs
A graph G=(V, E) where V is a set of vertices connected pairwise by edges E.
Why study graph algorithms?
Interesting and broadly useful abstraction.
Challenging branch of computer science and discrete math.
Hundreds of graph algorithms known.
Thousands of practical applications.
Communication, circuits, tran...

11 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 925 | Lượt tải: 0

A B-Tree of order m (the maximum number of children for each node) is a tree which satisfies the following properties :
Every node has <= m children.
Every node ( except root and leaves ) has >= m/2 children.
The root has at least 2 children.
All leaves appear in the same level
A non-leaf node with k children contains k – 1 keys

8 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 914 | Lượt tải: 0

Symbol table: key-value pair abstraction.
Insert a value with specified key.
Search for value given key.
Delete value with given key.
Different implementations
Array
Linked list
BST (binary search tree)

10 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 969 | Lượt tải: 0

Generic functions
In a generic function, data should be passed in a generic way (by address and size).
If the algorithm demands a specific function to manipulate data (e.g.., compare two values), such a function should be passed using a function pointer.
Example: A generic search function on an array.
How to pass data to this funct...

11 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 828 | Lượt tải: 0

Binary search implementation:
maintaining two parallel arrays of keys and values, keeping them in key-sorted order. It uses binary search for get.
Linked list implementation.
Both put and get take linear time per operation: to search for a key, we need to traverse its links; to put a key-value pair, we need to search for the given key...

7 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 975 | Lượt tải: 0

Sorting algorithms are essential in a broad variety of applications
Organize an MP3 library.
Display Google PageRank results.
List RSS news items in reverse chronological order.
Find the median.
Find the closest pair.
Binary search in a database.
Identify statistical outliers.
Find duplicates in a mailing list.
Data compr...

12 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 978 | Lượt tải: 0