Graph Representation in Python
Knowledge Points Summary
1. Graph Representation in Python
Graphs can be represented in several ways in Python, depending on the specific problem and requirements. Below are some common methods for representing graphs:
Adjacency Matrix
An adjacency matrix is a 2D array where each cell (i, j)
represents the cost or presence of an edge between nodes i
and j
. This is particularly useful for dense graphs or when you need to perform operations that require quick access to edge weights, such as the Floyd-Warshall algorithm.
# Example of an adjacency matrix for a graph with 26 nodes (characters 'a' to 'z')
inf = float('inf')
adj_matrix = [[inf] * 26 for _ in range(26)]
# Example: Set distance from 'a' to 'b' as 5
adj_matrix[0][1] = 5 # where 0 is 'a' and 1 is 'b'
Adjacency List
An adjacency list is a collection of lists, where each list corresponds to a node and contains the neighboring nodes and edge costs. This representation is more space-efficient for sparse graphs.
# Example of an adjacency list
adj_list = {
'a': [('b', 5), ('c', 3)],
'b': [('c', 2)],
'c': [('a', 4)]
}
Edge List
An edge list is a list of tuples, where each tuple represents an edge and contains the source node, destination node, and edge weight. This is useful for algorithms that iterate over all edges, such as Kruskal’s algorithm.
# Example of an edge list
edge_list = [
('a', 'b', 5),
('a', 'c', 3),
('b', 'c', 2),
('c', 'a', 4)
]
2. Method of char_to_index
The char_to_index
method is a simple utility function that converts a character into an index, which is often used in algorithms that require mapping characters to indices in arrays or matrices.
Implementation
def char_to_index(c):
return ord(c) - ord('a')
Explanation
ord(c)
: This built-in Python function returns the Unicode code point for a given characterc
.ord('a')
: Returns the code point for the character ‘a’, which is 97.- Subtraction: Subtracting
ord('a')
fromord(c)
gives a zero-based index for lowercase English letters (e.g., ‘a’ -> 0, ‘b’ -> 1, …, ‘z’ -> 25).
3. Usage of zip
The zip
function is a built-in Python function that aggregates elements from multiple iterables (e.g., lists, tuples) and returns an iterator of tuples. Each tuple contains elements from the corresponding positions in the input iterables.
Syntax
zip(*iterables)
*iterables
: One or more iterable objects (e.g., lists, tuples).
Example Usage
source = "abcd"
target = "acbe"
for s_char, t_char in zip(source, target):
print(s_char, t_char)
Output
a a
b c
c b
d e
Explanation
zip(source, target)
: This creates an iterator that aggregates corresponding elements fromsource
andtarget
.- Looping: The
for
loop iterates over each pair(s_char, t_char)
, allowing you to process corresponding elements from the two strings simultaneously.
Use Cases
- Parallel Iteration:
zip
is commonly used when you need to iterate over multiple sequences in parallel, as in the case of convertingsource
totarget
in the problem. - Combining Data: It is also useful for combining data from different lists or arrays for joint processing or comparisons.
原文地址:https://blog.csdn.net/weixin_39280437/article/details/140733607
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!